Tuesday, October 6, 2015

Maze Generation Algorithm

Recently, I had to develop a game that required a random maze to be generated. The logic behind it is not that hard, but some people may have trouble trying to code it, so I decided I would blog about it.

This post is a how-to generate random labyrinths. Keep in mind there are a lot of algorithms and this is not the best neither the most optimized. In my opinion it is the simplest though.

Introduction


What you will need:

  • lab: an array to store the labyrinth (I'll be using a 2D array);
  • visitedCells: a secondary array to keep record of the visited cells;
  • guideCell: the coordinates of the head of the path;
  • pathHistory: a stack to keep a record of the path taken.

    How the algorithm works:

    • The guide cell starts next to the exit;
    • The guide cell advances to a random unvisited cell;
      • The guide cell keeps advancing until there are no unvisited cells around it;
      • When there are no unvisited cells around, the stack gets useful:
        • back trace to a point of the path where there is at least one unvisited cell and develop the algorithm from there;
    • The maze is completely finished when all cells have been visited.
      • An even easier way to know it is finished is when the stack gets empty.


    Restrictions:

    • The dimension of the maze needs to be an odd number.


    Detailed Algorithm Analysis


    Let's say we need to generate a 7x7 maze.

    The first step is to fill the 2D array with walls (I'll be using 'X' to display walls). After this we need to free the cells which have odd x and y coordinates, just like the picture below:


    And this is the base matrix where the algorithm will work. That's why the the maze needs to have an odd dimension.
    The next step would be randomly picking one free cell and marking it as the guideCell. After that, place an 'S' on the maze border to mark the exit:

    S: exit
    +: guideCell

    The next step is to create the visitedCells array to keep track of the cells which have been visited or not. This array will not be 7x7 but 3x3. The dimension of the visitedCells array is given by

    visitedCellsDimension = (labDimension - 1) / 2

    Here is the current state of the visitedCells array:

    .: unvisited cell
    +: visited cell

    Ok, by this time we have our lab array and our visitedCell ready. We just need to push the guideCell coords to the stack:


    Now that we have everything ready, let the algorithm start working! Yay! :D

    First we need to generate a random direction and check if that cell has already been visited. If not, the guide cell will advance to that direction.

    Assume that the computer randomly says: "guideCell, go down!". The cell below the guideCell current location has not yet been visited according to the visitedCells array, so this is what will happen:
    • the guideCell coords will be updated and pushed to the stack;
    • the visitedCells matrix will be updated:
      • a '+' will be marked at {2, 1};
    • the lab array will also be updated:
      • the 'X' on {5, 2} will be removed.
      This is how the containers look at this point:


      Ok let's speed up things a little bit. I hope you are catching up with me.

      Let's say the computer generated this directions randomly:
      • right;
      • up;
      • left;
      • down;
      • right.

      The 1st direction (right) will be ignored because the guide cell can not go right! That's the border of the maze!
      The 2nd direction generated (up) will also be ignored because according to the visitedCells, the cell above the guideCell has already been visited. Do you get it? :)
      The 3rd direction is a valid one though! The guideCell can indeed go left. So this is what will happen:


      The 4th direction generated was 'down':


      And finally, the 5th direction generated was 'right':


      Ok, by now you should have realized how the algorithm works.

      Notice what happens now:
      • If the computer generates right or down, the guideCell can not go there because that is the maze borders!
      • If the computer generates left or up, the guideCell can not go there as well because according to the visitedCells array, both cells in that direction have already been visited!
      It is a dead end! So, how do we finish generating the maze? It's not finished yet...

      Well, it's not that hard! This is why we have the stack with the history of the path we took!
      When we run into this problem we just need to back trace the stack and look for a cell that has at least one neighbor that has not yet been visited. When we do find this cell, it becomes our new guideCell.

      Let me use the example we have been working on to illustrate what I mean:
      The current guideCell has no unvisited cells as neighbors, so we need to remove it from the stack. And since we removed it, the top of the stack is {1, 2}, and this cell has at least one neighbor unvisited: This is our new guideCell.


      And since there is only one valid direction (left), the following algorithm iterations will be:





      And at this point, once again, we got to a dead end. What did we do when this happened before? That is right! We popped the stack until we found a cell that had at least one unvisited neighbor.

      This time though, we will pop the stack and won't find a cell that matches this condition. Why? Because all cells have been visited! You can check that by looking to the visitedCells array.
      The program will therefore be popping the stack and eventually empty it.

      And that concludes the algorithm: when the stack gets empty, all the cells have been visited and the maze generation was successfully completed! :)

      Here is an example of a 31x31 maze generated with this algorithm:


      I hope this helped you and was not too confusing... Cheers!
      Posted by at
      Labels:

      No comments:

      Post a Comment

      Subscribe to: Post Comments (Atom)