Search code examples
c#algorithmhexagonal-tiles

Vertical Hex Grid: Get x rings of tiles surrounding a specific coordinate


Problem

What I am trying to do is get x numbers of rings from a specified point, and store those rings in a List<List<HexCoordinate>> where the inner list is a list of all the hexes in that ring and HexCoordinate is a structure defined below

Ideally, I would like to be able to specify the Coordinate, and how many rings out I would like to search and have the algorithm grab the tiles for me.

Images and Attempts

I have a Vertical (Flat Top) Hex Grid that looks like this Overall Hex Grid

In code, each tile is represented by a simple HexCoordinate structure GitHub

public struct HexCoordinate : IEquatable<HexCoordinate>
{
    public int X { get; private set; }
    public int Y { get; private set; }

    public HexCoordinate(int x, int y)
    {
        X = x;
        Y = y;
    }

    public HexCoordinate North() => this + new HexCoordinate(0, -1);
    public HexCoordinate South() => this + new HexCoordinate(0, 1);

    public HexCoordinate West() => this + new HexCoordinate(-1, 0);
    public HexCoordinate East() => this + new HexCoordinate(1, 0);

    public HexCoordinate NorthWest() => this + new HexCoordinate(-1, -1);
    public HexCoordinate NorthEast() => this + new HexCoordinate(1, -1);

    public HexCoordinate SouthWest() => this + new HexCoordinate(-1, 1);
    public HexCoordinate SouthEast() => this + new HexCoordinate(1, 1);

    public bool Equals(HexCoordinate other)
    {
        return X == other.X &&
               Y == other.Y;
    }
    public static HexCoordinate operator +(HexCoordinate one, HexCoordinate two)
    {
        return new HexCoordinate(one.X + two.X, one.Y + two.Y);
    }
}

For my example in particular, I have an image I have drawn out to try and figure this problem out myself Close Up Example

What I have Tried

And because I need to show what I have already tried, this is what I have tried so far

public const int MAX_RINGS = 3;
public List<List<HexCoordinate> GetsRingsWithinHex(HexCoordinate coordinate, int maxRings = MAX_RINGS)
{
    // Attempt One Pseudocode
    // reference: http://gamedev.stackexchange.com/questions/51264/get-ring-of-tiles-in-hexagon-grid
    // int ring = 1
    //   Travel around the ring by traversing N,SE,S,SW,NW,N,NE multiplied by the ring number
    //   ring++
    //      Travel Around ring again
    //      cont until desired ring...

    var hexRings = new List<List<HexCoordinate>>();

    // Add in the current hex to the list
    var currentHex = new List<HexCoordinate>(); 
    currentHex.add(coordinate);
    hexRings.Add(currentHex);

    // Now go through and add the other rings
    while (hexRings.Count <= maxRings)
    {
        var ring = new List<HexCoordinate>();
        HexCoordinate tempCoordinate = coordinate;
        int currentRingNumber = hexRings.Count;

        // We start off by going north to the correct ring, and then adding it to our list
        for (int i = 0; i < currentRingNumber; i++)
        {
            tempCoordinate = tempCoordinate.North();
        }
        ring.add(tempCoordinate);

        // After that, we proceed to go clockwise around the ring until we come back to the start
        for (int i = 0; i < currentRingNumber; i++)
        {
            tempCoordinate = tempCoordinate.SouthEast();

            // If the ring is an odd number, you need to re-align the coordinates back to where whey should be
            if (IntExtensions.IsOdd(i)) tempCoordinate = tempCoordinate.North();

            ring.add(tempCoordinate);
        }

        // The rightmost segment is east because we can go straight down the required number of times
        for (int i = 0; i < currentRingNumber; i++)
        {
            tempCoordinate = tempCoordinate.South();
            ring.add(tempCoordinate);
        }

        // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
        for (int i = 0; i < currentRingNumber - 1; i++)
        {
            tempCoordinate = tempCoordinate.SouthWest();
            ring.add(tempCoordinate);
        }

        // Coming into this statement, we are now at the bottom 3 coordinates.
        // Since our grid is laid out vertically, we can assume that these three hexes will be directly west of eachother
        // So we only have to go west twice to make our way to the next north segment 
        for (int i = 0; i < 2; i++)
        {
            tempCoordinate = tempCoordinate.West();
            ring.add(tempCoordinate);
        }

        // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
        for (int i = 0; i < currentRingNumber - 1; i++)
        {
            tempCoordinate = tempCoordinate.NorthWest();
            ring.add(tempCoordinate);
        }

        // The left most segment is easy because we can just go straight up
        for (int i = 0; i < currentRingNumber; i++)
        {
            tempCoordinate = tempCoordinate.North();
            ring.add(tempCoordinate);
        }

        // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
        for (int i = 0; i < currentRingNumber - 1; i++)
        {
            tempCoordinate = tempCoordinate.NorthEast();

            // If the ring is an even number, you need to re-align the coordinates back to where whey should be
            if (IntExtensions.IsEven(i)) tempCoordinate = tempCoordinate.South();

            ring.add(tempCoordinate);
        }

        // Finally, we add the ring to our system rings and loop until we no longer fit the criteria
        hexRings.Add(ring);
    }

    return hexRings;
}

