Hex Grid CalculateDistance

Unity Courses Show
,
#1

I did the conversion from square to hex grid before watching this bonus section, to challenge my understanding. This led me to a different CalculateDistance instead of the heuristic version in the course.
It’s based on the triangle/cone where a change in X doesn’t add to the distance, which widens for larger absolute values of Z. Integer division rounding down handles whether the destination GridPosition is on an odd or even row. I thought it was a fairly neat solution, so I thought I’d share it:

// in Pathfinding class
public int CalculateDistance(GridPosition gridPositionA, GridPosition gridPositionB)
{
    int zDistance = Mathf.Abs(gridPositionB.z - gridPositionA.z);
    int xDifference = gridPositionB.x - gridPositionA.x;
    int xDistance;

    // Starting row (z) is even
    if (gridPositionA.z % 2 == 0)
    {
        if (xDifference < 0)
        {
            xDistance = Mathf.Max(-xDifference - (zDistance + 1) / 2, 0);
        }
        else
        {
            xDistance = Mathf.Max(xDifference - zDistance / 2, 0);
        }
    }
    else // Starting row (z) is odd
    {
        if (xDifference < 0)
        {
            xDistance = Mathf.Max(-xDifference - zDistance / 2, 0);
        }
        else
        {
            xDistance = Mathf.Max(xDifference - (zDistance + 1) / 2, 0);
        }
    }
    return (zDistance + xDistance) * MOVE_COST;
}

I used similar code in the GridPosition class to get GridPositions in a range (including neighbors, range=1). It doesn’t check for validity, I handle that afterwards.

// in GridPosition class
public static List<GridPosition> GetGridPositionsInRange(GridPosition gridPosition, int range, bool includeSelf=true)
{
    List<GridPosition> gridPositionsInRange = new List<GridPosition>();

    bool startingRowOdd = gridPosition.z % 2 == 1;

    for (int z = 0; z <= range; z++)
    {
        int xMin = -(range - (z + (startingRowOdd ? 1 : 0)) / 2);
        int xMax = range - (z + (startingRowOdd ? 0 : 1)) / 2;

        for (int x = xMin; x <= xMax; x++)
        {
            if (!includeSelf && z == 0 && x == 0)
                continue;
                
            gridPositionsInRange.Add(new GridPosition(gridPosition.x + x, gridPosition.z + z));

            if (z == 0)
                continue;
                
            gridPositionsInRange.Add(new GridPosition(gridPosition.x + x, gridPosition.z - z));
        }
    }

    return gridPositionsInRange;
}
2 Likes
#2

That looks nice, good job!
Definitely make sure you test it on all kinds of scenarios. When I tried doing my heuristic I tried tons of approaches and always had weird edge cases where it suddenly stopped working.

1 Like
#3

I kinda solved it on a different way. I took a good look at an earlier link posted by CodeMonkey Hexagonal Grids

And I think I actually managed to implement it like stated on the site. The big epiphany was realizing that GridPosition is actually an implementation of Offset Coordinates. Once I realized this the conversion is easy. I made some helpers method on GridPosition to convert from and to Axial Hexes. And with this hexes you can now easily calculate ranges and distances and to other magical stuff.

In the GridSystem I have the following code: ( this used in all actions and in pathfinding to calculate a basic list of allowed gridpositions )

public List<GridPosition> GetGridPositionsInRange(GridPosition currentPosition, int range) {
        var results = new List<Hex>();
        for (int q = -range; q <= range; q++) {
            for (int r = Mathf.Max(-range, -q - range); r <= Mathf.Min(range, -q + range); r++) {
                results.Add(currentPosition.ToAxial() + new Hex(q, r));
            }
        }

        return results.Select(h => h.ToGridPosition()).Where(IsValidGridPosition).ToList();
    }

In GridPosition I have added the following:

 public Hex ToAxial() {
        var q = x - (z - (z % 2)) / 2;
        var r = z;
        return new Hex(q, r);
    }

And then the corresponding Hex and Cube classes:

public readonly struct Hex
{
    public Hex(int q, int r)
    {
        this.q = q;
        this.r = r;
    }

    public int q { get; }
    public int r { get; }

    public override string ToString() => $"Hex({q},{r})";

    public static Hex operator +(Hex a, Hex b) {
        return new Hex(a.q + b.q, a.r + b.r);
    }

    public GridPosition ToGridPosition() {
        var col = q + (r - (r % 1)) / 2;
        var row = r;
        return new GridPosition(col, row);
    }

    public int Distance(Hex b) {
        return ToCube().Distance(b.ToCube());
    }
    
    public Cube ToCube() {
        var s = -q - r;
        return new Cube(q, r, s);
    }
}

public readonly struct Cube
{
    public Cube(int q, int r, int s)
    {
        this.q = q;
        this.r = r;
        this.s = s;
    }

    public int q { get; }
    public int r { get; }
    public int s { get; }

    private static Cube Subtract(Cube a, Cube b) {
        return new Cube(a.q - b.q, a.r - b.r, a.s - b.s);
    }

    public int Distance(Cube b) {
        var vec = Subtract(this, b);
        return Mathf.Max(Mathf.Abs(vec.q), Mathf.Abs(vec.r), Mathf.Abs(vec.s));
    }

    public override string ToString() => $"Cube({q},{r},{s})";
}

Really loved it to solve this puzzle :grinning: and yes I copied a lot of code out of the site.

3 Likes

Privacy & Terms