预运算地图寻路的一种方法
上次谈到服务器上寻路算法的优化。文末提到，其实，针对具体需求，我们实际上可以预运算所有的路径，把结果持久化在文件中，运行时用 O(1) 的时间就可以查询到任意路径。
对于半径为 N 的地图网格，选取任意两点作为起点和终点，一共有 N^4 数量级的路径，直接按起点和终点来缓存路径显然不现实。
但实际上，除非整张地图是个复杂的迷宫，大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上，整条路径和你从客厅出发是高度重叠的；仅有出家门前的那一小段略有不同。
在服务器上寻路，通常解决的是 NPC 的小范围内移动绕开障碍（从卧室到家门）的问题，远距离移动的路线（从家到公司）应当在另一个层面去解决。
基于网格寻路无论是用 A star 还是基于图的 dijkstra 算法都非常简单，这里不谈算法，只谈结果的持久化问题。
为了解决起点和终点有 N^2 种可能性，这个数量级太大的问题，我们可以适当的将地图划分成若干区域。如果每个区域都是一个内部没有任何障碍物的凸多边形，那么，当我们的起点和终点都落在同一个区域时，连接两点的直线就是最短路径。
如何划分区域，不是本文的重点。这里只简单说两句。如果障碍物基本上是轴对齐的，那么简单的贴着障碍线对分切割就好了。就是对地图不断的做二分的过程，空间划分用一个 KD tree 划分即可；如果障碍线不是轴对齐的，那么可以用 BSP 树做空间凸集的划分。
现在，我们假设地图已经划分为多个凸多边形了。如果我们的划分不算太畸形（避免出现细细长长的区域），那么基于这个划分方案，我们可以得到一个较优的路径。方法是这样的：
当起点和终点不在同一区域时，首先，我们找到起点到终点所属区域的轮廓任意一点的最短路径。即，最快靠近目标区域；然后，从目标区域的轮廓上的那一点直线通达目的地。
只要区域划分得当，这条路几乎是最优的。即使不算最短路径，也是非常好的结果。
如何找到一点到一个面（轮廓线）的最短路径？我曾经写过一篇 blog 谈我们实际使用过的一个算法 。
简单说就是，我们在网格图上先把目标区域的格子都涂上 0 ，然后把所有上色的格子的邻近格都加 1 ，逐步把整张图都填上数字。最终，没有数字的格子就是无法抵达的，而每个格子上的数字就是距离那个区域的最短路径的距离。
这张图可以视为一个流图，数字看作高度，当我们处于某个非 0 的格子时，只要向临接的格子中数字最小的走，就能最快的抵达最低点 0 ，整个过程就是最短路径。
任意一个区域中的任意一点到另一个区域的最短路径就可以储存在这么一张图中。图上每个格子都只需要记录一个方向。如果是四边形网格，就是 8 个方向加一个不可抵达标志，一共是 9 个状态，用 4bit 表示即可。当然也可以利用 8bit 记录更多的方向信息。
如果我们只处理划分好的区域中，每个区域的附近（直线距离）的有限个区域，那么就可以用一个非常紧凑的数据结构来保存所有的信息 。注意，临近区域未必是紧挨着的区域，只要空间直线距离不远都算。
首先，我们记录下地图上每个格子自己数据几号区域。然后在区域结构中保存下每个区域附近有那些区域。每个格子中额外记录到附近每个区域最短路径的方向（或不可抵达）。
运行时，我们只要查到目的地所归属的区域，然后在出发格上查询到对应区域的行动方向就可以移动了；或者在同一区域时直接直线移动。每来到一个新的格子时候就重新做一次查询，这个查询是 O(1) 的，且可以共享个服务器所有单位同时使用。这非常适合障碍是静态的，而目的地在不断运动（比如追逐一个移动的对象）的场合。
Comments
"对于半径为 N 的地图网格，选取任意两点作为起点和终点，一共有 N^4 数量级的路径，直接按起点和终点来缓存路径显然不现实。"
可以试试compressed path database + heuristic encoding, 内存小, ns级别查询.
例如 50GB路径数据可以压缩成10M
Posted by: sudo | (9) December 30, 2023 11:01 AM
迄今为止看到过的最快寻路算法,特别适合性能场合高的场景,太厉害了,请受我一拜!~~~
Posted by: 胡亚静 | (8) August 30, 2023 11:51 AM
不考虑动态障碍物，直接recast或自行自行实现navimesh速度快多了，内存也不耗。考虑动态障碍物不跟静态挡格链接的情况，直接在静态寻路的基础中应用计算几何绕动态挡格。比你好太多了，速度快，内存消耗少。餐卡slg的大世界寻路比如rok。
Posted by: zhulin | (7) October 27, 2021 01:35 PM
所以也是分级寻路？先寻大区域，再细化到点到点？
因为游戏地图，路线比较少，所以不需要缓存太多信息？
遇到动态NPC，就小区域再寻一下路？
Posted by: 谍海浮沉 | (6) February 7, 2021 12:07 PM
@菜鸟浮出水面
策划是个人么
Posted by: threezhiwang | (5) January 12, 2021 10:56 AM
感谢风哥分享心得，学习了。
Posted by: 大海 | (4) January 10, 2021 07:04 PM
导航算路也可以借鉴啊
Posted by: threezhiwang | (3) January 7, 2021 11:35 AM
高见！
Posted by: 罗伊 | (2) January 6, 2021 09:51 AM
如果障碍比较少。区域划分其实我感觉可以让策划自己针对地图划分好，区域内可以让策划也设置好路点，在区域内寻路就直接向路点跑，跨区域了就用路点当astar寻路去做，性能一定非常高。如果障碍确实比较多，围绕障碍体边延长切分或者边对分切分做凸集区域，然后在每个区域里的顶点跟边中点设置路点，区域内寻路就朝离目标最近的路点直线走，跨区域了就用路点寻路，应该也比较快。有点像navmesh的做法：D
Posted by: 菜鸟浮出水 | (1) January 5, 2021 04:32 PM