等距地图的准确A*搜索启发式算法？

Question

等距地图的准确A*搜索启发式算法？

algorithmsearchheuristicsa-starisometric

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)倍，但是计算得出的代价与对角线移动相同。问题是：我该如何修改当前的启发式算法，以便在等距布局下产生正确的结果？简单地用straight替换diagonal或反之亦然是行不通的。 Map layout

- Electro

是的，但地图中的每个方格仍然是一组两个坐标。我们并不建议对所有内容进行大规模重写；只需要在计算启发式时进行一些数据处理即可。最终，我们仍然需要更好的描述才能更好地为您提供建议。（例如：我一直在谈论如何修复算法中的完成距离部分；重新阅读后，似乎您只是遇到了“到达此处的距离”部分的问题） - CoderTao

“到达此处的距离”部分就是启发式。我需要的是一种考虑地图布局不规则性的启发式。 - Electro

好的，那么再说一遍，你期望从这个启发式算法中得到什么输出？是这样的距离关系：distance(3,2; 3,3) < distance(3,1; 3,3) < distance(3,2; 3,3) 吗？ - CoderTao

假装最后一个是 distance(3,2; 3,3) < distance(3,1; 3,3) < distance(2,3; 3,3)。 - CoderTao

那差不多对了。第一个花费是10，第二个和第三个是14。但如果您愿意，请重新阅读更新后的问题。 - Electro

显示剩余5条评论

2个回答

-1

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

对于六边形来说，曼哈顿距离应该是一个适当的启发式方法。

编辑：反转了超链接的语法，糟糕。

- agorenst

不幸的是，在六边形网格上的图块只能沿着6个方向移动，而且每个方向的移动成本相同，所以我不能使用它。 - Electro

我的天，我完全读错了你的问题。不知怎么搞的，等距变成六边形了。对此感到很抱歉。 - agorenst

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- CoderTao · Accepted Answer

尝试一下的方法是将等距坐标转换为正方形网格坐标集进行所有计算。假设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 + 源X偏移(3,3在x = 2;所以变成2,5)；通过数学计算找到源X变得更加困难。

[意识流;请忽略]等距坐标在Y = 0时对于源X是准确的。因此，要计算源X，您需要“向左/向上移动Y次”，这应该会在X坐标中产生Y/2的变化；向下取整...粗略地建议正方形坐标将是：

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

编辑: 已修复可怕的错别字...再次。