# Finding cells within range on hexagonal grid

First up - I know I'm being super-dense here.

With that out of the way, I'm trying to write a C# implementation of this algorithm:

var results = []
for each -N ≤ dx ≤ N:
for each max(-N, -dx-N) ≤ dy ≤ min(N, -dx+N):
var dz = -dx-dy


I've taken this from this tremendous resource.

My problem is that every implementation of this I've tried so far has had crazy results. For example, the code shown below currently results in this: and this: My code currently sits like this:

for (int x = this.CellPositionX - distance; x <= this.CellPositionX + distance; x++)
{
for (int y = this.CellPositionY - Math.Max(-distance, -x - distance); y <= this.CellPositionY + Math.Min(distance, -x + distance); y++)
{
HexPosition rangePosition = new HexPosition(x, y);
}
}


Can anyone spot something awry here? All suggestions welcome. I've been banging my head on this one a while now.

Thanks!

Updated note: I am using Axial coordinates in the grid. Update #2: as pointed out below, I had my for..each loop wrong and wasn't using deltas for the working out. Thanks for the help!

I currently have an issue as shown below with the implementation from the answers: I'm going to keep investigating - if I figure it out I'll post the full results back here. Thanks all!

• Thanks for the that resource it looks really good! I was a little blown away when I realized almost all of the graphics were interactable. :) – Christer Feb 2 '16 at 22:53
• The example he gives uses cube coordinates, whereas it seems you're using either offset or axial coordinates. You need to convert the x,y,z from the cubic coordinates he has to whatever coordinate system you're using. – Alex Sherman Feb 2 '16 at 23:25
• @Vector57 I'm using Axial. From the conversion section there it's mentioned that I don't need to do anything with the Z property though and that q/r and x/y are interchangable... or have I misunderstood that? – aaron-bond Feb 3 '16 at 18:31
• It appears that way, although in the examples he uses r = z but I don't see why it should matter which you choose. – Alex Sherman Feb 3 '16 at 18:57

So upon further inspection your problem actually has nothing to do with coordinate system conversions. This could have been made more clear by not naming your axial coordinates X and Y but rather Q and R. The problem you're actually having is bad loop conditions. The original code sample produces delta q's and r's which you try to convert, in your for loops, to absolute coordinates and you made a mistake. The algorithm should look instead as follows:

for (int dx = -distance; dx <= distance; dx++)
{
for (int dy = Math.Max(-distance, -dx - distance); dy <= Math.Min(distance, -dx + distance); dy++)
{
HexPosition rangePosition = new HexPosition(
this.CellPositionX + dx, this.CellPositionY + dy);
}
}

• Oh derp... the article even mentions that they're delta values :( Gonna try this out now and see how it goes. Thanks :) – aaron-bond Feb 3 '16 at 19:04
• Thanks for this. It's definitely a lot closer to the right way of doing it. I'm still messing something up with the coordinates but at least I have the right number! For some reason I'm ending up with one cell too high on the -x and one too low on the +x. I've posted a pic up top if you know anything about it but I'll continue to investigate myself anyway :) thanks for your help! – aaron-bond Feb 3 '16 at 21:17
• Are you correctly interpreting the axial coordiantes? Remember that you chose to use x and y rather than x and z, so if the rest of your code doesn't account for this change from the examples it can result it weird behavior. – Alex Sherman Feb 3 '16 at 21:33
• Yep, I've switched so that it's x and z. dx becomes x and z = -dx - dy... – aaron-bond Feb 3 '16 at 21:40
• The new pic you posted shows 7 hexes highlighted. This is what you would expect with distance=1. Try printing out the values. With CellPosition set to 0,0 and distance 1, the hexes you get should be (-1, 0) ; (-1, 1) ; (0, -1) ; (0, 0) ; (0, 1) ; (1, -1) ; (1, 0) – amitp Feb 3 '16 at 21:43

As Vector57 noted, the problem is you are using the wrong coordinate system. The algorithm described is meant to be used with cube coordinates, which have x, y and z components: This may not be obvious from the algorithm's pseudocode, but that's because it's a simplification of this:

var results = []
for each -N ≤ dx ≤ N:
for each -N ≤ dy ≤ N:
for each -N ≤ dz ≤ N:
if dx + dy + dz = 0:


... a plain nested loop over x, y and z, what you'd expect from a range algorithm.

I don't know what coordinate system you are using, but I'm guessing it's one of the "offset coordinate" systems, which are popular because they are easy to implement by placing the grid cells inside a 2D array: This doesn't mean you can't use these cube algorithms; it just means you need to convert from the cube coordinates to your own. For example, to convert to/from the "odd-q" vertical layout, use these:

# convert cube to odd-q offset
col = x
row = z + (x - (x&1)) / 2

# convert odd-q offset to cube
x = col
z = row - (col - (col&1)) / 2
y = -x-z

• I had a feeling it was something like this. There was a part of that page that mentioned conversion from Cube to Axial and said to just remove the z portion and the remaining q and r become x and y. I think I must've over-simplified there. Thanks for this. Excellent explanation of what I was missing. I'll give it a go later! :) – aaron-bond Feb 3 '16 at 9:09
• I've just taken a look and I'm using axial. Surely since the algorithm has no mention of Z it's also a straight q = x and r = y system too? – aaron-bond Feb 3 '16 at 18:23