环绕六边形地图中的距离计算

Question

所以我正在尝试获取六边形平铺地图的基本计算。我使用的是菱形样式地图，如这个经典宝石所示(选中"菱形"选项)：

https://www.redblobgames.com/grids/hexagons/#map-storage

在我的地图中，R和Q不一定相同，也就是说，地图可以是"矩形"。由于地图同时用 R 和 Q 换行，因此有许多可能的正确距离，我有兴趣找到其中最短的距离。

例如，如果你去 (0

， 0) - (1， 0) - (2， 0) - (3， 0) - (4， 0) - (4， 1) - (4， 2)，则从 (0， 0) 到 (4， 2) 的距离是 2 - (5， 1) - (6， 0)=(0， 0)所以我得到了这个代码，它正确地计算了这个包装距离：

public static Integer distance(HexCubeCoord origin, HexCubeCoord destination) {
// Normalize destination taking origin to (0, 0)
Integer dR = destination.getGridR() - origin.getGridR();
Integer dC = destination.getGridC() - origin.getGridC();
// Wrap normalized distance
HexCubeCoord normDest = new HexCubeCoord(HexCalculator.wrapR(dR), HexCalculator.wrapC(dC));
// Calculate distances to (0, 0) and the other three mirror origins
Integer d0 = simpleDistance(new HexCubeCoord(0, 0), normDest);
Integer d1 = simpleDistance(new HexCubeCoord(0, HexGridData.getColCount()), normDest);
Integer d2 = simpleDistance(new HexCubeCoord(HexGridData.getRowCount(), 0), normDest);
Integer d3 = simpleDistance(new HexCubeCoord(HexGridData.getRowCount(), HexGridData.getColCount()), normDest);
// Return the min of those four distances
return Math.min(Math.min(Math.min(d0, d1), d2), d3);
}
public static Integer simpleDistance(HexCubeCoord origin, HexCubeCoord destination) {
Integer dR = destination.getGridR() - origin.getGridR();
Integer dC = destination.getGridC() - origin.getGridC();
Integer dZ = - dC - dR;
return Math.max(Math.max(Math.abs(dR), Math.abs(dC)), Math.abs(dZ));
}

现在，我将使用距离计算很多，我希望它更简单。我已经花了很多时间尝试减少所需的操作量，特别是我想避免计算到四个镜像原点的距离，以获得之后的最小距离。

我不要求明显的优化，例如避免实例化新对象，这些对象我可以稍后弄清楚。我可以使用任何数学魔法来简化此算法吗？

Answer 1

经过大量的工作和时间，我终于发现了一个距离计算，它似乎适用于我所有的测试用例。

我希望回答我自己的问题没问题，我将结果的距离计算发布在环绕的六边形地图中，以防其他人觉得有趣。

public static Integer distance(HexCubeCoord origin, HexCubeCoord destination) {
// Normalize destination taking origin to (0, 0)
Integer dR = destination.getGridR() - origin.getGridR();
Integer dC = destination.getGridC() - origin.getGridC();
// Wrap normalized distance to get closer to (0, 0)
// Wrap c-wise
if (Math.abs(dC) >= HexGridData.getColCount() / 2) {
dC = (HexGridData.getColCount() - Math.abs(dC)) * (- Integer.signum(dC));
}
// Wrap r-wise
if (Math.abs(dR) >= (HexGridData.getRowCount() / 2) - Math.floor(dC / 2)) {
dR = (HexGridData.getRowCount() - Math.abs(dR)) * (- Integer.signum(dR));
}
Integer dZ = (- dC - dR);
// Calculate distance in the usual form
return Math.max(Math.max(Math.abs(dR), Math.abs(dC)), Math.abs(dZ));
}

它从 https://blog.demofox.org/2017/10/01/calculating-the-distance-between-points-in-wrap-around-toroidal-space/中概述的方法开始，但是当包装 r 时，我添加了"- Math.floor(dC/2)"部分，以补偿网格在 (+， +) --- (-, -) 对角线上的同化。

编辑(19年1月)：

我发现提供的解决方案在某些极端情况下不起作用。

一段时间后，我再次处理了这个问题，经过大量尝试，我发现如果您使用偏移坐标而不是轴向或立方体，则计算环绕六边形地图中的距离的问题变得微不足道。唯一需要注意的是，行数或列数(无论您决定进行偏移)都必须是偶数，以便地图正确换行。