Go back to Richel Bilderbeek's homepage.
Go back to Richel Bilderbeek's C++ page.
Maze code snippet to create a square maze. The
tool 'Maze Creater' demonstrates this
function.
* View a screenshot of 'Maze Creater',
showing a generated maze.
* View the code of 'CreateMaze' in plain text.
* Go to the page of 'Maze Creater'.
//From
http://www.richelbilderbeek.nl/CppCreateMaze.htm
const std::vector<std::vector<int>
> CreateMaze(const
int size)
{
//Size must be odd
assert( size % 2 == 1);
std::vector<std::vector<int> > maze(size, std::vector<int>(size,0));
//Draw outer walls
{
maze[0] [i ] = 1;
maze[size-1][i ] = 1;
maze[i] [0 ] = 1;
maze[i] [size-1] = 1;
}
//Draw pillars
for (int y=2;
y!=size-1; y+=2)
{
for (int x=2;
x!=size-1; x+=2)
{
maze[y][x] = 1;
}
}
//Check around pillars
const int nWallsToAdd
= ((size / 2) - 1) * ((size / 2) - 1);
for (int
i=0; i!=nWallsToAdd; )
{
for (int
y=2; y!=size-1; y+=2)
{
for (int
x=2; x!=size-1; x+=2)
{
= (maze[y-1][x] == 0 ? 0 : 1)
+ (maze[y+1][x] == 0 ? 0 : 1)
+ (maze[y][x+1] == 0 ? 0 : 1)
+ (maze[y][x-1] == 0 ? 0 : 1);
if ( nWalls == 0)
{
{
case 0: maze[y-1][x] =
1; break;
case 1: maze[y+1][x] =
1; break;
case 2: maze[y][x+1] =
1; break;
case 3: maze[y][x-1] =
1; break;
}
++i;
}
{
switch(std::rand() % 6)
{
case 0: std::swap(maze[y-1][x], maze[y+1][x]); break;
case 1: std::swap(maze[y-1][x], maze[y][x+1]); break;
case 2: std::swap(maze[y-1][x], maze[y][x-1]); break;
case 3: std::swap(maze[y+1][x], maze[y][x+1]); break;
case 4: std::swap(maze[y+1][x], maze[y][x-1]); break;
case 5: std::swap(maze[y][x+1], maze[y][x-1]); break;
}
}
}
}
}
return maze;
}
The
algorithm consists of the following parts:
1.
Preparation
2.
Calculating the number of walls to add
3.
Adding and moving walls
First,
the algorithm creates a square maze, with walls on the edges and pillars at regular
spacing in between. For a 7x7 maze this would yield the following maze (where
an X denotes a wall and . denotes a path):
XXXXXXX
X.....X
X.X.X.X
X.....X
X.X.X.X
X.....X
XXXXXXX
The
numbers of walls, N, to add to obtain a perfect maze of size s (that is: a
width of s and a height of s squares) is:
N(s) = (((s – 1) / 2) - 1) * (((s –
1) / 2) - 1)
For
a 7x7 maze, this values equals 4, which is equal to the number of pillars (note
that in the code a simpler function is used, because in int
division 7 divided by 2 equals 3).
All
pillars are visited. Around each pillar, the walls are counted. If there are zero
walls, one wall is added. If there is one wall, two randomly chosen spaces of
the four spaces adjacent to the pillar are swapped.
*
Wikipedia page
about maze creation algorithms
Go back to Richel Bilderbeek's C++ page.
Go back to Richel Bilderbeek's homepage.
