曼哈顿 六边形网格中瓷砖之间的距离

Question

对于方形网格，图块 A 和 B 之间的欧几里德距离为：

distance = sqrt(sqr(x1-x2)) + sqr(y1-y2))

对于被限制沿方形网格移动的演员，曼哈顿距离是我们必须行进的实际距离的更好衡量标准：

manhattanDistance = abs(x1-x2) + abs(y1-y2))

如何获取两个图块之间的曼哈顿距离如下图红线和蓝线所示的六边形网格？

Answer 1

我曾经在游戏中设置了一个六边形坐标系，使 y 轴与 x 轴成 60 度角。这避免了奇偶行的区别。

_{（来源：althenia.net）< /sub>}

此坐标系中的距离为：

dx = x1 - x0
dy = y1 - y0

if sign(dx) == sign(dy)
    abs(dx + dy)
else
    max(abs(dx), abs(dy))

您可以将 (x', y) 从您的坐标系转换为 (x, < em>y) 在这一点中使用：

x = x' - floor(y/2)

因此 dx 变为：

dx = x1' - x0' - floor(y1/2) + floor(y0/2)

使用整数除法实现此操作时请小心舍入。在 C 中，int y floor(y/2) 为 (y%2 ? y-1 : y)/2。

Answer 2

我假设您想要如图所示识别的两个图块中心之间的平面中的欧几里得距离。我想这可以从图中推导出来。对于任何 x 和 y，从图块 (x, y) 的中心到图块 (x + dx, y) 的中心的向量为 (dx, 0)。从图块 (x, y) 和 (x, y + dy) 中心出发的向量为 (-dy / 2, dy*sqrt(3) / 2)。对于任何 x、y、dx，简单的向量加法给出 (x, y) 和 (x + dx, y + dy) 之间的 (dx - (dy / 2), dy * sqrt(3) / 2) 向量，和迪。总距离就是向量的范数： sqrt((dx - (dy / 2)) ^ 2 + 3 * dy * dy / 4)

Answer 3

如果你想要直线距离：

double dy = y2 - y1;
double dx = x2 - x1;
// if the height is odd
if ((int)dy & 1){
    // whether the upper x coord is displaced left or right
    // depends on whether the y1 coordinate is odd
    dx += ((y1 & 1) ? -0.5 : 0.5);
}
double dis = sqrt(dx*dx + dy*dy);

我想说的是，如果dy是偶数，它只是一个矩形空间。如果dy为奇数，则右上角的位置向左或向右1/2个单位。

Answer 4

对这个问题的直接回答是不可能的。这个问题的答案与你如何在内存中组织图块有很大关系。我使用 odd-q 垂直布局，并使用以下 matlab 代码始终给我正确的答案。

function f = offset_distance(x1,y1,x2,y2)
    ac = offset_to_cube(x1,y1);
    bc = offset_to_cube(x2,y2);
    f = cube_distance(ac, bc);
end

function f = offset_to_cube(row,col)
    %x = col - (row - (row&1)) / 2;
    x = col - (row - mod(row,2)) / 2;
    z = row;
    y = -x-z;
    f = [x,z,y];
end

function f= cube_distance(p1,p2)
    a = abs( p1(1,1) - p2(1,1));
    b = abs( p1(1,2) - p2(1,2));
    c = abs( p1(1,3) - p2(1,3));
    f =  max([a,b,c]);
end

这是一个 matlab 测试代码

sx = 6;
sy = 1;
for i = 0:7
    for j = 0:5
        k = offset_distance(sx,sy,i,j);
        disp(['(',num2str(sx),',',num2str(sy),')->(',num2str(i),',',num2str(j),')=',num2str(k)])
    end
end

有关此解决方案的数学详细信息，请访问：http://www.redblobgames.com /网格/六边形/ 。您可以在以下位置获取完整的 hextile 库： http://www.redblobgames.com/grids /hexagons/implementation.html

Answer 5

这听起来像是 Bresenham 线算法 的工作。您可以使用它来计算从 A 到 B 的路段数量，这将告诉您路径距离。

Answer 6

如果将不同的六边形定义为图，则可以得到从节点 A 到节点 B 的最短路径。由于到六边形中心的距离是恒定的，因此将其设置为边权重。

不过，这对于大油田来说可能效率低下。