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

1. There are no circles in the maze, which means all roads in the maze lead to an dead end or to the exit.
2. 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.
//***********|
//********* *|
//*******   *|
//******  * *|
//*******   *|
//***********|
```

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:

1. if this cell is out of boundary, do not dig it, return to last step
3. 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)
4. else dig it. and move to this cell, jump to step 1.

Algorithm, a DFS approach:

``````map = [][] # initialize the map with full of walls
for each (i, j) cell in map:
DFS(i,j)

def DFS(i, j):
if i, j is out of boundary:
return
if (i,j) is visited:
return
if number of visited neighbors of (i, j) > 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:
void maze(vector<vector<char>>& map){
//U unvisited, ' ' visited
for (int i = 0; i < map.size(); ++i)
{
for (int j = 0; j < map.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.size(); ++j)
{
cout<<map[i][j];
}
cout<<endl;
}
}
//Use DFS
void _maze(vector<vector<char>>& map, int i, int j){
int direct[] = {{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.size()) return ;
#ifdef DEBUG
cout<<"("<<i<<", "<<j<<")"<<endl;
#endif
//visited, go back to 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]];
int nj = j + direct[visitOrder[k]];
_maze(map, ni, nj);
}
}

int countVisitedNeighbor(vector<vector<char>>& map, int i, int j){
int direct[] = {{1,0}, {-1,0}, {0,1}, {0,-1}};
int count = 0;
for (int k = 0; k < 4; ++k)
{
int ni = i + direct[k];
int nj = j + direct[k];
//out of boundary
if(ni < 0 || nj < 0 || ni >= map.size() || nj >= map.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;
}```

This site uses Akismet to reduce spam. Learn how your comment data is processed.