学步园

寻路算法在游戏中大量应用，在PC游戏里，更是随处可见。就比如星际争霸，红警这些超爽游戏中，用鼠标随便点一个地方，部队就会绕过一些障碍，并以最短的路径到达目的地。那么在手机游戏中怎样达到这种效果呢？这正是本文要讨论的问题。
这篇文章将首先讨论应该怎样实现，而不会给出具体代码。当然，在稍后的文章里，我会对代码做详细的说明，这样做也是为了减轻部分人因带宽小而导致打开网页过慢的问题。
说起寻路，你一定会想起A*这种是程序员都知道的东西，当然，在PC游戏中，A*由于其特色而被大量使用。后来，有些人觉得A*实在“太好”，总是会找出最短路径而导致游戏不太真实，因此，又发明了被我称作“A*++”的东西。
问题回到手机游戏。好像A*真的很好，但我们却不能用它，为什么？因为它太“大”了，我们的游戏会因为他死在手机上。前几天在QQ群里看到有人作了一个A*，当然，是测试用的，这不是不可以，但是如果真的用到游戏里，并且是体系较大的游戏里，就真TMD会死悄悄的！
现在的问题是，我需要在一个网络游戏中进行寻路，我应该用什么方法呢？有三个选择：

1.深度优先：即能走就走，若有多条路可走则按照一定的次序选择（如上下左右），但不走回头路。如果无路可走就退回。显然这种方法不一定能找到最短的路径，但它对内存的要求很小。由于与真实的找路过程有相似之处，所以可以让精灵直接按搜索的过程移动，不需任何等待。不过由于上下左右的次序太机械，精灵一开始并不是朝着最短的路线走去，所以移动路线还不够真实，特别在比较空阔的时候会容易找不到路。

2.广度优先：与深度优先搜索相对应的是广度优先搜索。这种方法的思路很简单，就是先搜索一步可到的点，再搜索两步可到的点......如此直到找到目标点为止。这种搜索方法显然能保证走的是最短路径，搜索速度也较快，不过对空间的占用较大。

3.启发式搜索：比如A*。（懒得讲，PASS掉）

我使用广度优先算法，因为如果在一种限制时间的游戏里，深度优先的速度将是无法容忍的。当然，广度优先会用不少的内存，当然，我相信你总有办法会解决。前阵子我也请教了GUST（猛玛技术总监）关于寻路这个问题，他同样认为广度优先是一种比较可行的在手机游戏里使用的方法。当然，不同的问题在不同的游戏中会有不同的应该效果，就比如广度优先算法，我在使用中也遇到了不少问题。我将会在下篇文章中给出代码以及一些问题的解决方案。（当然，水平有限，可能这些问题很拙劣）
如果你感兴趣，请联系我，我们一起讨论，QQ：70705327