《从人类的思维方式中寻找启示宏观～微观寻径算法（1）.doc》由会员分享，可在线阅读，更多相关《从人类的思维方式中寻找启示宏观～微观寻径算法（1）.doc（6页珍藏版）》请在三一文库上搜索。
1、从人类的思维方式中寻找启示宏观微观寻径算法1寻找路径是游戏中人工智能的一个重要的主题。 特别是即时战略游戏随着游戏场景的增大，游戏场景的维数的扩充，游戏中参加寻径的智能体数目的增多，寻径的时间和空间开销都将会成为影响游戏性能重要因素。本文提出一种新的寻径算法思路：宏观微观(MacToMic)寻径算法。这种寻径算法思路相对于传统的寻径算法思路来说，更加类似于人human-like的思维模式。它结合了人类宏观启发式思维的优势和计算机微观处理的速度优势而产生的高效的寻径算法。传统的寻径算法及其弊端传统的寻径算法及其弊端传统的寻径算法比方广度优先算法和 AStar 算法都是基于单个节点进行寻径的。这种
2、算法模式具有明显的局限性寻径的效率时间和空间开销受制于寻径场景的节点数目，更进一步说就是受制于场景的精细程度而不是地图的复杂程度。虽然从地图的结构来说，图 1 和图 2 是完全一样的。 图 1 图 2但是对于基于节点搜索的广度优先算法和 AStar 算法来说它们并不会等同看待，而是在图 1 中所付出的寻径代价远高于图 2。当然在这个 1010 的地图上面问题的严重性并不明显，但如果是在一个 10001000 的地图涉及到 1000000 个节点的时候呢？更别说在一个100010001000 涉及到 1000000000 个节点的三维场景中了，这简直是一场恶梦！从人类的思维方式中寻求启示从人类的
3、思维方式中寻求启示对于同样的任务，人类的方法就高明得多了。人类压根儿不受网格的“束缚。在人类的眼中地图就如下所示：当然，让计算机超越“网格还不是那么容易的事情，因为对于计算机来说矩形实在太“优美了！读者可以尝试在上面的地图上面寻找两辆轿车之间的路径最好尝试把这条路径画出来 ，体会一下你自己是怎么寻找路径的。如果我估计得不错，我想你先观望一下两辆车各自的位置，然后大致上找到一条可通行的路径，最后在你画出路径的时候，你会按照你先前大致找到的路径的方向画出一条绕开所有障碍的路径。总结来说人类寻径的速度跟一张地图的复杂度，而不是一张地图的网格多少有关，而这些传统的寻径算法明显跟后者的关系大一些。较前沿
4、的寻径算法研究其实也正朝着这个方向，比方导航点法，还有分解矩形法等，让搜索节点数大大减小。但这些算法，都存在一些问题，比方导航点需要人为地设置，分解矩形法并没有很好地减小搜索的节点数。下面是从 PaulTozour 的寻径算法演示平台里面得到的一些图片。 导航点法 分解矩形法为了设计一种具有人这种能够从“宏观上寻径的计算机算法，我们回忆一下自己在一张地图上面寻找两点之间的较短路径的时候所做的工作流程，我首先会大致地扫描一下地图，大体地找到最短路径的“轮廓或许这样说缺乏准确，但是我想你能理解。 然后接下来在细致地“区分出最短路径。其实这个过程对一个人来说是非常自然的，但是我们怎么能用计算机算法来
5、实现这样“模糊“的概念呢？人和计算机毕竟有不同，我们不能像划分图多边形那样处理，因为经过那样的处理后，对于计算机来说依然很“模糊。最后我决定让地图分成很多较大的格子并通过预计算来处理这些格子之间的连通关系，然后在后续的寻径过程中可以大大地减少所需要搜索点的数目，事实上在某些情况下，还可以用最简单的试探式寻径从而更加减少广度优先搜索的开销，或 AStar 算法估值的开销，而且搜索出来的路径还特别自然！计算机和人不同，计算机总是认为正立的矩形相对于其它多边形更加亲切一些，这跟我们建立的笛卡儿坐标系有关 。宏观微观宏观微观(MacToMic)(MacToMic)寻径算法寻径算法简化的宏观微观寻径算法
6、简化的宏观微观寻径算法1 1预处理过程预处理过程遵照人类的思维方式，第一步是宏观地观察观察地图，所以在这个算法的第一步就是把地图分块，但并不像前面提到的那些寻径算法的分块方式通过很复杂的算法把地图分成大小不等而杂乱的很多块，而是简单地把地图分成大小相等的很多个小长方形，为了方便陈述，我举个例子，比方现在我们在一个 2525 象素的正方形地图上面寻径，我们可以把整个地图分块成 25 个 55 的正方形。第二个步骤是在每一个正方形小块的非障碍物点上面使用广度优先算法。当然，这个广度优先算法只有起始点而没有目标点，目的是得到该正方形小块与其上下左右四块小正方形小块的连通性就是说是否存在一条路径使到两
7、个正方形小块直接连通，注意是直接，就是说边界上是否有连通点，当然使用广度优先而不是简单的判断边界还有另外的目的，就是测试出本来的正方形小块本身是否是连通的，如果没有连通需要特殊处理，这里先不要考虑这种情况，方便理解算法。 如果，0 代表障碍，1 代表可行的话，那么下面的是 4个分块之间的连通关系：左上与右上连通，左上与左下不连通，右上与右下不连通，左下与右下连通。当我们完成对每一个小块进行上面的处理后，我们将得到一个表：每一个小块为搜索关键字，能够得到与该小块直接连通的小块的搜索关键字。 更抽象层次来说，其实这个表描述的就是一个关于节点之间是否相连的无向图。 一二步骤就完成了简化情况下的预处理
8、过程。 一旦完成预处理过程，对于同一幅地图就不需要重复预处理了，就是说后续的寻径过程都是基于这个预处理结果的。 2 2寻径过程寻径过程预处理完成后，可以开始寻找路径了。先判断待搜索的点分别属于哪两个正方形小块当然也许是处于同一个小块，这样的时候就用传统的算法处理 ，然后通过 Astar 或者干脆用广度优先算法搜索出这两个正方小块之间的最短路径这个路径当然是由小正方块为单位构成的，如果你还记得的话，每个小正方块是 55 的 。到了这步，我们就减少了很多需要搜索的点的数目，我们自然可以使用 Astar 算法或者广度优先算法在剩下的正方形小块里面以一个象素为搜索节点单位来搜索出始末点之间的最短路径。
9、不过，更简单快捷地我们可以试探法来得到一条看起来更自然的路径。可以想象出，我们现在得到的搜索空间是一条宽为 5 的带子形区域最短路径就存在于这个带子范围里面。 ，我们可以从起始点开始，以接下来一个相邻的正方形小块的中点为目标走过去这个过程具体是判断当前点和下一个相邻正方形小块的中点的坐标关系，比方，如果横坐标大一些，就向着减小的方向走，纵坐标大些，向着减小的走，如果两个都小了，就斜走。 当当前点一旦踏入下一个正方形小块，就立即把参考点改为再下面一个正方形小块的中点，一直下去，如果顺利的话，就能够很便捷地找到看起来比拟自然的路径，如果不顺利，一般是因为走进死胡同了，那么就走出来，再向没走过的方向
10、走，肯定能走到终点。 寻径的过程是这个算法的重要步骤，如果文字的说明大家不能很好地理解，那么请大家运行我做的算法演示程序，从那个程序的演示功能会让大家很容易地把握算法的搜索过程。 宏观微观算法在大格子里面的搜索演示宏观微观算法在小格子里面的搜索演示到了这里这个算法的简化版就算结束了。完整的宏观微观寻径算法完整的宏观微观寻径算法当然，仅仅像上面那样做的话，算法速度的提高还不算很多，比方搜索一个 125125的地图的时候，我们把地图分成 625 块 55 的小块，这样的话我们还得在一个有 625 块节点的地图上面搜索。但是应用上面算法的思想与及迭代的思想迭代的思想相结合把小块本身看成是一个寻径的单
11、位，对于这些小块组成的地图再进行一次“宏观的处理把 55 块55 的小块看成是一个大块。所以对于 125125 的地图我们第一步是把这个地图分成55 块正方形，每块正方形的大小是 2525，然后列出这些正方形的邻接表。接着把125125 的地图分成 2525 块 55 的正方形块，然后再列出这些小块之间的邻接表。读者最好按照这个例子粗略画出一个草图，那样更容易理解这个迭代过程搜索的时候第一步就是判断两个正方形处于哪两个大正方形2525上，然后就用Astar 或者广度优先找出最短路径，路径单位是大正方形，然后再判断这两个点在哪两个小正方形55里面，然后以上一个步骤所得到的大块为单位的路径作为搜索
12、空间，以小块为搜索节点，用 Astar 或者广度优先算法找出最短路径，最后用同简化版同样的算法得到真正的，以象素为根本节点的最短路径。这就是整个算法大致上的过程。这个算法通过对一个根本不变的地图做预处理，牺牲一些储存空间，从而大大提高后续每次寻径所需要的时间并且减小每次搜索所需要的空间。这种算法特别适合使用在那种地图精度高，但是复杂度比拟小的时候。 即时战略游戏地图大多属于这种类型。 根据一些统计数据，该算法在 1000 1000 的地图上面，速度是广度优先，AStar 等算法的 100 倍。思维慎密的读者会发现上面所描述的算法是不完全正确的，当一个分块本身并不连通的时候从同一个分块上面的某一个非障碍物点到同一个分块上面另外一个非障碍物点不存在一条仅仅经过该分块的路径 ，算法会发生错误的！如果没有意识到算法的这个缺漏的读者也可以仔细考虑考虑为什么会引起寻径结果的错误。在下一期将谈及如何解决这个问题，并进一步讨论如何把这个算法应用到游戏里面与及该算法的其它一些优良的特性，同时也指出其缺乏与及改良的向。