在Lua中的A*寻路算法

最近我在 Lua 中实现了 A* 寻路算法,但由于在成本中使用曼哈顿方法来处理 H 值,所以我遇到了错误的路径问题。

我想了解是否有其他方法来计算节点的成本。 下面是我目前正在使用的方法:

function CalcG(A,B)
    if type(A) == "table" then
        A = A.Pos
    end
    if type(B) == "table" then
        B = B.Pos
    end
    return (A-B).Magnitude
end

function CalcH(A,B)
    if type(A) == "table" then
        A = A.Pos
    end
    if type(B) == "table" then
        B = B.Pos
    end
    return math.abs(A.X - B.X) + math.abs(A.Z - B.Z)
end

function GetCost(A,B,C)
    return CalcG(A,B) + CalcH(B,C)
end

计算成本:

GetCost(Start,CurrentNode,End)

如果有人能指导我使用更好的启发式方法,我将不胜感激。

点赞
用户646619
用户646619

只要启发式是“可接受的”(不高估路径的实际成本),正确的 A * 实现就能保证找到最短路径(有关更多详细信息,请参见Wikipedia上的A*条目)。对于一个不能对角线移动的网格,曼哈顿距离可以满足此标准。但从您的图像来看,似乎您也可以对角线移动,因此曼哈顿距离不再准确地评估距离。考虑这张图片:

![Example image](https://i.stack.imgur.com/cb1On.png)

蓝色是曼哈顿距离,绿色是“正确”的距离。

正如您所看到的,当我们添加对角线移动的能力时,两点之间的距离变得更短。曼哈顿距离现在高估了距离,因此不可接受,导致 A * 不总是找到最短路径。

那么,我们可以使用什么启发式来模拟对角线网格移动呢?当然有!它被称为**切比雪夫距离**。它考虑到对角线运动,因此更适合在这种情况下建模距离。想象一下在棋盘上的国王。

它的实现很简单:

function chebyshevDistance(dx, dy)
    return math.max(dx, dy)
end
2013-07-25 04:37:22