“连连看”小析
“连连看”小析
“连连看”小析
一.缘起
近段日子与几位同事聊到了“连连看”这个小游戏，感觉还颇有些趣味，虽然其本身规则并不繁琐，但玩起来确实很能让人投入。出于自己的一点追究癖，自己这几天还认真考虑了一些“连连看”游戏的实现方式，并且也有事没事的写了一点代码，发现虽然“连连看”这个游戏看上去挺简单，想要比较好的实现却也需要不少的努力（当然也可能是自己的能力有限啦……），所以决定将其间的一些思考记录下来，整理一下自己思路的同时，也可以给一些想要了解的朋友一些参考，当然我最希望的是有兴趣的朋友可以交流指正 ：）
另外一提的是，网上关于这方面的资料我没有细找（不过游戏下载非常之多 ：）），只看到 《编程之美》 这本书上有一篇专门讨论“连连看”的文章，有兴趣的朋友可以翻出来看看，讲的很好：）
二.探索
下面我便依着自己的思考过程来番流水账式的记录：
1. 如何随机生成Map（地图）
第一个问题是如何生成随机地图，一开始的思路非常简单，就是将一堆待排的图片随机的摆放于棋盘上，中间无非是记录一些图片剩余数量之类的中间参数，后来与同事讨论时才意识到了“死锁”问题。而所谓“死锁”，即是游戏地图无论如何都无法消去的情况，最简单的应该算这种了：
1 | 2 |
|---|---|
2 | 1 |
按照常规的三条连线消去的“连连看”规则，这幅地图中的四个图案是不可能被消去的，而我们随机生成的地图自然必须要规避这种情况的，一开始的想法是能否找到一些启发式的排列规则，使其按照此种排列便可顺利回避死锁问题，但是这条思路后来并未有给我非常清晰的答案（有知道的朋友麻烦告知一声），于是我退而求其次，即让随机排放“尽量”规避死锁的问题，就这这个方向，我大抵想到了两套方案：
① 随机生成一张地图，然后让程序首先进行检查，如果确认可以避免死锁问题，那么地图检测通过，否则重新生成，实现来讲趋于复杂，效率也比较低下，但是可以基本规避死锁问题。
② 随机生成一张地图，但并不进行合法性检查，但提供所谓的重排功能，即当无法继续游戏的时候可以重排游戏图案，在很大程度上来解决死锁问题，实现来讲比较简单，效率高效，但是并不能根本上解决地图死锁问题。
比较上述两种思路，最终我还是选择了后者，原因上我还是趋于简单的解决方案，并且第一种方案也存在生成失败的情况（一直重复生成，然后检测失败），而且就游戏而言，效率基本上都要优于正确性，我想这也是目前很多游戏都采用“重新洗牌”的原因吧：）
既然不用考虑有效性的问题，那么随机化地图的方法就可以多种多样了，目前的做法是采用非常简单的置换法，即首先依次将图案整齐的排放至地图中，然后随机交换图案位置。
涉及到实现细节，示例代码中，
bool RandomSetStateTable( int randomness );
这个函数即是用于随机化地图的，参数指定了随机化的程度，越高越随机。
void ReRange();
这个函数则是用来重排地图的，使用的方法其实也是简单的置换而已 ：）更具体的细节大家可以参看源码。
二．如何搜索指定两个图案之间的路径？
“连连看”中最重头的戏码便是搜索到指定两个图案之间的“最短”路径。这里的“最短”打上引号其实是有原因的，因为“连连看”游戏中的“最短”路径其实并不是要求路径长度最小，而是要求路径转弯数最少，即以下两种路径下，第二种虽然路径长度与第一种长度相同，但是由于其所需的直线数目最少（转弯数目最少），所以其即是两条路径中的较短路径。
一开始的我也忽视了上面的问题，即采用简单的广度优先算法来搜索两个给定图案之间的距离，导致的问题便是：
相同的两点，或者说两个图案，当链接的顺序不同时，产生的结果却不同。以上面的示意图为例，可能选择连接（0，0）（2，3）时，获得的路径是“路径1”，而选择（2，3）（0，0）时获得的路径却是“路径2”，当然，这并不是BFS本身的问题，而是我定义路径长短的标准问题，由于我一开始简单的以路径长度为标尺，遂而导致了程序判断“路径1”和“路径2”等价的问题。
找到病症之后，我做了一些修改，目前的搜索方法是，首先沿着同一方向搜索到底，直到发现遇到了边界，再尝试从不同的方向进行搜索，由于“连连看”不存在斜连的情况，所以对于每一个节点来说，每次最多都只在四个方向上进行搜索，加上目前的搜索过程修改为了单一方向优先，所以每次都仅需从相反的两个方向上搜索即可：
通过上面的示意图可见，这种方法可以达到“连连看”“最短”路径搜索的目的，其实说到底，这种方法仍然属于正统的BFS，仅仅是将在同一直线上的节点都看成是兄弟节点而已，当然，你也可以规定在同一直线上某一范围内的节点是兄弟节点来展开搜索，具体的情况还是要根据具体的问题领域来进行分析。
从实现的角度来讲，示例的代码中提供了：
int GetLinkCount( const StatePoint& p1, const StatePoint& p2 )
来获取指定两点之间的连接直线数目，并且不会考虑两点的内容是否相同，仅仅是返回两点间的连接直线数目而已，如果不存在链接，便返回NO_LINK（-1）。
typedef std::pair<int,StatePoint*> LinkPath;
LinkPath GetLinkPath( const StatePoint& point_1, const StatePoint& point_2 );
这个函数具体的返回了从指定点point_1到point_2的链接路径，LinkPath.first指明路径中的节点数，LinkPath.second则是存储了各个节点的数组指针，注意的是该数组是动态分配的，所以你需要在调用之后处理内存释放的问题，当没有连接时返回LinkPath（0，NULL）。
三. 杂项
当然，实现过程中还有一些小问题，由于很小，不便单独成项，所以和在一起讲讲，也算是一个总结。
首先一点是使用什么数据结构来表示游戏状态，由于“连连看”的游戏Map太像二维数组了，所以采用数组的表示方法应该是最直观的想法。
需要注意的一点是“连连看”的链接路径可以允许经过外围：
比较简单的一个解决的方法是在游戏内部表示时，采用“大一圈”的数组表示，但是对外暴露的接口一定要隐藏这个实现细节，这点上确实很容易让人犯错 ：)
目前代码中提供了构造函数：
LinkNow( int row, int col, int limit_link_count, int kind_number );
参数的意义分别是：行数、列数、最大连接直线数以及图案种类，默认状态下是10*10、最大连接为3、图案数目则是25。
另外一提的是获取下一对可以连接的节点，用于实现游戏的提示功能，目前的实现方法还比较粗糙，具体的思路便是一次查找相等的地图并尝试连接，一旦连接成功，则返回，其间可以优化的地方还有不少 ：）
实现来讲，代码中提供了：
typedef std::pair<StatePoint,StatePoint> LinkPair;
LinkPair GetLinkPair();
用于获取目前游戏状态下可以连接的节点对。
其他的一些获取功能函数都比较简单，在此不再赘述，有兴趣的朋友可以参看源码。
四. 总结
“连连看”虽小，但是其间的道理也不简单，各种的问题都需要好好的处理分析才能基本理解，放而广之，我们平时生活工作中是否也有不少我们以为简单却实际上很不简单的事情存在呢……？
“连连看”的内部逻辑实现可以看这里，其中附带了两个实例程序，一个是控制台的，一个则是用HGE实现的图形化程序，内部的逻辑都是同样的，有兴趣的朋友可以看一看 ：）