我想做的是找到六边形网格上两点之间有多少个六边形。我已经尝试在网上搜索公式，但没有找到与我使用的六边形网格相匹配的公式。
这个六边形网格的布局与此示例相同，并且具有相同的坐标系统：http://www.gamedev.net/index.php?app=core&module=attach§ion=attach&attach_rel_module=ccs&attach_id=1962
我知道这可能在这个坐标系统中不可能实现，但在我回去更改之前，这是最后一次尝试。非常感谢您提前的帮助。
在六边形网格上计算距离
17
- DeathorGlory9
4
你是指以六边形为中心的点吗？换句话说，你想知道在[0,0]和[3,3]之间有多少个点吗？ - ChiefTwoPencils
是的，这正是我想要了解的。 - DeathorGlory9
1你是在寻找两个六边形之间仅向左、右或对角线行走的最短路径步数吗？还是你在寻找更复杂的东西？ - jakber
我正在寻找两点之间最短路径上的六边形数量，例如，如果我在坐标为2,3的六边形上，并想要到达坐标为6,7的六边形，我需要穿过多少个六边形才能到达那个点。 - DeathorGlory9
11个回答
10
如果你使用了一个沿着六边形两个方向的纹理前进的坐标系，你本可以使用：
distance = max(
abs(dest.y - start.y),
abs(dest.x - start.x),
abs((dest.x - dest.y)*-1 - (start.x - start.y)*-1)
)
但是您没有这样做，您正在使用一种波浪形坐标系统，该系统仅沿着一个方向（水平方向）与谷纹相符。幸运的是，我们可以使用转换方法在两者之间进行转换
straight.y = squiggle.y
straight.x = ciel(squiggle.y / -2) + squiggle.x
因此，使用这个方程组解决距离问题得到：
distance = max(
abs(dest.y - start.y),
abs(ceil(dest.y / -2) + dest.x - ceil(start.y / -2) - start.x),
abs(-dest.y - ceil(dest.y / -2) - dest.x + start.y + ceil(start.y / -2) + start.x)
)
这将为您提供两个六边形之间的曼哈顿距离，仅使用它们的坐标即可（假设我没有在输入x和y时出现任何打字错误，因为你的网格与我的旋转90度）。但是，如果要使其正常工作，您必须为我的初中代数老师买一个饼干，否则我将搞砸分配性质。
注意：可能需要微调才能处理负坐标，我没有检查。
- user2709663
10
感谢@user2709663和@jonathankoren提供的答案。我花了很多时间研究你们的答案，但发现两者都存在一些问题。或者至少对于这些答案考虑的网格类型并没有清楚地说明。然而，我找到了一个非常好的教程和解决方案的代码实现，还有一个管理六边形网格的库，网址是：http://www.redblobgames.com/grids/hexagons/（库的代码网址是：http://www.redblobgames.com/grids/hexagons/implementation.html）。我也写了一个matlab版本的距离代码，适用于“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
- Md Monjur Ul Hasan
5
这个被采纳的答案是错误的。当它提到在非正交轴上使用正交坐标时，我一开始就对它持怀疑态度，但是运行代码并将其与我的解决方案进行比较后，发现距离的过度估计会不断累积。
实际正确的解决方案是：
def hexDistance(start, dest):
if (start.x == dest.x):
return abs(dest.y - start.y)
elif (start.y == dest.y):
return abs(dest.x - start.x)
else:
dx = abs(dest.x - start.x)
dy = abs(dest.y - start.y)
if start.y < dest.y:
return dx + dy - int(math.ceil(dx / 2.0))
else:
return dx + dy - int(math.floor(dx / 2.0))
This uses the hexagonal to square representation:
------
------ 0, +1 ------
-1, +1 ------ +1, +1
------ 0, 0 ------
-1, 0 ------ +1, 0
------ 0, -1 ------
------
--------------------------
| -1, +1 | 0, +1 | +1, +1 |
|--------------------------
| -1, 0 | 0, 0 | +1, 0 |
|--------------------------|
| | 0, -1 | |
--------------------------
- jonathankoren
1
1这会给出一个太高的值，对于一个普通的六边形场地来说，它会导致字段向下对角线。 - Nico Müller
4
寻找两个六边形之间的最短路径：
- 从一个六边形开始
- 如果在不同的行上，请沿着对角线向另一行前进。
- 如果在同一行上，请直接朝向另一个六边形。
dx ，y方向的差异为dy。如果dy/2>dx ，则无需执行第二步，因此距离就是dy。否则，距离为dy + (dx-dy/2)。除非我犯了一个错误。- jakber
2
M H Rasel 在他以前的回答中链接了这篇文章：六边形网格。在阅读这篇优秀的文章后，我发现需要使用立方体坐标来计算距离。下面是 Kotlin 代码片段：
data class Point(val x: Int, val y: Int, val z: Int) {
fun distance(b: Point): Int {
return (abs(x - b.x) + abs(y - b.y) + abs(z - b.z)) / 2
}
}
var x = 0
var y = 0
var z = 0
val p1 = Point(x, y, z) // starting position
val steps = "ne,ne,ne".split(",") // go to North-East 3 times
for (direction in steps) {
when(direction) {
"n" -> { ++y; --z }
"ne" -> { ++x; --z }
"se" -> { ++x; --y }
"s" -> { --y; ++z }
"sw" -> { --x; ++z }
"nw" -> { ++y; --x }
}
}
val p2 = Point(x, y, z) // we arrived here
val dist = p1.distance(p2) // the result is here (in this example: 3)
编辑：我假设这是一个平顶六边形网格。
- Jabba
0
如果你的六边形平铺有方向：N，NE，SE，S，SW，NW，就像在Advent of Code 2017 problem 11中一样，并且你将目标偏移为（0,0）（通过提前从目标位置减去你的位置），以下逻辑对我有效：
def distance(self):
# Take diagonal steps towards self.x == 0
steps = abs(self.x)
# y moves closer to 0 by steps because moving diagonal, but never moving too far
if self.y > 0:
# Might still be positive, but never negative
y = max(self.y - steps, 0)
else:
# Might still be negative, but not positive
y = min(self.y + steps, 0)
# You move 2 positions north/south by a single move so divide y's by 2
return abs(y) // 2 + abs(steps)
我认为这个方法对于六边形网格使用东和西方向而不是像你的程序一样使用南和北方向，只需要交换x和y的角色即可。在这种情况下，如果需要，你可以朝着self.y == 0的对角线方向移动等。
- Peheje
0
很遗憾，我不知道你当时使用的是哪个坐标系统，因为链接已经失效了，但是这里发布的大部分解决方案对我来说都不起作用。 这是我使用的坐标系统：
------
------ 0, +1 ------
-1, +1 ------ +1, 0
------ 0, 0 ------
-1, 0 ------ +1, -1
------ 0, -1 ------
------
--------------------------
| -1, +1 | 0, +1 | |
|--------------------------|
| -1, 0 | 0, 0 | +1, 0 |
|--------------------------|
| | 0, -1 | +1, -1 |
--------------------------
这是对于点(x1,y1)和(x2,y2)适用的代码/公式：
public int distance(int x1, int y1, int x2, int y2){ //distance of hexfields, 1 is source 2 is target
int dx = Mathf.Abs(x1 - x2);
int dy = Mathf.Abs(y1 - y2);
if(dx == 0){ return dy; }
else if(dy == 0){ return dx; }
else{
if(x2 < x1 && y2 < y1){ //empty Corner
return dx+dy;
}else if(x2 < x1 && y2 > y1){ //Filled Corner
return Mathf.Max(dx, dy);
}else if(x2 > x1 && y2 < y1){ //Filled Corner
return Mathf.Max(dx, dy);
}else if(x2 > x1 && y2 > y1){ //empty Corner
return dx+dy;
}else return 0;
}
}
当然，这段代码的质量可以进行优化，但现在这样可能更容易理解。
- krmlks
0
这里有一种直接计算方法，它依赖于四个转换，将所有输入映射到正 y 向量和 30 度向量之间的区域。首先考虑平铺的六边形堆叠在 y 轴上，x 轴将是波浪线。
- 将第一个坐标转换为 0,0
- 将左半部分折叠到右半部分，保留 y 轴
- 将下行 30 度向量与 y 轴之间的区域折叠到 y 轴和上行 30 度向量之间的区域。下行 30 度向量将映射到上行 30 度向量。
- 将上行 30 度以下的区域折叠到 y 轴和上行 30 度向量之间的区域。
经过所有这些步骤后，最短路径是向上 30 度到目标 x，然后直接向上到目标 y。
def range x1, y1, x2, y2
# translate x1,y1 to origin and
# and fold left half over right side
rx = (x2 - x1).abs
ry = y2 - y1 - (rx % 2) * (x1 % 2)
# fold along 30deg downward
if ry <= -rx / 2
ry = ry.abs - rx % 2
# rx remains unchanged
else
# fold along 30deg upward
if ry < rx / 2
c = rx / 2 - ry # steps down from 30deg line
ry = rx / 2 + (c + (rx % 2)) / 2
rx -= c # rx update must be after ry
end
end
rx + ry - rx / 2
end
- user3278073
0
这里有一个关于C#和偏移“even-r”坐标的答案。 首先请查看这篇文章： https://www.redblobgames.com/grids/hexagons/
static int distanceBetweenCells(int x1, int y1, int x2, int y2)
{
Vector3 evenr_to_cube(int row, int col)
{
int q = col - ((row + (row % 2))/2);
int r = row;
return new Vector3(q, r, -q - r);
}
Vector3 point_1 = evenr_to_cube(x1, y1);
Vector3 point_2 = evenr_to_cube(x2, y2);
int a = (int)Math.Abs(point_1.X - point_2.X);
int b = (int)Math.Abs(point_1.Y - point_2.Y);
int c = (int)Math.Abs(point_1.Z - point_2.Z);
return Math.Max(a, Math.Max(b, c));
}
您可以根据上面的文章轻松地修改此内容以适应您的坐标类型。
- Griever G.F.
0
这里有一个次优但不太次优（应该是O(n)）的算法：
首先，创建一个函数，确定六边形网格中某个位置的六边形是否与具有特定起点和终点的线段相交（例如，计算它由哪六条线组成，并执行类似于http://alienryderflex.com/intersect/的操作。）
其次，创建一个函数，确定点位于六边形网格上的哪个六边形中。
现在，按照以下方式编写算法：
- 保留线段到目前为止重叠的所有六边形的列表
- 从线段起点所在的六边形开始
- 对于最近重叠的六边形周围的每个六边形，如果它不在列表中，则查看线段是否与该六边形相交。如果是，则将其作为新列表的头部并重复此过程
- 如果我们没有要测试的六边形，则返回我们制作的列表
- Patashu
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接