Let’s create a perfect maze generator

Before we get started with this tutorial you need to download and be familiar with the software I am going to use.

We’ll be using Unity 3D game engine to create this maze generator , so that you can use this system to create your own game. Click here to download it

We all know what a maze is “its is a network of paths and hedges designed as a puzzle through which one has to find a way.”(according our friend GOOGLE)

What we are going to create is a “Perfect maze“.

A perfect is a maze with no circular paths and there’s only one path from one point of the maze to other.

Here are some pictures to explain it.

This is not a perfect maze.

This is a perfect maze.

Programming a system the creates mazes for you is not very difficult and to make it easier we will be using the simplest algorithm “Depth first search”.

But before we get started with the algorithm , we need to set up our scene.

Create a closed grid filled with walls.

Each square in this grid is a cell and all the lines represent the walls of the cells.

Now we need to remember some information.

Which wall belong to which cell.

Is that cell has been visited by the system?.

Now to do this you can use data structures or simple classes.

here’s an example.

public class Cell {
public bool visited
public GameObject north;
public GameObject east;
public GameObject west;
public GameObject south;
public Cell (){
 north = null;
 east = null;
 west = null;
 south = null;
 }
}

Once you’ve assigned everything to the Cell classes you can continue with with algorithm.

Depth first search or (DFS)

Here’s how it works.

We will choose a random cell and mark it as visited
Look for a random neighbor cell you haven’t visited yet.
If you find one then remove or destroy the wall between the current cell and random neighbor then move in to that neighbor cell and mark it as visited.If you don’t find one then back up to the previous cell.
Repeat the 2 and 3 step until you’ve been to every cell.

Here’s the pseudo-code for the Depth first search or (DFS) algorithm.

create a array or list to hold a list of last visited cells
and call it lastCell,we will use it as a stack.
int totalCells = total number of cells present.
int currentCell = 0;
int visitedCells = 0; 

currentCell = choose a cell at random.
visitedCells++; increment the value of visitedCells

while visitedCells < totalCells 

    find all neighbors of currentCell which haven't visited yet.  
    if one or more found 
        choose one at random 
        destroy or remove the wall between it and currentCell 
        add currentCell location on the lastCell.
        make that random neighbor cell currentCell 
        visitedCells++ 
 else 
 get the most recent entry off the lastCell
 make it currentCell
     endIf 

endWhile

When the "while" loop terminates, the algorithm is completed.Because we’ve visited every cell we already know that no cell is inaccessible,This algorithm prevents the creation of the circular paths.

We can now put the start and the endpoint wherever we want.

Click here to see this system in action

You can also get this project on unity’s asset store :

Here’s the complete video series :

Blog

Let’s create a perfect maze generator

Depth first search or (DFS)

2 thoughts on “Let’s create a perfect maze generator”

Leave a Reply Cancel reply