Random Maze Generator

random maze generator. 其实就是在⼀个⼆维空间画墙但不能允许有封闭空间

一亩三分地

维基百科 迷宫算法

• Graph theory based methods
  • Depth-first search
  • Recursive backtracker
  • Randomized Kruskal's algorithm
  • Randomized Prim's algorithm
• Recursive division method

Recursive backtracker

The depth-first search algorithm of maze generation is frequently implemented usingbacktracking:

1. Make the initial cell the current cell and mark it as visited
2. While there are unvisited cells
   1. If the current cell has any neighbours which have not been visited
      1. Choose randomly one of the unvisited neighbours
      2. Push the current cell to the stack
      3. Remove the wall between the current cell and the chosen cell
      4. Make the chosen cell the current cell and mark it as visited
   2. Else if stack is not empty
      1. Pop a cell from the stack
      2. Make it the current cell

• 首先找到任意一个没有被访问的cell
  • 查看其领域是否有没有被访问的cell
  • 在其中任意找一个cell，拆除他们的墙
  • 将新的cell作为当前cell，老cell入栈
• 如果当前cell领域都被访问过，则从stack pop一个作为当前cell
• 如果sta empty，则任意找到一个未被访问的cell

 class Solution
 {

 public:
     vector<vector<pair<int,int>>> makeMaze(int h, int w)
     {
         //0 not visited, 1
         vector<vector<bool>> visited(h, vector<bool>(w));

         vector<vector<pair<int, int>>> wall(h, vector<pair<int, int>>(w));

         stack<pair<int, int>> sta;

         bool find = false;

         do
         {
             find = false;
             for (int hi = 0; hi<h; hi++)
             {
                 for (int wi = 0; wi<w; wi++)
                 {
                     if (!visited[hi][wi])
                     {
                         find = true;
                         dfs(visited, sta, wall, hi, wi);
                     }
                 }
             }
         } while (find);

         return wall;
     }

     void dfs(vector<vector<bool>> &visited, stack<pair<int, int>> &sta, vector<vector<pair<int, int>>> &wall, int hi, int wi)
     {
         while (1)
         {
             vector<int> neighbor_unvisited;

             for (int i = 0; i<4; i++)
             {
                 if (hi + directions[i].first >= 0 && hi + directions[i].first<visited.size() &&
                     wi + directions[i].second >= 0 && wi + directions[i].second<visited[0].size()
                     && !visited[hi + directions[i].first][wi+directions[i].second])
                 {
                     neighbor_unvisited.push_back(i);
                 }
             }

             if (neighbor_unvisited.size()>0)
             {
                 int idx = neighbor_unvisited[rand() % neighbor_unvisited.size()];
                 sta.push(make_pair(hi, wi));

                 //break wall
                 if (idx == 0)//this is upper wall
                 {
                     wall[hi - 1][wi].second = 1;
                 }
                 else if (idx == 1)
                 {
                     wall[hi][wi].second = 1;
                 }
                 else if (idx == 2)
                 {
                     wall[hi][wi - 1].first = 1;
                 }
                 else
                 {
                     wall[hi][wi].first = 1;
                 }

                 visited[hi + directions[idx].first][wi + directions[idx].second] = true;

                 hi = hi + directions[idx].first;
                 wi = wi + directions[idx].second;
             }
             else if (!sta.empty())
             {
                 hi = sta.top().first;
                 wi = sta.top().second;
                 sta.pop();
             }
             else break;
         }
     }

     vector<pair<int, int>> directions = {
         { -1,0 },{ 1,0 },{ 0,-1 },{ 0,1 }
     };

 };

Randomized Kruskal's algorithm

This algorithm is a randomized version of Kruskal's algorithm. Create a list of all walls, and create a set for each cell, each containing just that one cell. For each wall, in some random order: If the cells divided by this wall belong to distinct sets: Remove the current wall. Join the sets of the formerly divided cells.

struct Wall
{
    int hi,wi;
    int direction;// 0 is right, 1 is down

    Wall(int _hi,int _wi,int d)
    {
        hi=_hi,wi=_wi,direction=d;
    }
}

vector<vector<pair<int,int>>> makeMaze(int h,int w)
{
    vector<Wall> walls;

    vector<vector<pair<int,int>>> node(h,vector<pair<int,int>>(w));
    vector<vector<int>> count(h,vector<int>(w,1));

    for(int hi=0;hi<h;hi++)
    {
        for(int wi=0;wi<w;wi++)
        {
            node[hi][wi]=make_pair(hi,wi);

            walls.push_back(Wall(hi,wi,0));
            walls.push_back(Wall(hi,wi,1));
        }
    }

    while(!walls.empty())
    {
        Wall wall=walls.back();

        if(wall.direction==0)
        {
            if(wall.wi!=w-1)
            {
                pair<int,int> left=getParent(wall.hi,wall.wi,node);
                pair<int,int> right=getParent(wall.hi,wall.wi+1,node);

                if(left!=right)
                {
                    if(count[left.first][left.second]>count[right.first][right.second])
                    {
                        count[left.first][left.second]+=count[right.first][right.second];
                        count[right.first][right.second]=0;
                        node[right.first][right.second]=make_pair(left.first,left.second);
                    }
                    else
                    {
                        count[right.first][right.second]+=count[left.first][left.second];
                        count[left.first][left.second]=0;
                        node[left.first][left.second]=make_pair(right.first,right.second);
                    }
                }
            }
        }
    }

    return walls;
}

