她是一款神奇的小游戏，老少皆宜，百玩不厌，她是给一堆图案中的相同图案进行配对的简单游戏，在2003年，一个叫做朱俊的网友将这种形式搬到了PC上，立刻成为办公一族的新宠，并迅速传遍了世界各地，她就是连连看。没想到这几日我却和它邂逅出了一段趣事，而这一切都源于前几日我所在公司某产品在内部群里的一段对白：

蒋某：大家看这个页面，用户的头像怎么有重复的呢？又不是做连连看啊~
任某：Hoho，我们反倒不如在这个页面埋个彩蛋做个连连看呢？
众人：Blah,blah,blah…

于是我便来了兴致，苦思冥想两日，终于实现了称得上高效率连连看算法，而后便产生了这前端版的连连看，在此过程中有些许心得，遂记录于此，同诸君分享。

1、小人儿寻径思想

抽丝剥茧，连连看的核心无非就是给定一地图矩阵，并指定其上相同两点，判断此两点能否连通，能连通则此两点可消去，反之亦然，一旦实现了该核心算法，在此基础上稍加交互及特效，便有了一活灵活现的可视化连连看。

这么来说，我放置于起点一小人儿，让小人去穷举寻找到终点的路径，显然，有路则通，无路则不通，问题的关键在于小人儿每一步的下一步该怎么走，连连看的连线规则只能是直线，故小人儿的下一步最多是个三岔口，每遇到一个岔口我就让小人走其中一个方向，然后分别将其余的方向将小人之前走过的坐标轨迹合在一起作为备用线路记在脑子里。倘若当前路线走到死胡同抑或到了终点旁边但是拐弯超过了两次，就取出脑中的第一条备用线路并从脑中抹去，然后瞬间转移到该备用线路的最后一个坐标继续寻路，直到找到符合条件的路或者所有的备用路线都用光了依然无果时便停下来将是否有路的结果汇报给我。

2、效率问题让小人儿苦不堪言

如此一来会遇到一个问题，就是当地图矩阵越大，上边的障碍物越少的时候，小人儿的选择路线就会非常的多（远远超过最大允许的堆栈深度），此时小人儿从出发到给我汇报的耗时会让游戏的可玩性大大降低，如何让小人儿能够思考，能够优先选择最优路线呢？

3、启发式小人儿寻路算法

为了让小人儿每次都能聪明的选择接近最快到达目的地的路线，就要对上述算法稍加改造，启发式搜索就是在状态空间中的搜索对每一个搜索的位置进行评估，得到最好的位置，再从这个位置进行搜索直到目标，这样可以省略大量无畏的搜索路径，极大提高了小人儿寻径的效率。在启发式搜索中，对位置的估价是十分重要的，评价函数的形式如下：

其中是预评估的结点，是起始结点到预评估结点已知的耗散值，是欲评估结点到目标结点估算的耗散值，我的算法如下：

预估结点所在路线已用过的拐点

预估结点到目标结点最少所需的拐点数+预估结点到目标节点的距离

表示该点总的估值，估值越小，该点所在路线越接近最优路线

随便举个例子阐释下：

起始结点坐标：，目标结点坐标：，从起点开始，下一步有两条分支和，很显然点的估值较点的估值小，小人儿就会优先向下走，以后凡是遇到岔路均优先走估值最小的路线，如此一来，上例中的地图小人儿很快就能到达终点，图中蓝色轨迹即为小人儿所走的路线。

暂且说到这里，依然饶有兴致的童鞋请猛击这里查看DEMO，自行查看源代码。