Computers can handle repetition. In fact, it is one of the things computers are exceptionally good at. As we discussed in Part 1, this ability is a core value that lets us add procedurally generated levels to our games – adding both variety and replayability.
In this tutorial, we’re going to be utilizing this “skill” computers have to make a recursive algorithm. From the last part, we’ve already built the base class with the necessary attributes and set up our Unity project. Now, we’re going to be actually building the algorithm from that base class which we can later use to generate a procedural maze. Recursive algorithms can be very powerful and useful (as you’ll see more in Part 3), and I hope you find this subject equally as intriguing as I do. If you’re ready to take the next step into the world of procedural generation, let’s jump into it!
Starter files
This tutorial is the second part of a series that began with this tutorial Part 1. If you’d like to start off exactly where we left off with that tutorial, you can download the source code here: Source Code.
BUILD GAMES
FINAL DAYS: Unlock 250+ coding courses, guided learning paths, help from expert mentors, and more.
An Overview of the Logic
Let’s have a look at our strategy for this project:
In this tutorial, we’re going to be working on the Algorithm Class. Recall that the base class looked like this:
using UnityEngine;
using System.Collections;
//<summary>
//Basic class for maze generation logic
//This is inherited by the recursive Maze Generator
//</summary>
public abstract class BasicMazeGenerator {
//Used to obtain the Row and Column from the private variables
public int RowCount{ get{ return mMazeRows; } }
public int ColumnCount { get { return mMazeColumns; } }
private int mMazeRows;
private int mMazeColumns;
private MazeCell[,] mMaze;
//A constructor that makes the rows and columns non-zero
//and instantiates a new MazeCell at that specific rank and range
public BasicMazeGenerator(int rows, int columns){
mMazeRows = Mathf.Abs(rows);
mMazeColumns = Mathf.Abs(columns);
if (mMazeRows == 0) {
mMazeRows = 1;
}
if (mMazeColumns == 0) {
mMazeColumns = 1;
}
mMaze = new MazeCell[rows,columns];
for (int row = 0; row < rows; row++) {
for(int column = 0; column < columns; column++){
mMaze[row,column] = new MazeCell();
}
}
}
//called by the algorithm class to start the algorithm
public abstract void GenerateMaze();
public MazeCell GetMazeCell(int row, int column){
if (row >= 0 && column >= 0 && row < mMazeRows && column < mMazeColumns) {
return mMaze[row,column];
}else{
Debug.Log(row+" "+column);
throw new System.ArgumentOutOfRangeException();
}
}
}Note on lines 32 to 36, a series of maze cells are instantiated. This is important. The cells are generated in the base class. However, it’s not until we get to the algorithm class that we actually get to do something to those cells. Recall that the “MazeCell” is simply a class with a direction and a series of booleans.
using UnityEngine;
using System.Collections;
public enum Direction{
Start,
Right,
Front,
Left,
Back,
};
public class MazeCell {
public bool IsVisited = false;
public bool WallRight = false;
public bool WallFront = false;
public bool WallLeft = false;
public bool WallBack = false;
public bool IsGoal = false;
}It’s pretty easy to see what the booleans do, they determine if the cell has been visited and the location of the walls around the cell. But what, specifically, is the “Direction” enumerator meant to do? This is used to determine where the open spaces are. Part of the logic in the algorithm class is determining a) how many open spaces a maze cell has and b) knowing where those are (i.e, in front, back, left, or right of the cell).
Given the sets of data we’re given in the base and MazeCell classes, what do we need to do to the algorithm class? We already know it has to be recursive, but what is the recursive algorithm going to look like? Well, we are going to need to do the following:
- Determine the number of open spaces on a maze cell
- Store that number
- Move to an open space
We’ve already discussed how to do that part. However, that description seems to be more like a strategy for solving a maze, not building one. What bits of logic can we use to build a maze? Well, we can approach it like this:
- Assume we start in a corner, not the center. This could be rank 0 and range 0 (i.e. the cell on the zeroth column and zeroth row).
- We know a corner has (at least) two walls and (at least) two open spaces.
- Since the cells have already been generated, we need to make sure we haven’t already visited a cell (i.e. !IsVisited).
- We know there are no cells outside of the maze, therefore, “IsVisited” would equal false on the edges (this bit of logic is what puts up the two corner walls)
- We know a corner has (at least) two open directions.
- We can then randomly pick from those open directions to determine where to move next.
- We can then put a wall in the open direction we didn’t go (i.e., if we have the left and right directions open and we randomly choose the left direction, why not put a wall in the right direction?)
- Once we have moved to that cell, we do another check to see where the open spaces are, and if it has been visited already.
- If we know the open spaces of a cell, we can just repeat all the steps starting at step 6.
Believe it or not, that is all the bits of logic we need. This is why I say the recursive method of maze generation, while not the most intuitive at times, is undoubtedly the most elegant. Just a few coding tricks and a bit of discrete math can generate a completely new maze for us.
Coding the Algorithm
Create a new C# script called “RecursiveMazeAlgorithm”
First off, we need to make sure this inherits from our “BasicMazeGenerator” class and not “MonoBehaviour”
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
}We need to initialize this class and tell it to get all its row and column data from the base class.
using System.Collections.Generic;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
}Now, you’ll probably notice the class name is underlined in red. This is because we need to implement the abstract method “GenerateMaze” that comes from the base class. Implement the “GenerateMaze” method and create a new method called “VisitCell” which is going to be called in “GenerateMaze.”
using System.Collections;
using System.Collections.Generic;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
public override void GenerateMaze()
{
VisitCell(0, 0, Direction.Start);
}
private void VisitCell (int row, int column, Direction moveMade)
{
}
}We’re mostly going to be using an integer value to store the number of available moves and we’ll use an array to store in which direction those possible moves are.
using System.Collections;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
public override void GenerateMaze()
{
VisitCell(0, 0, Direction.Start);
}
private void VisitCell (int row, int column, Direction moveMade)
{
Direction[] movesAvailable = new Direction[4];
int movesAvailableCount = 0;
}
}Most of the action in this class is going to take place within a do-while loop.
using System.Collections;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
public override void GenerateMaze()
{
VisitCell(0, 0, Direction.Start);
}
private void VisitCell (int row, int column, Direction moveMade)
{
Direction[] movesAvailable = new Direction[4];
int movesAvailableCount = 0;
do
{
} while (movesAvailableCount > 0);
}
}The condition for this loop is “movesAvailableCount” being greater than zero. This makes sense since we want to apply our logic for each available move. Also, if you’re not familiar with the difference between a do-while loop and a while loop, for our purposes, the main difference is that a do-while loop is guaranteed to be called at least once. This is very important for recursive functions since we’re going to be calling this “VisitCell” method from within itself.
Next, we need to work on the logic that will determine where an open space is and where a wall is. Since we’re working with cells that have already been made, we can use the “GetMazeCell” method we created on the base class. Also, since it’s a grid, think about moving left or right within the maze as incrementing the “row” and “column” variables. Therefore, to move right, we would increment the “column” variable by one (moving to the cell in the next column), and moving forward would be incrementing the “row” variable by one. It is a fairly intuitive way of moving through the maze but it’s worth mentioning since the code for the logic is going to look like this:
using System.Collections;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
public override void GenerateMaze()
{
VisitCell(0, 0, Direction.Start);
}
private void VisitCell (int row, int column, Direction moveMade)
{
Direction[] movesAvailable = new Direction[4];
int movesAvailableCount = 0;
do
{
movesAvailableCount = 0;
//check move right
if (column + 1 < ColumnCount && !GetMazeCell(row, column + 1).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Right;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Left)
{
GetMazeCell(row, column).WallRight = true;
}
//check move forward
if (row + 1 < RowCount && !GetMazeCell(row + 1, column).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Front;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Back)
{
GetMazeCell(row, column).WallFront = true;
}
//check move left
if (column > 0 && column - 1 >= 0 && !GetMazeCell(row, column - 1).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Left;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Right)
{
GetMazeCell(row, column).WallLeft = true;
}
//check move backward
if (row > 0 && row - 1 >= 0 && !GetMazeCell(row - 1, column).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Back;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Front)
{
GetMazeCell(row, column).WallBack = true;
}
GetMazeCell(row, column).IsVisited = true;
} while (movesAvailableCount > 0);
}
}It’s a dense bit of code (but not the densest we’ll be dealing with!) but I think it’s reasonably easy to understand the logic of what’s going on. An extremely important part to understand is the difference between an if-statement, an else-statement, and an if-else statement. We’re using if-else in this class which means the “else” condition will be evaluated only if the “if” statement is false. If it is true, the else-if statement doesn’t get checked at all. If it was an “if” statement it would be checked immediately after the previous “if” statement and if it was an “else” statement, the code inside would be executed if the the “if” statement was false (something we don’t want in this case). If you keep that in mind, it should be fairly easy to understand what’s going on here. Also note that once we’ve done all those checks, we mark the cell as being visited.
Now, we need to tell it where to go next. This is where we do the recursive part. The code looks like this:
using System.Collections;
using UnityEngine;
public class RecursiveMazeAlgorithm : BasicMazeGenerator
{
public RecursiveMazeAlgorithm(int rows, int columns) : base(rows, columns)
{
}
public override void GenerateMaze()
{
VisitCell(0, 0, Direction.Start);
}
private void VisitCell (int row, int column, Direction moveMade)
{
Direction[] movesAvailable = new Direction[4];
int movesAvailableCount = 0;
do
{
movesAvailableCount = 0;
//check move right
if (column + 1 < ColumnCount && !GetMazeCell(row, column + 1).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Right;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Left)
{
GetMazeCell(row, column).WallRight = true;
}
//check move forward
if (row + 1 < RowCount && !GetMazeCell(row + 1, column).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Front;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Back)
{
GetMazeCell(row, column).WallFront = true;
}
//check move left
if (column > 0 && column - 1 >= 0 && !GetMazeCell(row, column - 1).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Left;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Right)
{
GetMazeCell(row, column).WallLeft = true;
}
//check move backward
if (row > 0 && row - 1 >= 0 && !GetMazeCell(row - 1, column).IsVisited)
{
movesAvailable[movesAvailableCount] = Direction.Back;
movesAvailableCount++;
}
else if (!GetMazeCell(row, column).IsVisited && moveMade != Direction.Front)
{
GetMazeCell(row, column).WallBack = true;
}
GetMazeCell(row, column).IsVisited = true;
if (movesAvailableCount > 0)
{
switch (movesAvailable[Random.Range(0, movesAvailableCount)])
{
case Direction.Start:
break;
case Direction.Right:
VisitCell(row, column + 1, Direction.Right);
break;
case Direction.Front:
VisitCell(row + 1, column, Direction.Front);
break;
case Direction.Left:
VisitCell(row, column - 1, Direction.Left);
break;
case Direction.Back:
VisitCell(row - 1, column, Direction.Back);
break;
}
}
} while (movesAvailableCount > 0);
}
}A fairly simply switch-case that calls this “VisitCell” method from within itself. Note that we’re still upholding the method of navigation through the cells (i.e. incrementing the column by one moves right and incrementing the row by one moves forward). Also, note that we’re choosing a random direction by using “Random.range” and “movesAvailableCount.” Even though we’re not going to be able to see it (everything we’ve written still needs to go through the spawner class), you can add a couple of debug lines that will help you see how the logic works when the maze is spawned in.
for (int i = movesAvailableCount; i>0; i--)
{
Debug.Log("Maze Cell has " + movesAvailable[i] + " Open direction");
}
Conclusion
Congratulations – you’ve just built an algorithm to generate our maze! It was an intensive and elusive process, but through some solid foundations, you’ve seen how we can get it done. That being said, everything until this point has been fairly abstract in the sense that we haven’t done anything in the game world. This is tutorial ends this “era of abstraction.”
In the next tutorial, we’re going to be taking the cells and walls we’ve made and instantiate floors and “actual” walls. If you thought this tutorial was fun, we’re going to be doing even more fun things in the next lesson. The logic for spawning a maze is very similar to how we handled the algorithm class. In this sense, you are already familiar with the approach and so I can’t wait to see you there. Until then…
Keep making great games!
