我想做的是找出六边形网格上两点之间有多少个六边形。我曾尝试在线搜索公式，但找不到与我正在使用的十六进制网格类型匹配的公式。
六角网格的布局与此类似，具有相同的坐标系：http ://www.gamedev.net/index.php?app=core&module=attach§ion=attach&attach_rel_module=ccs&attach_id=1962
我知道使用此坐标系可能无法做到这一点，但这是我回去更改它之前的最后努力。非常感谢您提前。
问问题
17737 次
8 回答
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 度）。但是你必须为我的中学代数老师买一块饼干才能让它起作用，否则我会搞砸分配属性。
注意：可能需要摆弄负坐标，我没有检查。
于 2013-08-23T04:38:41.200 回答
7
感谢@user2709663 和@jonathankoren 提供答案。我花了很多时间来回答你的问题，但发现这两个都有一些问题。或者至少没有明确说明为这些答案考虑的网格类型。然而，我发现了一个非常好的教程和这个问题的代码实现，以及一个用于管理十六进制网格的库： http ://www.redblobgames.com/grids/hexagons/ （库代码：http://www.redblobgames .com/grids/hexagons/implementation.html）。我还为“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
于 2016-11-12T18:01:35.910 回答
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))
这使用 hex->square 表示：
------
------ 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 | |
--------------------------
于 2014-09-23T04:24:34.530 回答
4
要找到两个六角形之间的最短路径：
- 从一个十六进制开始，
- 在不同的行上，沿着对角线朝向另一行。
- 在同一行时，直奔另一个六角形。
我们称 x 方向dx的差异和 y 方向的差异dy。如果dy / 2 > dx，你不必做第二步，那么距离就是dy。否则，距离为dy + (dx - dy / 2)。除非我犯了错误。
于 2013-01-24T00:53:59.997 回答
2
MH Rasel 在他之前的回答中链接了这篇文章：Hexagonal Grids。在这篇优秀的帖子之后，我发现我需要立方体坐标；这提供了计算距离的最简单方法。这是 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)
编辑：我假设一个平顶六角网格。
于 2017-12-11T09:35:40.017 回答
0
If tiles on the grid can potentially become blocked then you are interested in the A* (or A-Star) maze-solving algorithm: http://labs.makemachine.net/2010/03/a-star-maze-solver/
The mechanism used in this video applies to a grid of squares, but with hardly any extra coding one could apply it to a hexagon mesh. For every tile, the solver knows which tiles to try next because the tiles store pointers to their surrounding tiles. In a grid of squares each tile would store a maximum of 4 pointers (maximum because they only store pointers to unblocked tiles), and the only difference in your case would be storing a maximum of 6 pointers.
If tiles are always traversable then A* will still certainly get the job done, however there is likely a faster way. If I'm interpreting your question correctly you're interested not in a distance, but in a whole-number count of the number of hexes between 2 given hexes? Try the following:
class Coord {
int x;
int y;
}
int dist(Coord hex1, Coord hex2) {
int xSteps = Math.abs(hex1.x - hex2.x);
int ySteps = Math.abs(hex1.y - hex2.y);
return Math.max(xSteps, ySteps) + Math.abs(xSteps - ySteps);
}
Why you may ask? This question is about determining how many times we must move vertically or horizontally as opposed to diagonally. We want to move diagonally as much as possible, otherwise we're not being smart about our distances. Math.abs(xSteps - ySteps) is the number of non-diagonal moves we must make. Add to that the greater of the distances of x and y, and you're done.
于 2013-01-24T01:46:29.450 回答
0
这是一个次优但不是太次优（应该是 O(n)）的算法：
首先，制作一个函数来确定六边形网格中某个位置的六边形是否与具有某个起点和终点的线段相交（例如，计算它所组成的六条线并执行以下操作：http： //alienryderflex.com/intersect/。）
其次，创建一个函数来确定一个点在六边形网格上的哪个六边形。
现在，像这样编写你的算法：
- 保留到目前为止线段重叠的所有六边形的列表
- 从线段起点所在的六边形开始
- 对于最近重叠的六边形周围的每个六边形，如果它不在列表中，请查看直线段是否与该六边形相交。如果是这样，请将其作为列表的新标题并重复
- 如果我们用完了要测试的六边形，请返回我们制作的列表
我建议您测试线段与六边形之间的接缝完全平行并沿着接缝延伸的情况，以查看您是否在一侧、两侧或都没有（因此停止）获得六边形。
于 2013-01-24T00:20:59.177 回答
0
如果您的六角平铺有方向：N、NE、SE、S、SW、NW，就像在Advent of Code 2017 问题 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)
我认为它可能适用于具有 EAST 和 WEST 方向的六角网格，而不是像你这样的 NORTH 和 SOUTH，只需切换 x 和 y 的角色。在这种情况下，您将朝着 self.y == 0 对角线移动（如果需要）等。
于 2017-12-15T19:56:18.033 回答