Spiral

It is common in tile based games to want to iterate all tiles in a non-linear fashion. Some times that appears as a spiraling technique so as to iterate all tiles in a performant way from some center location.

The general algorithm is to iterate tiles in a linear direction until a layer distance and then turn direction. Each time all four directions are turned we increase the depth of our layer. This creates a spiraling inspection of coordinates.

At the bottom you will find an improved Algorithm version in C.

Example Usage

In dungeon building we may want to place rooms in from some starting point to give the map a feel of centered-ness. We may just want to do a linear search for some object closest to our starting position.

This first block of code is a generalied routine in our dungeon builder that will iterate all cells in the tile map given a starting position and a lambda inspection routine.

void XoGeni::CellMap::inspectAllCellsInSpiral(const std::function<bool(Cell* cell)> &inspector)
{
    bit::Spiral spiral;

    // Starting point
    unsigned int centerX = width / 2 - 1;
    unsigned int centerY = height / 2 - 1;

    // Iterate cells
    for(unsigned int i=0; i < cells.size(); i++)
    {
        unsigned int currentX = centerX + spiral.x;
        unsigned int currentY = centerY + spiral.y;

        Cell* current = getCellAtPosition(currentX, currentY);
        bool complete = inspector(current);

        spiral.next();

        if(complete)
        {
            return;
        }
    }
}

This second block of code makes use of that generalized method to take a room's position and spiral outward creating more rooms to surround it.

XoGeni::Room* XoGeni::CellMap::buildRoom()
{
    unsigned int roomWidth = LevelGenerator::random.next(minRoomWidth, maxRoomWidth);
    unsigned int roomHeight = LevelGenerator::random.next(minRoomHeight, maxRoomHeight);

    Room* room = NULL;
    CellMap* cellMap = this;
    unsigned int i=0;

    inspectAllCellsInSpiral([roomWidth, roomHeight, cellMap, &room, &i] (Cell* cell) -> bool {

        if(i % cellMap->roomScatter == 0)
        {
            // Distribute according to room scatter distance
            if(cellMap->canHouseDimension(cell->x, cell->y, roomWidth, roomHeight))
            {
                // See if cells at this position within the room dimension are free
                bool canBePlaced = true;
                cellMap->inspectCellsInDimension(cell->x, cell->y, roomWidth, roomHeight, [&canBePlaced] (Cell* cell) -> bool {
                    if(cell->room != NULL || cell->isRoomPermiter)
                    {
                        canBePlaced = false;
                        return true; // break inspection loop
                    }
                    return false;
                });

                // If the cells are free then emplace the room
                if(canBePlaced)
                {
                    room = new Room(cell->x, cell->y, roomWidth, roomHeight);
                    cellMap->emplaceRoom(room);
                    return true;
                }
            }
        }

        i++;

        return false;
    });

    return room;
}

Implementation in C++

Here is our implementation class on how to perform a spiral calculation using coordinate mathematics.

Spiral.hpp

#pragma once
#ifndef BIT_SPIRAL_H
#define BIT_SPIRAL_H

namespace bit
{
    class Spiral
    {
    public:
        Spiral();
        int x, y;
        void next();

    protected:
        unsigned int layer;
        unsigned int leg;
    };
}

#endif

Spiral.cpp

#include "Spiral.hpp"

bit::Spiral::Spiral()
    : layer(1), leg(0), x(0), y(0)
{
}

void bit::Spiral::next()
{
    switch(leg)
    {
        // Step right
        case 0:
            ++x;
            if(x == layer)
            {
                ++leg;
            }
            break;

        // Step up
        case 1:
            ++y;
            if(y == layer)
            {
                ++leg;
            }
            break;

        // Step left
        case 2:
            --x;
            if(-x == layer)
            {
                ++leg;
            }
            break;

        // Step down
        case 3:
            --y;
            if(-y == layer)
            {
                leg = 0;
                ++layer;
            }
            break;
    }
}

Better version with C

I made improvements to this algorithm to optionally support maximum layers. This was helpful to prevent sprialing into tiles that were outside of a certain distance or bounds.

Header definition:

// SPIRAL
struct dm_spiral {
    int x, y;
    int leg, layer, maxlayers;
};
struct dm_spiral dm_spiral(int maxlayers);
bool dm_spiralnext(struct dm_spiral*);

Body:

///////////////////////////
// SPIRAL START

// this process steps right, down, left, up (and then right again)
// to form a spiral to the layer specified
// "leg" is what direction it is going
// it follows its leg until it hits the next layer edge
// "layer" is how expanded the legs will run
bool dm_spiralnext(struct dm_spiral *s)
{
    switch (s->leg) {
    // Step right
    case 0:
        ++s->x;
        // since stepping right finishes a layers circle we break if it has finished
        if (s->maxlayers > -1 && s->x > s->maxlayers)
            return false;
        if (s->x == s->layer)
            ++s->leg;
        break;
    // Step down
    case 1:
        ++s->y;
        if (s->y == s->layer)
            ++s->leg;
        break;
    // Step left
    case 2:
        --s->x;
        if (-s->x == s->layer)
            ++s->leg;
        break;
    // Step up
    case 3:
        --s->y;
        if (-s->y == s->layer) {
            s->leg = 0;
            ++s->layer;
        }
        break;
    }

    return true;
}

struct dm_spiral dm_spiral(int maxlayers)
{
    struct dm_spiral s = {
        0, 0, 0, 1, maxlayers
    };
    return s;
}

// SPIRAL END
///////////////////////////

Example usage spiraling out from the center of a room made of 2D tiles:

int center_x = room->x + room->width / 2;
int center_y = room->y + room->height / 2;
int layers = dm_maxi(room->width, room->height);
// define spiral struct with a maximum layers the width or height of the room
struct dm_spiral sp = dm_spiral(layers);
do {
    // get the current position, which is center of room plus spiral offsets
    int current_x = center_x + sp.x;
    int current_y = center_y + sp.y;
    // bounds check for tile
    if (!dng_cellmap_is_in_bounds(cellmap, current_x, current_y))
        return;
    // get tile at position to operate on
    struct dng_cell *current = dng_cellmap_get_cell_at_position(cellmap, current_x, current_y);
    if (current && inspect(current))
        return;
    // incremement to next tile in spiral
} while(dm_spiralnext(&sp));