Finding cells within range on hexagonal grid

Question

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
    results.append(cube_add(center, Cube(dx, dy, dz)))

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);
            range.Add(rangePosition);
        }
    }

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!

Answer 1

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);
        range.Add(rangePosition);
    }
}

Answer 2

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:
                results.append(cube_add(center, Cube(dx, dy, dz)))

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