Nerd For Tech
Published in

Nerd For Tech

Maze Generation : Digging out the Walls

Maze being generated using a Recursive Back Tracking Algorithm

So, we have a grid of cells and just have to ‘dig’ out the maze. First, let’s get a solid grasp on what the algorithm is doing.

As you can see above, the ‘head’ of the Algorithm moves one step forward in a random direction. It continues to move forward until it can no longer move. At that point, it starts to move back along it’s path until it reaches a spot that it can move into a cell not along it’s path. This method guarantees that every cell is visited. But a potential down side is that we end up with long path ways that branch off with no overlapping paths. There will be only one way to solve this type of maze.

Let’s review what will need for our code. We will need a list of the cells in the current path(the red above), and we will need to be able to check if a has been visited yet.

Code for the individual Cells

Here we can use a small class to track Cell information. By attaching this to our Cell(cube) prefab, it will keep track of whether it has been visited or not. And as a bonus, when it is visited, we can turn off the renderer component.

Code for Checking for UnVisited Cells

Now moving onto the Maze Generation Class, let’s break into steps. First we have to check if a Cell has been visited. There are couple of ways of handling this, but this time I will look at using Colliders and Raycasts.

In this method, we use the current cell as the origin point of the raycast and a specific direction. The difference between using Raycast and RaycastAll is that RaycastAll will give you an array of all colliders the ray passes through instead of just the first one.

We then Use Foreach to run through the results, which should be two cells and a wall. By using TryGetComponent, we can eliminate the wall without getting a null reference while also getting a reference to the Cell Info class to test the _visited Bool.

By setting this up as a Return type of method instead of a void, we make the method usable in other cases.

Now we can use the VisitCheck() to check each of the directions around the current Cell. We are going to make this Method return a List of the Cells that we find that are unvisited, so first we have to initialize the a new list that we will use. Then we can Add to the List by making a call to the VistCheck() for each direction. Line 10 is to clean the Nulls out of the List. RemoveAll will check each item in the List against a condition and remove any matches. Here we are using a Lambda expression that translates to “IF item is null set it for removal.” RemoveAll also condenses the List as it runs through it leaving no gaps in the List, which is important if you want to iterate through the list.

Main code for generating a Maze

Now we are getting into the meat of the Generation code. Here we have a Coroutine that will run while there are Unvisted cells. I’ve tried to give my variables self explanatory names so we can walk through the code easily.

First thing we do is clear out the List of neighbors that is left over from the previous cell, Before calling NeighborhoodCast() to repopulate the list. Then if the List in not empty, we pick a random Cell and move to it with MovePathToCell(). If it is empty, that means we have hit a dead end and have to start moving back down our path. After Removing the current cell from the Path List, we trim the list to remove any Null left behind and make the new last cell in the List the current Cell. This will repeat until we reach a cell that has available neighbors to move into.

Code for Moving to Next Cell in Path.

MovePathToCell() is mostly simple ‘paper work’. We make the current Cell _lastCell and assign the cell that we are moving to as the _currentCell. We call Visit() on the new current Cell to mark it as visited. We reduce the Unvisted count and Add the current Cell to our path. Then we deal with the wall between the two cells.

Code for removing a Wall between tow cells.

When we want to remove a Wall, we call BreakWall() that does some simple 3D Math to get the direction that was traveled from one cell to the other. Then it uses the same style of RaycastAll used in the VisitCheck(). This time it checks for the WallInfo class. When it finds it, there is an Event triggered sending out the ID of the wall.

Code for WallInfo class

Looking at the WallInfo, we can see that it is subscribed to the Event that was just triggered by the BreakWall() of the Maze Generator. When the class on a wall gets the Event trigger, it checks itself against the Wall that has been targeted. If it matches, It destroys itself. If we were making a maze for in a game, we could use this method to replace the wall with another model, perhaps a archway or a door. But for this ‘prototype’ version, we will simply destroy it.

Code for starting the Maze Generation.

How do we start all this off you are starting to ask, Well that is simple. The GridGenerator class from my last article calls the BuildMaze().

We start with a modified version of the MovePathToCell() code to set the first cell for the Path. Here I hard code it to start at 0,0, But that can be easily set to anywhere in the grid. Then we start the Tunnel() coroutine.

And with a could last additions we can call this complete.

Code for setting up the Master Cell Array.

First let’s make two public methods for setting up the Master Cell array and Adding cells to it.

We can call SetCellArray() in the Start() of GridGenerator. Then we can call AddCellToArray when we instantiate each cell.

Maze Generation GIF

Now you have to all the pieces to make a simple maze generator for your next game or app.

--

--

--

NFT is an Educational Media House. Our mission is to bring the invaluable knowledge and experiences of experts from all over the world to the novice. To know more about us, visit https://www.nerdfortech.org/.

Recommended from Medium

Making The Enemy Shoot Backwards!

“It won’t work!”​ — How to respond when engineers say it can’t be done

How do I Grow a Business Using The Xamarin Mobile App?

Boilerplate in programming

DevTalk: Logstash Aggregations

Codesmith — Week Two… and some change

A Pattern for Analyzing API Responses with BigQuery

Relationships and Growing Pains

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store
Thomas Kesler

Thomas Kesler

A Unity Developer with a fondness for Fantasy games and the challenge of pushing boundaries.

More from Medium

What is Filebase and How do you use it?

The Fourth Player Challenge: Problem Solving and Jumping

Bug Fix on Model Flip

In 6 steps, Add a double jump in Unity