4

我已经编写了 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)地图上，直线移动的成本实际上是对角线移动的数倍，它被计算为对角线移动的移动。问题是：如何修改我当前的启发式方法，以便为等距布局产生正确的结果？简单地替换为，反之亦然是行不通的。diagonalstraight

地图布局

4

2 回答 2

4

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

假设 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));
}

根据新的问题进行更新：

假设您正在尝试获取 distance(3,2; 3,3) < (distance(2,3; 3,3) = distance(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);
}

编辑：修复了可怕的错字......再次。

于 2009-08-12T15:12:12.567 回答
-1

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

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

编辑：颠倒了超链接的语法，哎呀。

于 2009-08-12T15:15:45.693 回答