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
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
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.
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;
}