| 模仿QQ连连看【思路、java源码】__教程 |
|
| 日期：2007-5-20 0:36:54 人气：143 [大 中 小] |
|
|
|
|
|
由于有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 （转化后的情况三，最左上的折点已经被替换） |
|
|
| 出处：本站原创 作者：佚名 |
|
|
