在六边形网格上计算距离

Question

在六边形网格上计算距离

17

我想做的是找到六边形网格上两点之间有多少个六边形。我已经尝试在网上搜索公式，但没有找到与我使用的六边形网格相匹配的公式。

这个六边形网格的布局与此示例相同，并且具有相同的坐标系统：http://www.gamedev.net/index.php?app=core&module=attach&section=attach&attach_rel_module=ccs&attach_id=1962

我知道这可能在这个坐标系统中不可能实现，但在我回去更改之前，这是最后一次尝试。非常感谢您提前的帮助。

- DeathorGlory9

你是指以六边形为中心的点吗？换句话说，你想知道在[0,0]和[3,3]之间有多少个点吗？ - ChiefTwoPencils

是的，这正是我想要了解的。 - DeathorGlory9

1

你是在寻找两个六边形之间仅向左、右或对角线行走的最短路径步数吗？还是你在寻找更复杂的东西？ - jakber

我正在寻找两点之间最短路径上的六边形数量，例如，如果我在坐标为2,3的六边形上，并想要到达坐标为6,7的六边形，我需要穿过多少个六边形才能到达那个点。 - DeathorGlory9

11个回答

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

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

- Gershom Maes · Answer 1

如果在网格上的方块有可能被阻塞，那么您可能会对A*（或A-Star）迷宫求解算法感兴趣： http://labs.makemachine.net/2010/03/a-star-maze-solver/

视频中使用的机制适用于正方形网格，但只需要极少的额外编码即可将其应用于六边形网格。对于每个方块，求解器知道要尝试哪些相邻方块，因为这些方块存储指向其周围方块的指针。在正方形网格中，每个方块最多存储4个指针（最多因为它们只存储指向未阻塞方块的指针），而在您的情况下唯一的区别是最多存储6个指针。

如果方块始终可遍历，则A*仍然可以完成任务，但可能存在更快的方法。如果我正确理解了您的问题，您想要的不是距离，而是两个给定六边形之间的整数计数？请尝试以下操作：

class Coord {
    int x;
    int y;
}

int dist(Coord hex1, Coord hex2) {
    int xSteps = Math.abs(hex1.x - hex2.x);
    int ySteps = Math.abs(hex1.y - hex2.y);

    return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps);
}

为什么会这样问呢？这个问题是关于确定我们必须垂直或水平移动多少次，而不是对角线移动。我们希望尽可能地对角线移动，否则我们就没有聪明地计算距离。 Math.abs(xSteps - ySteps) 是我们必须进行的非对角线移动次数。加上 x 和 y 的距离中较大的那个距离，你就完成了。