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,
1 2 3 4 5 6 7 |
//Following is not a legal maze, it contains wall block and circle road. //***********| //********* *| //******* *| //****** * *| //******* *| //***********| |
A legal maze is something like,
1 2 3 4 5 6 |
// * * | // * | //** *| // ** | // * * *| // | |
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.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 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; } |