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,

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
  2. if this cell is already digged, do not dig it again, 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:

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.

 

Leave a Reply

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

  Subscribe  
Notify of