pair<int,int> getParent(int hi,int wi,vector<vector<pair<int,int>>> &node)
{
    while(node[hi][wi]!=make_pair(hi,wi))
    {
        int phi=node[hi][wi].first;
        int pwi=node[hi][wi].second;
        hi=phi;
        wi=pwi;
    }
    return make_pair(hi,wi);
}
void randomWall(vector<Wall> &walls)
{
    for(int i=walls.size()--;i>0;i--)
    {
        int r=rand()%i;
        swap(walls[r],walls[i]);
    }
}

Recursive division method

建立迷宫竟然也能用Divide and conquer做！ 迷宫建立问题真是一个好问题！ Mazes can be created with recursive division, an algorithm which works as follows: Begin with the maze's space with no walls. Call this a chamber. Divide the chamber with a randomly positioned wall (or multiple walls) where each wall contains a randomly positioned passage opening within it. Then recursively repeat the process on the subchambers until all chambers are minimum sized. This method results in mazes with long straight walls crossing their space, making it easier to see which areas to avoid. For example, in a rectangular maze, build at random points two walls that are perpendicular to each other. These two walls divide the large chamber into four smaller chambers separated by four walls. Choose three of the four walls at random, and open a one cell-wide hole at a random point in each of the three. Continue in this manner recursively, until every chamber has a width of one cell in either of the two directions.

void buildMaze(vector<vector<int>> &vwalls,vector<vector<int>> &hwalls,int h,int w)
{
    vwalls=vector<vector<int>>(h,vector<int>(w));
    hwalls=vector<vector<int>>(h,vector<int>(w));

    helper(vwalls,hwalls,0,0,h-1,w-1);
}

void helper(vector<vector<int>> &vwalls,vector<vector<int>> &hwalls,int up,int left,int down,int right)
{
    if(up==down || left==right)return;

    int ranh=up+rand()%(down-up-1)+1;
    int ranw=left+rand()%(right-left-1)+1;

    //decide which not dig a hole
    int except=rand()%4;

    if(except!=0)
    {
        //vertical up line dig a hole
        int holeh=up+rand()%(ranh-up);
        vwalls[holeh][ranw]=1;
    }

    if(except!=1)
    {
        //vertical down line dig a hole
        int holeh=ranh+rand()%(down-ranh);
        vwalls[holeh][ranw]=1;
    }


    if(except!=2)
    {
        //vertical up line dig a hole
        int holew=left+rand()%(ranw-left);
        hwalls[ranh][holew]=1;
    }


    if(except!=3)
    {
        //vertical up line dig a hole
        int holew=ranw+rand()%(right-ranw);
        hwalls[holeh][holew]=1;
    }

    helper(vwalls,hwalls,up,left,ranh,ranw);
    helper(vwalls,hwalls,up,ranw+1,ranh,right);
    helper(vwalls,hwalls,ranh+1,left,down,ranw);
    helper(vwalls,hwalls,ranh+1,ranw+1,down,right);
}

错误的思路！！ BFS 解决迷宫问题 从左上角开始判定是路，向四周扩散，如果随机数是1，就认为是路。如果队列要空了，第四个认为一定是路，加到队列中。 不一定右下角是路。

 vector<vector<int>> randdomMaze(int h, int w)
 {
     vector<vector<int>> maze(h, vector<int>(w));

     queue<pair<int, int>> que;

     que.push(make_pair(0, 0));

     while (!que.empty())
     {
         pair<int, int> pos = que.front();
         que.pop();

         if (pos.first >= 1 && maze[pos.first - 1][pos.second] == 0)
         {
             int r = rand() % 2;
             if (r)
             {
                 maze[pos.first - 1][pos.second] = 1;
                 que.push(make_pair(pos.first - 1, pos.second));
             }
             else maze[pos.first - 1][pos.second] = -1;
         }


         if (pos.first<h - 1 && maze[pos.first + 1][pos.second] == 0)
         {
             int r = rand() % 2;
             if (r)
             {
                 maze[pos.first + 1][pos.second] = 1;
                 que.push(make_pair(pos.first + 1, pos.second));
             }
             else maze[pos.first + 1][pos.second] = -1;
         }


         if (pos.second>0 && maze[pos.first][pos.second - 1] == 0)
         {
             int r = rand() % 2;
             if (r)
             {
                 maze[pos.first][pos.second - 1] = 1;
                 que.push(make_pair(pos.first, pos.second - 1));
             }
             else maze[pos.first][pos.second - 1] = -1;
         }


         if (pos.second<w - 1 && maze[pos.first][pos.second + 1] == 0)
         {
             int r = rand() % 2;
             if (r || que.empty())
             {
                 maze[pos.first][pos.second + 1] = 1;
                 que.push(make_pair(pos.first , pos.second + 1));
             }
             else maze[pos.first][pos.second + 1] = -1;
         }
     }

    //打印迷宫
     for (int hi = 0; hi<h; hi++)
     {
         for (int wi = 0; wi<w; wi++)
         {
             if (maze[hi][wi] == 1)
                 cout << '0';
             else cout << '1';

             cout << '\t';
         }

         cout << endl;
     }
     return maze;
 }