最优路径算法

1、9.4.3寻路算法路径选择问题是游戏开发中经常遇到的问题，比如热门的Android游戏crystallight， 游戏中的敌人需要寻找到一条路径前进，直到被杀死或者是到达终点；又如，棋类游戏中， 需要为棋子选择最”理智”的行进路径，以达到最佳棋面；再如，9.3.5节中提到的复杂游戏 AI，其核心就是为”飞机”寻找一条最理想的逃生路线。此外，在非规则实体的碰撞检测中， 也需要选择较优的路径到达碰撞边缘。类似的路径选择问题经常出现，但是如何合理地实现 寻路算法，是很多程序员需要解决的难题。A*算法知多少很多游戏开发者一提到寻路算法，就想到A*算法；一提到A*算法，就望而却步。下面 将揭开A*算法的

2、神秘面纱。A*算法确实是最高效、最流行的寻路算法，是搜索算法最深层的延伸A*算法由4个 要素组成：A*=估价函数+并查集+堆+广搜。A*算法必须有强大的算法功底和长年累月的实 战积累方能实现。另外，A*也并非总是最适合的算法，它仅仅是在不同运用领域表现出更 强的通用性，仅仅是在数据统计范畴内性能期望值最高。那么，A*是否适合移植到Android平台呢？我们需要进一步分析它的特点与专长。A* 算法的精髓是以空间换取时间，它的运用前提是：解空间充分大，运算时间受到刚性限制， 而存储空间（一般是内存）相对充足。如果将它移植到Android平台上，其一，手机系统的内 存资源弥足珍贵，A*算法将完全失去

3、用武之地；其二，手机游戏的寻路空间相对较小，解 空间相对狭隘。因而，搜索算法的瓶颈不再是冗余的搜索尝试，而估价函数的开销以及冗长 的代码将成为新的瓶颈。因此，A*算法并不是Android手机游戏的唯一选择，针对不同的 路径选择需要，应该定制不同的搜索算法。量身定制寻路算法设计寻路算法应该基于两个原则：开发者力所能及、算法力所能及。算法功底不是很雄厚的开发者，不必追求华丽的A*算法，可根据实际需要写一个普通 的宽搜或者广搜算法。毕竟手机游戏的解空间与PC游戏差了不止一个数量级，常规搜索的 时间开销也不会庞大。游戏开发者需要认真做好的是优化。其实，开发寻路算法的大门一直 都敞开着，只要开发者能够找

4、准游戏的定位，选准突破的方向。例如，热门塔防游戏-Robo Defense，它的搜索空间很小，对常规的搜索算法做一些优化，即能实现即时寻路。具备深厚算法功底的开发者可以根据不同的路径选择需求，选择最恰当的寻路算法。对 于解空间较小、实时性较高的游戏，A*算法将是最恰当的选择，设计高效的估计函数将成 为算法性能的关键；如果解空间较大，内存空间紧缺，那么采用迭代加深搜索算法效果更佳，此算法的内存消耗微乎其微，而且能够保证最先搜到最短路径；如果游戏中的精灵需要持续 寻路（比如NPC每走一步，都要寻找一次最优路径），那么遗传算法将是再适合不过的选 择了，每执行一轮遗传算法得到的最终种群、经过移位和补位处理可以用来优化下一轮的初 始种群，这将极其显著地消除重复性搜索尝试。需要特别注意的是，使用人工智能算法实现 寻路，虽然不能总是获得最优路线，但是量身定做的智能算法能够进一步节约内存消耗，能 够让游戏在Android手机上面更加流畅地运行，同时，智能算法求解出的，智能”路线往往也 会给玩家带来意外的惊喜与趣味。比如，蚂蚁吃蛋糕游戏应用了人工