Mazes are unpredictable parts of gameplay, if it is 2D you can see and create a path above. If you can see the whole maze above in 3D, you can do the same like rolling a ball in the maze. Especially, imagine a VR game you run through the maze to find an exit.
After delving into the realm of vertices on 3D primitive objects in Unity, I decided to take on a project to create a maze on a plane. The gird’s centers are the points on the plane and the borders are put accordingly around them. In this tutorial, I try to explain creating a 3D variable-sized maze using the points on a plane in Unity.
Maze Generation and Recursive Backtracking Algorithm
As I mentioned above, after having a plane and points on it ( finding points on a plane, the implementation used in this project), I started to wonder how to create a maze using them. With a quick “maze generation algorithms” on Google, I stumbled upon this great collection of maze generation algorithms written by Jamis Buck. There are about 11 algorithms and demos listed.
I took the short path and chose the author’s previously favorite maze generation algorithm, Recursive Backtracking algorithm. Here is the algorithm’s explanation in his blog. My implementation is highly parallel to Ruby implementation there. The biggest difference is moving directions of a cell. It is N, S, W, E there and Up, Down, Left, Right in my implementation.
Implementation of Recursive Backtracking Algorithm
The algorithm is implemented in RecursiveBacktracker class.
There are two types of grids in the RecursiveBacktracker class. Integer one is for creating the maze and Cell one is for showing the maze. There could be a maze showing class but since its functionality is simple, it was not created. Width and height variables are used to create integer grid.
A Cell object consists of the information about the borders it has and the center position of it.
There are numerous enum variables used in the development to ease conveying the meanings of actions.
First, we have a Direction enum which holds the bit values for each direction.
There is an Opposite enum, as the name suggests the values of the opposite directions are swapped.
DirectionX and DirectionY enums are for the grid index movement. For each direction they changes the index value accordingly. For example, for (x,y) to move up it is (x + 0 , y + (- 1)), to move left it is (x + (- 1), y + 0) in a list of list.
To get the same directions different value from the different enums there is value changing functions.
Getting The Maze Ready
The outer object could request a maze by providing a grid to GetNewMaze function of the algorithm. First grid bounds values are set, later the grids are initialized as defaults. Using CarvePassagesFrom the algorithm is implemented and Grid is set with the maze values. Values of CellGridis filled in FillMazeValues and it is returned to requestee class as a new maze.
Creating Default Grids
Grid is created as GridHeight * GridWidth matrix as well as CellGrid. Grid’s initial value is set 0 zero representing it was not visited previously and do not have any passages. CellGrid is initialized with the corresponding posit, on coordinates of the given grid to the algorithm.
Carving Passages From Coordinates
The algorithm starts with going a random direction from the current point. Since each direction should be visited the list is randomized. New coordinates are calculated using the direction’s axis values. If the new point was not visited previously, a passage is carved towards it. Since there is a passage towards the new cell, there is a passage on the opposite side for the new cell.
Passage carving represented bit-wise. For instance, the point has only a passage to left making cell value 8 (1000 bit-wise), down cell is checked and it was not visited previously. A passage is carved to down, 8(1000) | 2(0010) = 10 (1010) . The cell has a passage on both the downside and left side of it now. The new cell now has a passage to the upper side having value 0(0000) | 1(0001) = 1.
Values Filled With Maze
Here we do 3 things, fill up the borders of each cell, map representation in symbols(as explained in the original post on the algorithm) and creating a bitwise value representation of the map. I like to use the last one as a brain exercise. Used that one a lot for debugging the map shows.
First of all the borders are added for right and downsides. Because one cell’s downside border lower cell’s upside border. We prevent duplicates while adding borders. Since only right and down borders are added, left and up borders of the maze is added firstly in separate steps.
Bit-wise And(&) operation between a cell and the direction gives us if there is a passage in that direction or not. For (Grid[y][x] & (int)Direction.Down) == 0), let’s assume Grid[y][x] = 12 (1100), 12 & 1 (0010) = 0000. It says that there is no passage in the cell in the down direction, meaning there is a border there. Direction down is added to borders of the cell. The same thing is checked for the right direction of the cell.
As borders are added to CellGrid, representations are added to string variables. For no down border “ “, down border “_”, no left border “”, left border “|” is added. Each row starts with a new line. Values of cells too collected in a mapping string to show and debug the maze.
In this class the size of the maze is set, a maze is asked to the algorithm and the created maze is mapped to the game scene.
The borders are created by this class. BorderParent is the parent transform for all created borders.
Creating The Maze
First, any previously set variables cleaned out or set with new values. Then, grid with coordinates are created with the correct size, the size shown on the scene, maze requested and 3D maze shown on scene.
Creating The Grid
A Vector3 matrix is created to hold the position values of the points on the plane with the correct size. Filling the matrix starts from left, upmost point. The first index represents the y-axis and the second index represents the x-axis.
Showing Maze On The Game Scene
Two cubes are created to be the vertical and horizontal borders of each point in the maze. Then each cell is iterated through. If a cell’s borders include a border in the direction of up or down, the horizontal border is placed, otherwise, the vertical border is placed.
Each border has padding to leave space for the corridor around the point. If the direction is up it is moved in positive direction in the x-axis and if it is down it is moved in negative direction. If the direction is left the border is moved in positive direction in the z-axis and if it is down it is moved in negative direction.
Creating The Demo UI
There is a button on the screen to create a random maze each time pressed and two text elements to show the current maze’s width and height values. Button’s onClick event calls the MazeGenerator’s CreateNewMaze.
Update: Create Prefab Of The Random Maze In Editor Play Mode In Unity
While searching about maze generation, I had stumbled upon a Reddit comment claiming people create mazes but never shows how to save them. This comment prompted me to work on this and the below video tutorial was born from the results of the work.
You know a project can be a rabbit hole, like this one. There are a lot of ways this project can be improved. Such as:
- Increasing the grid limit bigger than 11 * 11,
- Applying rotation accordingly to the plane’s rotation,
- Resizing the maze,
- Creating downsized versions of a bigger maze, etc.
You can find the project here.
Originally published at http://sscriptiee.wordpress.com on August 16, 2019.