请问求最短路径算法

pos · 发表于 2013-10-6 21:11:06

除了Dijkstra算法还有什么算法？

北大侠客行MUD，中国最好的MUD

hijacker · 发表于 2013-10-6 21:18:50

有人跟我说他用过a*

hijacker · 发表于 2013-10-7 00:27:56

回复 1# pos

还有一种寻路算法在这里http://pkuxkx.com//forum/viewthr ... highlight=%2Bptouch，但是我不确定这是不是最短路径

alucar · 发表于 2013-10-7 06:44:47

这个算法的思路与a*有点象，都是从起点和终点同时寻路，提高效率，但算法过程不同。没有细看代码，但从算法思路的描述上看可能不适用存在单向路径的情况，比如无量山这种。

hijacker · 发表于 2013-10-7 07:37:01

回复 4# alucar
原来是酱紫。。受教了！

alucar · 发表于 2013-10-7 08:30:02

本帖最后由 alucar 于 2013-10-7 10:44 AM 编辑

又仔细对比了一下，Dijkstra是一种无方向的遍历寻路，目前看适用性最好，但效率比较低；a*通过对比每个节点与终点的距离来实现偏向终点方向的寻路计算，但需要一张比较标准的地图来实现准确的距离比较，在有丐帮暗道这种捷径的地方需要进行特殊处理，不过如何处理俺目前还没有看明白，a*可以从起点和终点同步寻路以提高计算速度，但双向寻路不适用于存在单向路径的情况；ptouch的那个纯lua寻路机器人更类似于一个基于Dijkstra的双向寻路计算，在路径选择上会优先选取分支比较少的节点，但同样不适用于存在单向路径的情况。

当然以上仅是目前的理解，记得最短路径至少还有另外两到三种算法，尚未深究。

pkuxfeng · 发表于 2013-10-7 09:33:22

npc跑的太快，最短路径意义不大了，次优（小范围的遍历）可能是方向

slapyou · 发表于 2013-11-2 07:11:36

最短路径到目标点+以目标点为中心小范围广度遍历

slapyou · 发表于 2013-11-2 07:15:22

对于目前情况显然是area之间用路径快速到达然后用寻路到目标继而无脑遍历这是智能的但是未必会比暴力的依照固定路径遍历快

		自动登录	找回密码
密码			注册