模仿QQ连连看【思路、java源码】

2008-02-23 09:53:31来源：互联网阅读 ()

模仿QQ连连看【思路、源码】

目录
一连连看的要求
二任意两点能否连通
三地图无解提示
四连接提示功能
五道具问题
六地图问题

一、连连看的要求

1：要连接的两点上的图形是相同的。
2：两点间存在一条没有“障碍”的并且折点不超过两个的路线。
那么分析一下可以看到，一般分为三种情况

【图例说明】
假设以一个2维数组来表示一张连连看的地图，数组中
元素值为0的代表游戏界面中的空格子，值大于0的代表游戏
中的各种连接对象（1代表星星、2代表企鹅之类）

情况一：要连接的两点在同一条直线上

0 0 0 0 0 0
0 2 0 0 0 2 * ------ *
0 0 0 0 0 0

情况二：经过一个折点相连（号代表折点）

0 0 0 0 0 0
0 2 0 0 0 * ------
0 0 0 0 2 ------ *
（两条路都可连通）

情况三：经过两个折点相连（针对企鹅来说，即数字2）

0 0 0 0 0 0 0 0 0 0
0 2 0 1 0 2 0 2 0 1 0 2
0 0 0 0 0 0 或者 0 0 0 0

由于有1这个障碍，所以需要两个折点才能连通

二、任意两点能否连通

寻路算法是整个游戏的核心算法。网上实现的版本也很多，这里
的方法是我比较容易理解的一个方法^o^ ，还希望大家能提出宝
贵的批评意见和建议，谢谢了。

思路如下：

1 一条直线上两点能否相连是好判断的（一个简单的循环判断即可）

2 对于上面图例的情况二，折点的坐标是固定的，即折点要么是

[连点1的坐标x，连点2的坐标y]要么是[连点1的坐标y，连点2的坐标x]

y

|
|
| * ------
| ------ *
---------------- x

所以，我们只需判断连点1到折点能否连通，连点2到折点能否连通即可
得知连点1和连点2能否连通。并且由于折点与两个连点分别是在同一条
直线上，所以可以由第一步轻松判断得出结论。

3 将情况三转化为情况二，（这一步是该算法中最影响性能和需要改进的地方）
怎么转化？

0 0 0 0
0 2 0 1 0 2
0 0 0 0 0 0 （情况三）

将和其中一个连点在同一条直线上的折点当作该连点，那么情况三就转化为
了情况二

0 2 0 0 0
0 * 0 1 0 2 （星号为原先的连点）
0 0 0 0 0 0 （转化后的情况三，最左上的折点已经被替换）

现在两个连接对象2之间的情形，已经变为情况二了。

4 由上可知，寻找这个被替换的折点就成了关键。因为其坐标不固定，所以只
好递归一个一个寻找了。寻找这个点需要做很多的优化（偶也没想到多少）

2 0 0 0 0 0 * 0 0 0 0 1 0 0 0 0
0 0 0 0 1 0 0 0 1 2 0 0 0 * 0 0 0
0 0 0 1 2 * 0 2 1 0 0 0 0 2 1 2 0 0

上面三个图，号是折点，*号就是需要被替换的折点

假设A、B两点是同一个图形，来思考一下下面的路线

0 0 0 0 0 0
0 0 1 0 B 0
0 0 0 0 0 0
0 A AA 0 1 0
0 0 0 0 0 0
0 0 0 0 0 0

如果我们的算法从向右开始寻找，顺时针方向旋转，那么A点先向右移动1格
到达AA的位置，这时测试AA与B是否能连通（按情况二处理）,结果不能，因
为折点出都有“障碍”（两个1），然后A点在移动，到达AAA处

0 0 0 0 0 0
0 0 1 0 B 0
0 0 0 0 0 0
0 A AA AAA 1 0
0 0 0 0 0 0
0 0 0 0 0 0

在AAA处，再次与B点测试连通的时候（按情况二处理），结果是可以，所以
A点可以与B点连通，路线为
*
|
* －－－

在增加一个障碍

0 0 0 0 0 0
0 0 1 1 B 0
0 0 0 0 0 0
0 A AA AAA 1 0
0 0 0 0 0 0
0 0 0 0 0 0

这次，当寻找到AAA位置时，结果为不能连通。在向右，由于有障碍，所以向
右这条路，宣告失败，递归返回到原点，换一个方向从A点向下在开始判断

0 0 0 0 0 0
0 0 1 1 B 0
0 0 0 0 0 0
0 A 0 0 1 0
0 AA 0 0 0 0
0 AAA 0 0 0 0 (向下仍不能连通)

向左，一样。最后向上

0 0 0 0 0 0
0 0 1 1 B 0
0 AA 0 0 0 0
0 A 0 0 1 0
0 0 0 0 0 0