六边形网格中瓦片之间的曼哈顿距离

Question

六边形网格中瓦片之间的曼哈顿距离

23

对于一个正方形网格，瓦片A和B之间的欧几里得距离为：

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

对于一个只能沿着正方形网格移动的角色，曼哈顿距离是我们必须走的实际距离的更好度量：

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

如何计算六边形网格中两个格子之间的曼哈顿距离，如下图红线和蓝线所示？

enter image description here

- Coyod

我不确定你的问题是否有意义。你是指如何测量红线或蓝线的长度吗？ - Chris Pfohl

这个问题看起来不太合理，因为它描述了在一个方形晶格中的欧几里得距离，但似乎要求在六边形晶格上进行曼哈顿距离的计算。 - Svante

1

对于之前的混淆，我是指通过其中一条最短路径从A到B需要多少步骤。 - Coyod

6个回答

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

- Mike Dunlavey

浮点数“偶数”有意义吗？使用位与运算符来检查浮点数的偶数性是否有效？ - Svante

@Svante：说得好。我加了一个强制转换。我之所以加入“double”是因为1/2可能会出现。 - Mike Dunlavey

浮点数通常不是有理数的好替代品。你确定在你打算使用的编译器中(int)1.0是1吗？如果是(int)0.999999或(int)1.00000001呢？如果你非常必须使用浮点数，请尽可能晚地生成它们。 - Svante

@Svante：又说到了一个好点子。你可以假设浮点数对于整数是精确的，但依赖它可能仍然不是个好主意。在这种情况下，使用半整数更为谨慎。我只是不想让代码变得更加混乱。 - Mike Dunlavey

感谢您的考虑。我的想法是在伪代码中不包含任何实现细节，即没有类型、没有强制转换、没有位操作、没有不精确的函数，并且“=”表示相等，而不是赋值。 - Svante

2

我假设您想知道如图所示的两个标识为瓦片的中心在平面上的欧几里得距离。我认为可以从图中推导出来。对于任何x和y，从瓦片(x, y)的中心到瓦片(x + dx, y)的中心的向量是(dx, 0)。从瓦片(x, y)的中心到瓦片(x, y + dy)的中心的向量是(-dy / 2, dy * sqrt(3) / 2)。简单的向量加法得到了一个向量(dx - (dy / 2), dy * sqrt(3) / 2)，对于任何x、y、dx和dy，它连接了(x, y)和(x + dx, y + dy)之间。总距离然后是向量的范数：sqrt((dx - (dy / 2)) ^ 2 + 3 * dy * dy / 4)

- Ted Hopp

2

这个问题没有简单的直接答案。这个问题的回答非常取决于你如何在内存中组织你的瓦片。我使用奇数列竖向布局，并且使用以下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/。您可以在此处获取完整的六边形图库：http://www.redblobgames.com/grids/hexagons/implementation.html

- Md Monjur Ul Hasan

1

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

- dthorpe

1

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

但对于大型场地来说，这可能效率低下。

- Argote

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

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

- aaz · Accepted Answer

我曾在一个游戏中设置了一个六边形坐标系统，使得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。