1

我最近在 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)

如果有人可以指导我采用更好的启发式方法，我将不胜感激。

4

1 回答 1

0

（注意：WuTangTan 在评论中所说的仍然适用；这看起来也像您的实现中的一个错误）

只要启发式是可接受的，或者不高估路径的实际成本（有关更多详细信息，请参阅维基百科关于 A* 的条目），就可以保证正确的 A* 实现找到最短路径。对于不能沿对角线移动的网格，曼哈顿距离满足此标准。但是从您的图像来看，您似乎也可以沿对角线移动，因此曼哈顿距离不再准确判断距离。考虑这张图片：

示例图片

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

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

那么有没有一种启发式方法可以用来模拟对角网格的移动？你打赌！它被称为切比雪夫距离。它考虑了对角线运动，因此在这种情况下对距离建模要好得多。想想棋盘上的国王。

它的实现很简单：

function chebyshevDistance(dx, dy)
    return math.max(dx, dy)
end
于 2013-07-25T04:37:22.993 回答