等轴测图的精确 A* 搜索启发式？

Question

我已经编写了 A* 搜索算法的实现。 问题是我目前使用的启发式方法仅适用于方形网格。 由于我的地图是等轴测图，启发式方法并未考虑地图的实际布局以及单元格之间的距离。

更新：经过广泛的记录和分析（理解为花费大量时间试图找出平庸），我得出的结论是我当前的启发式效果非常好，有一点例外：真实直线和对角线运动的最终结果是相反的。

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const
{
    int diagonal = std::min(abs(coord.x-goal->position.x), abs(coord.y-goal->position.y));
    int straight = (abs(coord.x-goal->position.x) + abs(coord.y-goal->position.y));
    return 14 * diagonal + 10 * (straight - 2 * diagonal);
}

这意味着，在等距地图上，直线移动的成本实际上是对角线移动的 sqrt(2) 倍，计算结果是对角线移动的成本。 问题是：如何修改当前的启发式，以便为等距布局生成正确的结果？ 简单地用straight替换diagonal，反之亦然将不起作用。

Answer 1

要尝试的一件事是将所有计算从等距坐标转换为方形网格坐标集。

假设 0,0 仍然是地图的根。 0,1 保持不变，1,2 变为 0,2； 1,3 变为 0,3； 2,3 变为 1,4； 3,3 变为 2,5； 0,2 变为-1,1； 等等。这会让你回到方形网格，这样坐标和启发式应该再次起作用。

Y 坐标变为 Y+sourceX 偏移量（3,3 位于 x=2 处；因此变为 2,5）； 事实证明，以数学方式找到 sourceX 本身更加困难。

[意识流； 忽略] Y=0 处的等距坐标对于源 X 来说是准确的。因此，要计算源 X，您需要“向左/向上移动 Y 次”，这应该会产生 Y/2 的变化； 向下舍入，在 X 坐标中......粗略地表明方形坐标为：

sourceX = X - Y/2
sourceY = Y + sourceX

其中 sourceX 和 sourceY 是普通方形网格中的坐标； Y/2 是整数算术/向下舍入。

因此，从理论上讲，这将变为：

double DistanceToEnd(Point at, Point end)
{
    Point squareStart = squarify(at);
    Point squareEnd = squarify(end);
    int dx=squareStart.X-squareEnd.X;
    int dy=squareStart.Y-squareEnd.Y;
    return Math.Sqrt(dx*dx+dy*dy);
}
Point squarify(Point p1)
{
     return new Point(p1.X-p1.Y/2, p1.Y+(p1.X-p1.Y/2));
}

基于新的问题进行更新：

假设您正在尝试获得距离(3,2; 3,3) < （距离（2,3；3,3）=距离（3,1；3,3））； 以下内容应该有效：（从 C# 翻译；不保证不存在拼写错误）

inline int Pathfinder::calculateDistanceEstimate(const CellCoord& coord) const
{
    int cx=coord.x - coord.y/2;
    int cy=coord.y + cx;
    int gx=goal->position.x - goal->position.y/2;
    int gy=goal->position.y + gx;
    int diagonal = std::min(abs(cx-gx), abs(cy-gy));
    int straight = (abs(cx-gx) + abs(cy-gy));
    return 14 * diagonal + 10 * (straight - 2 * diagonal);
}

编辑：再次修复了可怕的拼写错误。

Answer 2

Amit 此处计算“六边形的曼哈顿距离”。 它是 C++ 代码，我不能保证它，但 Amit 是我以前听说过的游戏开发名字。

六边形的曼哈顿距离应该适合适当的启发式。

编辑：反转超链接的语法，哎呀。