无水厕所即时战略游戏中实⽤的寻路算法都有哪些，⽐较如何？ rts中的寻路系统⼀般需要满⾜有以下⼏个条件，
1. 效率⾼，因为rts普遍地图⼤，单位多，所以处理效率很重要 2. 易编辑，以便于level design
3. 效果真实，如能出最优（或者是看上去合理）
如 所说，⼀般⽤于寻路的 算法是A Star，
⾸先是A Star有利⽤到启发式函数（Heuristic Function）[1]，和另⼀个算法Dijkstra（A Star的⽆启发函数版）相⽐可能会更有效率，因为启发函数设计得当，可以⼤⼤减少计算的数量。
因为启发函数的估计往往不是精确的，所以A Star [删：不像Dijkstra，] 不⼀定能出⼈类⼈之上的最优解，但是对于游戏来说，看上去合理就⾏。
然⽽⽤A Star作为寻路算法，仅仅是寻路系统的基本部分。
作为系统，它需要有易编辑的特性。
这就涉及到A Star中每个节点（Node）的 表现⽅式。
最基本的表现⽅式是⽅块（Tile），如下图 [2]
<img src="/96ce8f90c08c851f58d74671441d81f8_b.jpg" data-rawwidth="292" data-
rawheight="258" class="content_image" width="292">
其中，可以将⼭洞所占的的⼏个⽅块设为“Not Movable”，这样A Star就会不会考虑到这⼏个⽅块，系统所⽣成的路径就不会碰到⼭洞。
⽤⽅块作为A Star节点优点是简单，
不过也有⽐较多的问题，
第⼀是，如果地图很⼤的话，⽅块就会很多，这样A Star的节点就会⼤⼤增加，处理的时间相应地会增⼤。
第⼆是，单位的移动只能是上下左右，最多加上斜⾏，总共⼋个⽅向，不够真实
第三是，单位的体积⼤⼩不⼀样的话，⼤单位的图像可能会覆盖到“Not Movable”部分。以上⾯的图⽚为例，⼀条路径会经过在⼭洞边边，⼀个占四个⽅块⼤⼩的巨⼈⾛过的话，就会⾛在⼭洞上⾯。
为了解决上⾯的⼀些问题，我们可以使⽤路经点（Waypoint）来做A Star节点，如下图 [3]塔底油
<img src="/1539b841d4d4570edbb179faaff9eefc_b.jpg" data-rawwidth="341" data-
rawheight="347" class="content_image" width="341">
图中的红⾊的路径点代替了⽅块，成为A Star节点，这样的好处是我们可以⾃由地添加路径点，可以相对地减少A Star节点数⽬，
同时也单位也可以按照设计师设计的⽅法去⾛。
然⽽，从上图也可以看出它的问题不少，
第⼀是，如果是⼤地图，路径点数量太少会显得⽣硬。
第⼆是，需要考虑得⾯⾯俱到，不然⼀条直路忘了加路径点，单位就会“绕”（看上去）过去。
为了更好地解决以上所述的问题，导航⽹格（Navmesh or Navigation Mesh）出现了，如下图所⽰ [4]
<img src="/2d9d2bdb0a1bfde30b5f729bb52f1632_b.jpg" data-rawwidth="538" data-
rawheight="430" class="origin_image zh-lightbox-thumb" width="538" data-
original="/2d9d2bdb0a1bfde30b5f729bb52f1632_r.jpg">
现在，灰⽩⾊的多边形成为了A Star节点。
它解决了上⾯所出现的所有问题，
第⼀，从图中可以看出，节点的数⽬⼤⼤减少，因为多边形可以覆盖任意区域，不⽤限制成⽅块或点。
除了提升计算速度之外，编辑导航⽹格的效率也⼤⼤增加。
第⼆，通过计算直线两点和导航⽹格的相邻点（上图蓝⾊点）的位置关系，可以计算出两点是不是可以直接⾏⾛⽽没有阻碍物。例如上图从A点到B点通过计算可以得出可以直线⾏⾛，不⽤想⽅块和导航点那样绕来绕去。
第三，在转⾓位不⼀定要经过相邻点，可以加上单位的体积半径，这样不同体积的单位都可以合理地通过转⾓。
对于 建筑的考虑
在RTS中的寻路系统，还有⼀个很重要的话题，就是要可以应对动态的游戏世界。
⼀个简单的例⼦就是起建筑。
在⼀些需要频繁修改游戏世界的场景中，以⽅块为节点会更加容易作出修改 [14] ——只需要将建筑所占的⽅块的“Not Movable”修改成“Movable”。例如著名的塔防游戏《Field Runner》，应该是利⽤这种⽅法来实现的，⽽且作为塔防，《Field Runner》可以只在建
激光切割烟雾净化器
塔之后寻路⼀次，缓存起来就⾏。所以在这⼀场景中⽅块⼜成为了⼀个⽅便快捷的选择。
然⽽，导航⽹格也是可以动态修改的，不过开发难度会更⼤，⽽且运⾏中动态修改可能会造成延迟。有⼀些⽅法可以优化，例如动态地修改局部导航⽹格 [12]，或者是完全不修改，⽽将建筑看作局部的障碍物⽤另⼀套机制来应对 [13]。
其实除了A Star算法之外，还有其他算法，或者技巧，可以⽤于RTS的寻路系统，这⾥简单地介绍⼀下，
例如 Potential Field，
它是将地图⽤⼀个矩阵来表⽰，矩阵储存着⼤⼩不同的电势（整数）。 例如，正电势表⽰吸引，负电势表⽰排斥。
⽽游戏中的单位本⾝是⼀个负电势，游戏以⼀个数组储存所有单位的电势和位置 [7]。
这样，在计算⼀个单位需要怎么从A点到B点时，我们可以⽤⼀个新的矩阵将⽬的地B点设成正电势，并以不同⽅式（如圆形、四边形等）辐射开来，离B点越远电势越低，直到0。
然后将地图矩阵，⽬的地矩阵，和所有单位数组的电势相加，得出⼀个新的、反映当前游戏世界的电势矩阵，
然后单位再选择周围所有电势点中的最⾼电势点去⾛。
不过这⾥坑很多，因为它本质上是Greedy Algorithm，所以它未必能出解。[5]
然⽽在某些设定中，例如在没有过于复杂地形，并且需要单位⾃动不相互覆盖的情况下，Potential Field还是可以完成任务 [8]。
因为相⽐A Star的寻路系统来说，这个⽅法会⽐较简单。
还有 Flocking Behavior，
在对于⼀⼤单位的寻路，计算量是很⼤的，⽽且往往会有很多的重复，这些都是可以避免的。
如果单位的移动是利⽤Steering Behavior [9] 来实现的话，
那么就可以为其中⼀个单位，称之为Leader，计算路径（例如⽤导航⽹格），
然后其他单位按照以下Flocking原则来移动：
1. 分离，避开相邻单位
2. ⼀致，和整体的移动⽅向⼀致，这⾥应该是Leader的移动⽅向
3. 聚合，向整体的平均位置靠拢
这样的话，就可以降低寻路的计算量，并且得到更加真实的体单位⾏进效果。
另外⼀个技巧和Flocking Behavior类似 [10]，
对于不⽤Steering Behavior的⼀⼤单位，
可以将他们设为⼀个组，计算这个组的路径（并且要考虑到这个组的半径以便通过转⾓位），
然后给每个单位offset⼀个适当的距离，
如果遇到⼩的通道，例如门，可以适当调整offset。
《全⾯战争》⾥⾯⼀个队伍40⼈，⼤概⽤的就是这种⽅法 [11]。
还有⼀个优化技巧是 Chunk [15]。
这个技巧和 所提到的“先切分地图然后分块去做”应该是⼀致的。
在规模宏⼤的地图中，为了进⼀步提⾼寻路速度，可以在编辑地图时将⼀些节点处理成⼀个Chunk，它有⼊⼝和出⼝，并且不同Chunk之间需要连接起来。
从A点移动到B点，⾸先先在Chunk之间做寻路，得到⼀系列的Chunk，
在Chunk 1的时候只需要在Chunk 1中寻路，去到Chunk 2的时候就只在Chunk 2中寻路。
它本质上是将地图分为两种维度，⼀种是粗略的Chunk，⼀种是Chunk⾥⾯的节点（可以是⽅块，路径点，导航⽹格），并分开进⾏处理。有种空间分割（Space Partition）的味道在⾥⾯。
系统温度监控
异形这个⽅法我没有真正⽤过，还望⼤家补充。
还有D Star，它主要运⽤在机器⼈领域 [6]，可以在未知环境中寻路，不过我没接触过。
--------------Update 1----------------
1. 增加了Potential Field的简单说明
2. 增加了常⽤的启发函数例⼦
3. 完善了A Star说明，指出它不⼀定能出最优解
--------------Update 2----------------
1. 增加了Flocking Behavior在⼤单位寻路的应⽤
2. 增加了Flocking Behavior的替代技巧
--------------Update 3----------------
1. 增加了对于动态地修改游戏世界的考虑（如建筑）
--------------Update 4----------------
1. 增加了Chunk 优化技巧
--------------Update 5----------------
流水线称重1. 在 的帮助下，发现A Star和最优解的⼀个错误，已更正。A Star的启发函数在单调的情况下是可以出最优解的，但是这个最优解未必符合⼈类认知上的最优解，因为启发函数未必准确。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议