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

Question

对于正方形网格,图块A和B之间的欧氏距离为:

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

对于被限制沿着正方形网格移动的演员,曼哈顿距离是我们必须行进的实际距离的更好度量:

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

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

Answer 1

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

六角网格http://althenia.net/svn/stackoverflow/hexgrid.png?usemime=1&rev=3

该坐标系中的距离为:

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 for int y floor(y/2)is (y%2 ? y-1 : y)/2.