And in case it is needed, here is my IntExtensions

public static class IntExtensions
{
    public static bool IsBetween(this int num, int low, int high)
    {
        return num >= low && num <= high;
    }

    public static bool IsOdd(this int value)
    {
        return value % 2 != 0;
    }

    public static bool IsEven(this int value)
    {
        return value % 2 == 0;
    }
}

My current problem is that this algorithm works for the 1st and 2nd rings, but once it gets to the third ring (and presumably further if I ran it past 3) the Coordinates along the bottom and corners start to become offset by 1... as can be seen by the output in my console below (with what it should be manually edited by hand)

Ring 0 - System 5, 5

Ring 1 - System 5, 4
Ring 1 - System 6, 5
Ring 1 - System 6, 6
Ring 1 - System 5, 6
Ring 1 - System 4, 6
Ring 1 - System 4, 5

Ring 2 - System 5, 3
Ring 2 - System 6, 4
Ring 2 - System 7, 4
Ring 2 - System 7, 5
Ring 2 - System 7, 6
Ring 2 - System 6, 7
Ring 2 - System 5, 7
Ring 2 - System 4, 7
Ring 2 - System 3, 6
Ring 2 - System 3, 5
Ring 2 - System 3, 4
Ring 2 - System 4, 4

Ring 3 - System 5, 2
Ring 3 - System 6, 3
Ring 3 - System 7, 3
Ring 3 - System 8, 4
Ring 3 - System 8, 5
Ring 3 - System 8, 6
Ring 3 - System 8, 7
Ring 3 - System 7, 8 //(Should be 7, 7)
Ring 3 - System 6, 9 //(Should be 6, 8)
Ring 3 - System 5, 9 //(Should be 5, 8)
Ring 3 - System 4, 9 //(Should be 4, 8)
Ring 3 - System 3, 8 //(Should be 3, 7)
Ring 3 - System 2, 7 
Ring 3 - System 2, 6
Ring 3 - System 2, 5
Ring 3 - System 2, 4
Ring 3 - System 3, 4 //(Should be 3, 3)
Ring 3 - System 4, 3

Would anybody be able to help put me in the right direction, or provide me with an algorithm that would allow me to get the rings of hexes? I have personally be stuck on this problem for about a day and a half now and I can't seem to figure this one out.


