Spiral outwards on jagged 2D grid

Question

My question is very similar to these other questions:

On a two dimensional grid is there a formula I can use to spiral coordinates in an outward pattern?

However, what do you do if your grid/matrix is irregular?

I'm creating a game where there are certain 'seats', represented by a 2D grid. On every odd row, there's one less seat/cell. When rendered, those rows are offset by ½ seat. I need an algorithm that outputs the closest seats, relative to whatever seat-coordinate I input, in an descending order, like so (blue cell is the starting coordinate, semi-transparent cells are outside the grid) :

The seat grid is stored as a jagged, multidimensional array, so the previous visualization is a bit misguiding. From an "algorithmic" point of view, it actually looks more like this (again, blue cell is the starting coordinate, semi-transparent cells are outside the array bounds):

The output would be something like

[0,0][1,0][0,1][-1,1][-1,0][-1,-1][0,-1][1,-1][2,0][1,1]...

samgak · Accepted Answer · 2016-08-11T02:57:06.610

Here's an iterative approach that breaks the spiral into 7 sub-levels per loop of the spiral, one sub-level to move out from the previous spiral level and 6 sub-levels to trace a hexagonal path around the boundary of the previous level:

static void spiralLoop(int startx, int starty, int levels)
{
    int level = 1, sublevel = 0, sublevelstep = 0;
    int x = startx, y = starty;
    while(level <= levels)
    {
        System.out.println("["+x+","+y+"]");

        switch(sublevel)
        {
            case 0:
                x++; // stepping up from previous (next innermost) loop
                break;
            case 1:
                x+=(y&1);y++; // up and right
                break;
            case 2:
                x-=(~y&1);y++; // up and left
                break;
            case 3:
                x--; // left
                break;
            case 4:
                x-=(~y&1);y--; // down and left
                break;
            case 5:
                x+=(y&1);y--; // down and right
                break;
            case 6:
                x++; // right
                break;
            default:
                break;
        }

        if(sublevel == 0) // (3)
            sublevel = 1;
        if(++sublevelstep >= level) // (1)
        {
            sublevelstep = 0;
            if(++sublevel > 6) // (2)
            {
                level++;
                sublevel = 0;
            }
        }
    }
}

(1) The length of each hexagonal side (number of sub-level steps) is equal to the level (which starts from one). After each iteration the number of steps is incremented, and if it has reached the end of a sub-level the sub-level is incremented and steps are reset to 0.

(2) If the level has been completed (sub-level > 6) then the level is incremented and sub-level is reset to 0.

(3) The first sub-level of each level (moving up from the previous level) only lasts one iteration.

It doesn't do any checking for whether the current position is outside the grid, but that would be simple to add.

A start x,y position is passed in, and used to initialize x and y. These values are used to determine whether the current row is odd or even, which affects how the position is updated.

To move diagonally left, decrement x only when y is even. To move diagonally right, increment x only when y is odd. See below:

row 0:    0 1 2 3 4 5 6 7 8 9
row 1:     0 1 2 3 4 5 6 7 8
row 2:    0 1 2 3 4 5 6 7 8 9
row 3:     0 1 2 3 4 5 6 7 8
row 4:    0 1 2 3 4 5 6 7 8 9
row 5:     0 1 2 3 4 5 6 7 8

Spiral outwards on jagged 2D grid

1 Answers1