Maze generation: making the grid

After a brief break I am back and decided to warm up with a bit of Maze Generation.

The maze in the GIF is being generated using a Recursive Backtracking Algorithm, also know as Flood Fill or Depth First Search. And will be the method we explore the coding of.

Objective: Generate a Random Maze from scratch.

Condition: A player or agent must be able to reach any point of the maze from any other point.

For this setup, I will be using a Plane for my surface, A cube for the ‘cells’ and another cube for the walls.

Here is the settings used for the Cell cube. Make sure that the position is set to Zero before making it your prefab.

And the settings for the Wall cube.

First thing we need to do is create the grid that we will make into a maze.

In this part of the code, we have a couple of variables that I need to define. _gridXSize and _gridZSize are fairly self explanatory, The Maze will be built on the X/Z plane, so I serialized these so that the designer can choose the size of the grid. _mazeParent is a empty GameObject that will hold the Maze and allow us to keep the Scene clean. It can be created on the fly or added by the designer.

If FillGridWithCells(), we use a nested For loop to create a clone of our Cell prefab in a position for each X,Z of the grid.

For the Walls, we have to do something a little different. We could create a wall at each direction around each cell in the grid, but then we will end up with doubled up walls. To avoid that, we will create walls along the Eastern(+X) side of the maze. Then again along the Northern(+Z) side of the maze. With the Southern and Western walls, we will use another nested For loop to create the pair for each Cell, this will fill in the Southern and Western Boundaries of the Maze as well as fill in the grid without over lap.

For the Surface placement, we need to do a bit of math to get sized and positioned correctly. First thing to note is that a Plane with a Scale of 1 will cover a 10 by 10 grid of Cubes at Scale 1. So when we figure out the scale (line 4 of the above code), we have to divide the result by 10. The +1 the I am using here is to create a bit of extra around the maze and is not strictly needed. But it does come in handy when you are dealing with mazes that are not even on both sides.

As for centering the plan under the the grid, You want to take half of the gird size for each axis to find the center point.

In the Next article we will look at what we need to do this grid to make a maze.