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

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

``` cpp
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`

``` cpp
#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`

``` 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:

```c
// 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:

```c
///////////////////////////
// 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:

```c
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));
```