之前试了很多种思路的寻路,包括自己摸索的和A星算法,最后发现还是迪杰斯特拉算法好用,最终实现了这个兼具优良准确度、高效率、低负载的算法。
下面列出一些基本数据,让大家直观地感受一下这个算法的优缺点。
基础数据 | |
---|
目标 | 找出起点到终点的最短路径 |
算法 | 迪杰斯特拉(Dijkstra) |
地图 | 铁阪 |
节点数量 | 90个 |
路径数量 | 135条 |
脚本元素数量 | 核心脚本(248) + 节点(1443) + 其他(206) = 1897个 |
等待动作数量 | 1个 |
等待时间 | 不等待 | 0.01秒 |
---|
用时 | <1秒 | <1.5秒 |
负载峰值 | 255/255 | <50/255 |
由于迪杰特斯拉算法需要在每一次寻路中遍历全部节点,因此我省略了非必要的部分,也就是“能不去的地方就不去”,
比如一些地图边缘的血包就被我忽略了。
脚本运行方面,为了平衡运行时间和负载压力,我在循环最多的地方放了一个等待。
根据测试结果,当不使用等待时,90个节点可以在1秒内遍历完毕并生成路径,但负载峰值会达到100%,
但由于运行时间极短,因此这种高负载状态也不会持续很久;
而如果每次遍历都等待0.01秒,则负载峰值最高也只有不到50,且用时也仅需1.5秒左右。
这种结果完全是可以接受的范围,甚至大大超出了我的预期,迪杰特斯拉算法确实让寻路实现了速度快、负载低、体积小的目标。
现在利用这个算法,理论上可以为全部地图制作寻路路径,
但性能强劲是用繁琐的前期准备换来的,为了表现出最好的寻路效果,必须人工设置每一个节点,再人工设置每个节点之间的路径。
同时节点的数量越多,每次遍历的次数也越多,效率也会降低。
总结
此演示代码的操作:
玩家进入地图后,可以看见每个节点的位置。
左键=选择起点
右键=选择终点
注意:选择的节点是距离玩家最近的节点