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

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