记录和分享GPS寻路方法和算法优化的一些思路

xiaozihe

近些天在做北侠GPS，在将北侠地图所有房间全部连通前提下(不进行区域划分)，遇到寻路计算耗时较长的问题。
1.对于寻路算法
简单的BFS算法是行不通的，因为BFS算法只能找到最短路线而无法找到最优路线的。即可能找到的是步数最少的路线，但是可能代价(比如路线行走的耗时和交通花费)不是最少的。
我采用的是Dijkstra算法。因为这种算法起码保证了可以获得最优路径，即使寻路耗时长一点又怎么样呢，毕竟玩北侠最不缺的就是时间~~，这是我刚开始的想法。
注：曾看见Q群里有大佬说可以采用A*算法，然而我并不明白在北侠中A*算法中的启发函数h(n)如何确定。如果可以，恳请大佬指教，小弟先在此谢过。
2.寻路算法耗时及优化
一开始，我的路径算法耗时比较长，比如从"黑木崖的黑木崖下"到"平西王府的书房"，这个路线的寻路过程基本遍历了地图所有的房间，大约需要耗时1600ms(1.6秒)。
后来我进行了预加载数据库到内存，并在处理table时（如等待处理的房间列表openList和已处理的房间列表closeList），由原来的数组改为采用哈希表形式(key-value)进行保存和比较(哈希表效率比数组高很多)，计算速度得到了质的提升。仍然以"黑木崖的黑木崖下"到"平西王府的书房"的路线进行测试，大约只需要130ms(0.13秒)，其他的短路线的计算耗时就更快了，一般都在100ms以内。
上述功能已测试了几天，目前运行良好

ppmm

求分享

man

非常不幸的是别人是他的1/10

jarlyyn

北侠的房间的数量级完全不需要优化吧……

当年我记得搞过双向逼近的，但发现完全没必要的。

jarlyyn

man 发表于 2023-4-30 04:23 PM
非常不幸的是别人是他的1/10

试验了下，的确……

campsun

支持楼主，我也是写了一堆各种寻路算法，再慢慢选择合适的。
楼主的这段路，我这里是 0.02s，还有优化空间，加油努力~

xiaozihe

谢谢各位大佬的提示。晚上对算法进行了优化，仍然以上面的路径进行测试，计算耗时一般在稳定在35ms以内。现在是休假在家，用的是5年前配的旧电脑，不知道新电脑对速度有没有提升，待收假回去后再进行测试。

我的地图还不是很完善，所以计算路径上可能有差异。另外，如果采用坐车的方式，则会少走一些路，计算路径应该会快一些。我是刚玩不久，号上缺钱，目前是能省则省，所以一般都不坐车。

xiaozihe

今天回到家，用家里的电脑测试了一下，计算耗时一般在25ms以内：

我的电脑硬件配置如下：

maxcn

能分享一个哇？

kumarajivar

你这个使用mudlet平台，还是跨平台的啊？