Solution

  • Alright, so I think I may have come up with a solution to my problem. I have tested it up to 4 rings and it is giving me all of the correct hexes in the corresponding rings.

    public List<List<HexCoordinate>> GetsRingsSurroundingHex(HexCoordinate coordinate, int maxRings)
        {
            // idea reference: http://gamedev.stackexchange.com/questions/51264/get-ring-of-tiles-in-hexagon-grid
            // int ring = 1
            //   Travel around the ring by traversing N,SE,S,SW,NW,N,NE multiplied by the ring number
            //   ring++
            //      Travel Around ring again
            //      cont until desired ring...
    
            var hexRings = new List<List<HexCoordinate>>();
    
            // Add in the current hex to the list
            var currentHex = new List<HexCoordinate>();
            currentHex.Add(coordinate);
            hexRings.Add(currentHex);
    
            // Now go through and add the other rings
            while (hexRings.Count <= maxRings)
            {
                var ring = new List<HexCoordinate>();
                HexCoordinate tempCoordinate = coordinate;
                int currentRingNumber = hexRings.Count;
    
                // We start off by going north to the correct ring, and then adding it to our list
                for (int i = 0; i < currentRingNumber; i++)
                {
                    tempCoordinate = tempCoordinate.North();
                }
                ring.Add(tempCoordinate);
    
                // After that, we proceed to go clockwise around the ring until we come back to the start
                for (int i = 0; i < currentRingNumber; i++)
                {
                    tempCoordinate = tempCoordinate.SouthEast();
    
                    // If the ring is an odd number, you need to re-align the coordinates back to where whey should be
                    if (IntExtensions.IsOdd(i)) tempCoordinate = tempCoordinate.North();
    
                    ring.Add(tempCoordinate);
                }
    
                // The rightmost segment is east because we can go straight down the required number of times
                for (int i = 0; i < currentRingNumber; i++)
                {
                    tempCoordinate = tempCoordinate.South();
                    ring.Add(tempCoordinate);
                }
    
                // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
                for (int i = 0; i < currentRingNumber - 1; i++)
                {
                    if (currentRingNumber.IsEven())
                    {
                        if (i.IsEven())
                            tempCoordinate = tempCoordinate.SouthWest();
                        else
                            tempCoordinate = tempCoordinate.West();
                    }
                    else
                    {
                        if (i.IsEven())
                            tempCoordinate = tempCoordinate.West();
                        else
                            tempCoordinate = tempCoordinate.SouthWest();
                    }
    
                    ring.Add(tempCoordinate);
                }
    
                // Coming into this statement, we are now at the bottom 3 coordinates.
                // Since our grid is laid out vertically, we can assume that these three hexes will be directly west of each other
                // So we only have to go west twice to make our way to the next north segment 
                for (int i = 0; i < 2; i++)
                {
                    tempCoordinate = tempCoordinate.West();
                    ring.Add(tempCoordinate);
                }
    
                // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
                for (int i = 0; i < currentRingNumber - 1; i++)
                {
                    if (i.IsEven())
                        tempCoordinate = tempCoordinate.NorthWest();
                    else
                        tempCoordinate = tempCoordinate.West();
    
                    ring.Add(tempCoordinate);
                }
    
                // The left most segment is easy because we can just go straight up
                for (int i = 0; i < currentRingNumber; i++)
                {
                    tempCoordinate = tempCoordinate.North();
                    ring.Add(tempCoordinate);
                }
    
                // We utilize Current Ring - 1 because we only want this to run on rings that are greater than 1
                for (int i = 0; i < currentRingNumber - 1; i++)
                {
                    if (currentRingNumber.IsEven())
                    {
                        if (i.IsEven())
                            tempCoordinate = tempCoordinate.East();
                        else
                            tempCoordinate = tempCoordinate.NorthEast();
                    }
                    else
                    {
                        if (i.IsEven())
                            tempCoordinate = tempCoordinate.NorthEast();
                        else
                            tempCoordinate = tempCoordinate.East();
                    }
    
                    ring.Add(tempCoordinate);
                }
    
                // Finally, we add the ring to our system rings and loop until we no longer fit the criteria
                hexRings.Add(ring);
            }
    
            return hexRings;
        }