环绕式菱形六边形网格最短距离计算算法简化需求

Great question! Let's break down how to simplify your wrap-around hex grid distance calculation mathematically—no more checking four mirror origins.

Option 1: Simplify by Using Symmetric Wrapping (Best Performance) #

The root reason you need to check four mirrors is that your current wrapR/wrapC functions normalize distances to a [0, size) range. Instead, if you wrap distances to a symmetric range (e.g., for a grid of size N, wrap to [-floor(N/2), ceil(N/2)]), you eliminate the need to check mirror origins entirely. This works because the symmetric wrap already gives you the offset closest to (0,0), which corresponds to the shortest path.

Here's how to implement this:

public static Integer distance(HexCubeCoord origin, HexCubeCoord destination) {
    int dR = destination.getGridR() - origin.getGridR();
    int dC = destination.getGridC() - origin.getGridC();
    
    int rowCount = HexGridData.getRowCount();
    int colCount = HexGridData.getColCount();
    
    // Wrap to symmetric range (closest to 0)
    int wrappedR = wrapSymmetric(dR, rowCount);
    int wrappedC = wrapSymmetric(dC, colCount);
    
    int dZ = -wrappedR - wrappedC;
    return Math.max(Math.max(Math.abs(wrappedR), Math.abs(wrappedC)), Math.abs(dZ));
}

// Helper to wrap values to [-floor(size/2), ceil(size/2)]
private static int wrapSymmetric(int value, int size) {
    int wrapped = value % size;
    // Adjust for positive values over the midpoint
    if (wrapped > size / 2) {
        wrapped -= size;
    }
    // Adjust for negative values under the midpoint (handles negative mod behavior)
    else if (wrapped < -size / 2) {
        wrapped += size;
    }
    return wrapped;
}

For your example (0,0) to (4,2) with rowCount=5, colCount=3:

• dR=4 wraps to -1 (since 4 > 5/2 = 2.5, subtract 5)
• dC=2 wraps to -1 (since 2 > 3/2 = 1.5, subtract 3)
• Distance is max(|-1|, |-1|, |2|) = 2—correct, and calculated in one pass.

Option 2: Simplify Without Changing Wrapping Logic #

If you can't modify your existing wrapR/wrapC functions (which return [0, size)), you can still eliminate the redundant simpleDistance calls by simplifying the math behind the four mirror checks.

Your original four distance calculations can be reduced to four simple expressions (no more triple max calls):

• d0: Direct path (no wrap) → r + c (since r,c ≥0, max(r,c,r+c) = r+c)
• d1: Wrap only columns → max(r, colCount - c) (since |c - colCount| = colCount - c, and |r + c - colCount| ≤ max(r, colCount - c))
• d2: Wrap only rows → max(rowCount - r, c) (similar logic to d1)
• d3: Wrap both rows and columns → (rowCount - r) + (colCount - c) (since both terms are positive, max(...) equals their sum)

Here's the simplified code:

public static Integer distance(HexCubeCoord origin, HexCubeCoord destination) {
    int dR = destination.getGridR() - origin.getGridR();
    int dC = destination.getGridC() - origin.getGridC();
    
    int r = HexCalculator.wrapR(dR);
    int c = HexCalculator.wrapC(dC);
    
    int rowCount = HexGridData.getRowCount();
    int colCount = HexGridData.getColCount();
    
    int d0 = r + c;
    int d1 = Math.max(r, colCount - c);
    int d2 = Math.max(rowCount - r, c);
    int d3 = (rowCount - r) + (colCount - c);
    
    return Math.min(Math.min(d0, d1), Math.min(d2, d3));
}

This cuts down on redundant calculations while keeping your existing wrapping behavior. For your example, this computes min(6, 4, 2, 2) = 2—same correct result, with fewer operations.

Why This Works #

Hex grid distance (in cube coordinates) is equivalent to the Chebyshev distance: max(|x|, |y|, |z|) where z = -x - y. For wrap-around grids, we only care about offsets that bring us closest to (0,0)—either by using the wrapped offset directly (symmetric wrap) or checking the four possible combinations of wrapping rows/columns (non-symmetric wrap). Both options eliminate the need to instantiate extra HexCubeCoord objects and reduce the number of mathematical operations.

内容的提问来源于stack exchange，提问作者DToffe