用十六进制实现A-Star算法

Question

首先，让我说我是一个初学者，这个程序是我第一次尝试“单飞”，所以如果我听起来像个笨蛋，请耐心等待。

我有一个十六进制网格，我想使用A*来查找从一个到另一个的路径。

适合80 x 80正方形的十六进制瓦片在内部存储为二维数组，并在代码中由这些二维坐标引用(即，he0，0，he1，0等)。

它们以“令人震惊的”转换显示在屏幕上：

if (X % 2 == 0)
{
    X = (X / 2) * 120;
    Y = Y * 80;
}
else
{
    X = ((X / 2) * 120);
    Y = (Y * 80) + 40;
}

我已经设置了我的A*实现，但是很明显，每个十六进制相邻的6个十六进制中的两个被算作是2而不是1，并且哪两个是不同的取决于X是奇数还是偶数。

我试图阅读计算正确差异的方法，但我不确定从哪里开始实现我所见过的各种方法。有没有一个简单的转换，我可以对我已经有的坐标系进行简单的转换，纯粹为了计算十六进制之间的距离，或者一个我可以使用的公式？

谢谢。

Answer 1

如果我没记错的话，应该是这样的：

int HexDistance(int x1, int y1, int x2, int y2) {
  int y1d = (y1 << 1) | (x1 & 1);
  int y2d = (y2 << 1) | (x2 & 1);
  int dx = Math.Abs(x2 - x1);
  int dyd = Math.Abs(y2d - y1d);
  return (dx < dyd) ? (dyd - dx) / 2 + dx : dx;
}

假设网格是这样的：

X:   0  1  2  3  4  5  6                                                    
------------------------
Y:   0     0     0     0
        0     0     0
     1     1     1     1
        1     1     1
     2     2     2     2

其中垂线和对角线是相邻的，但水平线不是。

基本上，首先对y坐标重新编号:在偶数列中，将其加倍；在奇数列中，将其加倍并加1。这将生成以下网格：

X:   0  1  2  3  4  5  6                                                    
------------------------
Y:   0     0     0     0
        1     1     1
     2     2     2     2
        3     3     3
     4     4     4     4

现在，如果事物是对角线的，那就很简单了。如果水平方向较大，则只计算水平方向的差异；如果垂直方向较大，则计算垂直方向的差异直到对角线，然后添加水平方向的差异。

编辑：我又出错了。我活该，因为我想在凌晨5点开始编程很抱歉，希望这没问题。