How to Generate a Maze in C++

Generating maze is amazing! This algorithm is also widely used in lots of computer games.

Given a 2D array, generate a maze in it. There are several requirements of this maze:

There are no circles in the maze, which means all roads in the maze lead to an dead end or to the exit.
There are no wall blocks in the maze. Each wall is 1 unit in width, each road is also 1 unit in width.

For example,

//Following is not a legal maze, it contains wall block and circle road.
//***********|
//********* *|
//*******   *|
//******  * *|
//*******   *|
//***********|

//Following is not a legal maze, it contains wall block and circle road.

//***********|

//********* *|

//******* *|

//****** * *|

//******* *|

//***********|

A legal maze is something like,

// *  * |
//   *  |
//**   *|
//  **  |
// * * *|
//      |

// * * |

// * |

//** *|

// ** |

// * * *|

// |

There is a simple and clear way to solve this problem, less than 100 lines of code.

Imaging an area full of rocks (wall) and you are a miner digging path through it.

When you are standing at a cell, you first randomly pick up an adjacent cell (up, down, left, right), try to dig it. When return, try another adjacent cell randomly, until all the 4 directions are tried.

The strategy for digging it with coordinate (i, j) or not is as follows:

if this cell is out of boundary, do not dig it, return to last step
if this cell is already digged, do not dig it again, return to last step
if there are more than 1 of its 4 neighbor cells are digged, do not dig it, return to last step (since it will cause circles in path)
else dig it. and move to this cell, jump to step 1.

Algorithm, a DFS approach:

for each cell in map:

cell = ‘*’ #wall

DFS(0,0)

def DFS(i, j):

cell = map[i][j]

if i, j is out of boundary:

return

if cell is visited:

return

if number of visited neighbors of cells > 1:

return

mark cell as visited

for each neighbor (ni, nj) of cell(random order):

DFS(ni, nj)

C++ code is as follows. The complexity is O(n*n), n is the edge length of map.

#include "string"
#include "vector"
#include "unordered_map"
#include "queue"
#include "cstdlib"
#include "ctime"
#include <iostream>
#include "algorithm"
#include "stack"
using namespace std;
class Solution{
public:
// Definition for singly-linked list.
void maze(vector<vector<char>>& map){
//U unvisited, ' ' visited
for (int i = 0; i < map.size(); ++i)
{
for (int j = 0; j < map[0].size(); ++j)
{
map[i][j] = '*';
}
}
_maze(map, 0, 0);
}
void showMaze(vector<vector<char>>& map){
for (int i = 0; i < map.size(); ++i)
{
for (int j = 0; j < map[0].size(); ++j)
{
cout<<map[i][j];
}
cout<<endl;
}
}
//Use DFS
void _maze(vector<vector<char>>& map, int i, int j){
int direct[][2] = {{0,1}, {0,-1}, {-1,0}, {1,0}};
int visitOrder[] = {0,1,2,3};
//out of boundary
if(i < 0 || j < 0 || i >= map.size() || j >= map[0].size()) return ;
#ifdef DEBUG
cout<<"("<<i<<", "<<j<<")"<<endl;
#endif
//visited, go back the the coming direction, return 
if(map[i][j] == ' ') return ;
//some neightbors are visited in addition to the coming direction, return
//this is to avoid circles in maze
if(countVisitedNeighbor(map, i, j) > 1) return ;
map[i][j] = ' '; // visited
//shuffle the visitOrder
shuffle(visitOrder, 4);
for (int k = 0; k < 4; ++k)
{
int ni = i + direct[visitOrder[k]][0];
int nj = j + direct[visitOrder[k]][1];
_maze(map, ni, nj);
}
}
int countVisitedNeighbor(vector<vector<char>>& map, int i, int j){
int direct[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int count = 0;
for (int k = 0; k < 4; ++k)
{
int ni = i + direct[k][0];
int nj = j + direct[k][1];
//out of boundary
if(ni < 0 || nj < 0 || ni >= map.size() || nj >= map[0].size()) continue;
if(map[ni][nj] == ' ') count++;//visited
}
return count;
}
void shuffle(int a[], int n){
for (int i = 0; i < n; ++i)
{
swap(a[i], a[rand() % n]);
}
}
void swap(int & a, int &b){
int c = a;
a = b;
b = c;
}
};
int main(int argc, char const *argv[])
{
Solution s;
int height = 6;
int width = 6;
srand(time(0));
vector<char> row(width);
vector<vector<char>> map;
for (int i = 0; i < height; ++i)
{
map.push_back(row);
}
s.maze(map);
s.showMaze(map);
return 0;
}

100

101

102

103

104

105

106

#include "string"

#include "vector"

#include "unordered_map"

#include "queue"

#include "cstdlib"

#include "ctime"

#include <iostream>

#include "algorithm"

#include "stack"

using namespace std;

class Solution{

public:

// Definition for singly-linked list.

void maze(vector<vector<char>>& map){

//U unvisited, ' ' visited

for (int i = 0; i < map.size(); ++i)

{

for (int j = 0; j < map[0].size(); ++j)

{

map[i][j] = '*';

}

_maze(map, 0, 0);

}

void showMaze(vector<vector<char>>& map){

for (int i = 0; i < map.size(); ++i)

{

for (int j = 0; j < map[0].size(); ++j)

{

cout<<map[i][j];

}

cout<<endl;

}

//Use DFS

void _maze(vector<vector<char>>& map, int i, int j){

int direct[][2] = {{0,1}, {0,-1}, {-1,0}, {1,0}};

int visitOrder[] = {0,1,2,3};

//out of boundary

if(i < 0 || j < 0 || i >= map.size() || j >= map[0].size()) return ;

#ifdef DEBUG

cout<<"("<<i<<", "<<j<<")"<<endl;

#endif

//visited, go back the the coming direction, return

if(map[i][j] == ' ') return ;

//some neightbors are visited in addition to the coming direction, return

//this is to avoid circles in maze

if(countVisitedNeighbor(map, i, j) > 1) return ;

map[i][j] = ' '; // visited

//shuffle the visitOrder

shuffle(visitOrder, 4);

for (int k = 0; k < 4; ++k)

{

int ni = i + direct[visitOrder[k]][0];

int nj = j + direct[visitOrder[k]][1];

_maze(map, ni, nj);

}

int countVisitedNeighbor(vector<vector<char>>& map, int i, int j){

int direct[][2] = {{1,0}, {-1,0}, {0,1}, {0,-1}};

int count = 0;

for (int k = 0; k < 4; ++k)

{

int ni = i + direct[k][0];

int nj = j + direct[k][1];

//out of boundary

if(ni < 0 || nj < 0 || ni >= map.size() || nj >= map[0].size()) continue;

if(map[ni][nj] == ' ') count++;//visited

}

return count;

}

void shuffle(int a[], int n){

for (int i = 0; i < n; ++i)

{

swap(a[i], a[rand() % n]);

}

void swap(int & a, int &b){

int c = a;

a = b;

b = c;

}

};

int main(int argc, char const *argv[])

{

Solution s;

int height = 6;

int width = 6;

srand(time(0));

vector<char> row(width);

vector<vector<char>> map;

for (int i = 0; i < height; ++i)

{

map.push_back(row);

}

s.maze(map);

s.showMaze(map);

return 0;

}

Bo Song

How to Generate a Maze in C++

Leave a Reply