预运算地图寻路的一种方法
上次谈到服务器上寻路算法的优化。文末提到,其实,针对具体需求,我们实际上可以预运算所有的路径,把结果持久化在文件中,运行时用 O(1) 的时间就可以查询到任意路径。
对于半径为 N 的地图网格,选取任意两点作为起点和终点,一共有 N^4 数量级的路径,直接按起点和终点来缓存路径显然不现实。
但实际上,除非整张地图是个复杂的迷宫,大部分路径是重复的。这和人实际上行路是一样的。如果你从家中的卧室去到办公室的工位上,整条路径和你从客厅出发是高度重叠的;仅有出家门前的那一小段略有不同。
在服务器上寻路,通常解决的是 NPC 的小范围内移动绕开障碍(从卧室到家门)的问题,远距离移动的路线(从家到公司)应当在另一个层面去解决。
基于网格寻路无论是用 A star 还是基于图的 dijkstra 算法都非常简单,这里不谈算法,只谈结果的持久化问题。
为了解决起点和终点有 N^2 种可能性,这个数量级太大的问题,我们可以适当的将地图划分成若干区域。如果每个区域都是一个内部没有任何障碍物的凸多边形,那么,当我们的起点和终点都落在同一个区域时,连接两点的直线就是最短路径。