Generating grid shell coordinates

Question

I need to generate grid shells for a given level. For example, the 2d grid "shell" at level 0 is just the cell (0,0). The level 1 shell would be every cell surrounding (0,0), the level 2 shell surrounds that one, etc.

The formula for the number of shells at each level is 8*level for each level above 0, and 1 cell for level 0.

The formula for the total number of shells is just the (number of side cells + 1) / 2

So, the output for level 1 would be the coordinates (in no particular order)

(-1,0)
(0,-1)
(1, 0)
(0, 1)
(1, 1)
(-1, 1)
(1, -1)
(-1,-1)

I'm struggling to come up with an algorithm to generate the coordinates at each level, despite knowing how many there should be, and what the coordinates are for each given level.

It would be even better if the coordinates for a given shell were ordered by distance from (0,0)

I'm also interested in how this would scale to 3d.

• Ewan: start by just doing one side, then the answer will become clear

Answer 1

For shell N:

• Start at (N,N)
• Move 2N cells in the direction (-1, 0); location is now (-N,N)
• Move 2N cells in the direction (0, -1); location is now (-N,-N)
• Move 2N cells in the direction (1, 0); location is now (N,-N)
• Move 2N-1 cells in the direction (0, 1); the last move would take you back to (N,N) but we don't want to double count that.

You can do all four sides in parallel if you want, or if you want them ordered by distance from the origin start half-way down each side (i.e. at (N,0), (0,N), (-N,0) and (0,-N)) and go out half distance in both directions from the starting points.

• xytor: This is a good solution. But I was wondering if it's possible to do this statelessly? So, given a level and an index, it would return that index's coordinate for that level. For example, given level 1 and index 2, it would return (1,0)
• Philip Kendall: The state here is so small you can recalculate things every time if you want to. Just work out where the ith move will end you up.
• xytor: That makes sense. I'm guessing for the 3d case, I would just nest the algorithm in another loop with a different direction?
• Philip Kendall: That's one way to do it; the 2D case is generating the 4 lines with one coordinate of ±N, the 3D case is generating the 6 planes with one coordinate of ±N, the 4D case is generating the 8 cubes with one coordinate of ±N, ... (and to go the other way, the 1D case is generating the 2 points with a coordinate of ±N)
• xytor: I just realized that a very inefficient solution is to just iterate through all the nodes inside of the shell, and only add the ones where i == min || i == max || j == min || j == max; where max is just the level, and min is -level.