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

Question

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/computing-the-distance-better-points-in-points-in-wrap-around-toroidal-space/中概述的方法开始，但是当包装R时，我添加了“-math.floo(dC/2)”部分，以补偿网格在(+，+)---(-，-)对角线上的同化。