22

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

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

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

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

如何获得六边形网格中两个瓷砖之间的曼哈顿距离，如下面的红线和蓝线所示？

在此处输入图像描述

4

6 回答 6

47

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

六角网格
（来源：althenia.net）

该坐标系中的距离为：

dx = x1 - x0
dy = y1 - y0

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

您可以使用以下方法将坐标系中的( x ', y ) 转换为 ( x , 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.

于 2011-02-22T23:26:02.543 回答
2

如果你想要直线距离：

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 个单位。

于 2011-02-22T22:44:08.877 回答
2

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

于 2011-02-22T22:40:52.147 回答
2

不可能直接回答这个问题。这个问题的答案与你如何组织内存中的磁贴非常相关。我使用奇数-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/grids/hexagons/ 。您可以在以下位置获得完整的 hextile 库：http ://www.redblobgames.com/grids/hexagons/implementation.html

于 2016-11-12T18:09:03.953 回答
1

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

不过，这对于大型字段可能效率低下。

于 2011-02-22T22:46:43.277 回答
1

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

于 2011-02-22T22:38:50.037 回答