基于A*的连连看启发式寻径算法

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

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

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

1、小人儿寻径思想

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

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

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

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

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

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

f(\alpha)=g(\alpha)%2Bh(\alpha)其中\alpha是预评估的结点,g(\alpha)是起始结点到预评估结点已知的耗散值,h(\alpha)是欲评估结点到目标结点估算的耗散值,我的算法如下:

g(\alpha)=预估结点所在路线已用过的拐点

h(\alpha)=预估结点到目标结点最少所需的拐点数+预估结点到目标节点的距离

f(\alpha)表示该点总的估值,估值越小,该点所在路线越接近最优路线

随便举个例子阐释下:

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

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

关于作者

Author: Guokai (腾讯微博 / Twitter / Google+ / Blog
Email/Gtalk: badkaikai@gmail.com

赞(0) 打赏
未经允许不得转载:WEB前端开发 » 基于A*的连连看启发式寻径算法

评论 8

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址
  1. #-49

    挺好的。支持下。哎俺还木有看明白。特别那个坐标是怎么建的呢。

    杭州-小白7年前 (2011-08-22)回复
    • @杭州-小白, 地图矩阵是一个函数随机生成的,不同的数字代表不同的两个图片,0代表可以走的路。

      郭凯7年前 (2011-08-22)回复
  2. #-48

    以前做游戏外挂的时候看了一下A*算法,没想到可以这么用,呵呵。

    Getil.Zhan7年前 (2011-08-22)回复
  3. #-47

    请问 f:1+2V5中 的2V5 是什么意思?

    gyrate7年前 (2011-08-26)回复
  4. #-46

    我在用jquery制作个人网站,,其中我想做鼠标到上方(hover)的时候会播放音效,不知道你有什么好点的解决办法吗?.谢谢了

    xnumb7年前 (2011-09-01)回复
  5. #-45

    不兼容FIREFOX,在IE下面效果不错

    wolfers7年前 (2011-10-19)回复

前端开发相关广告投放 更专业 更精准

联系我们

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

微信扫一扫打赏