Procedural Generation Of Mazes With Unity

Generating the Maze Data

Note that MazeConstructor.GenerateNewMaze() is currently empty; for now it's simply a stub to fill in later. In the GameController script, add the following line to the end of the Start() method. This will call that stub method:

    generator.GenerateNewMaze(13, 15);

The "magic" numbers 13 and 15 in the method's parameters dictate how large to make the maze. While they aren't being used quite yet, these size parameters determine the number of rows and columns in the grid respectively.

At this point you can start generating the data for the maze. Create a new script named MazeDataGenerator; this class will encapsulate the data generation logic, and will be used by MazeConstructor. Open the new script and replace everything with:

using System.Collections.Generic;
using UnityEngine;

public class MazeDataGenerator
{
    public float placementThreshold;    // chance of empty space

    public MazeDataGenerator()
    {
        placementThreshold = .1f;                               // 1
    }

    public int[,] FromDimensions(int sizeRows, int sizeCols)    // 2
    {
        int[,] maze = new int[sizeRows, sizeCols];
        // stub to fill in
        return maze;
    }
}

Note that this class doesn't inherit from MonoBehaviour. It won't be directly used as a component, only from within MazeConstructor, so it doesn't need MonoBehaviour's functionality.

Meanwhile:

1. placementThreshold will be used by the data generation algorithm to determine whether a space is empty. This variable is assigned a default value in the class constructor, but it's made public so that other code can tune the generated maze.
2. Once again, one method (FromDimensions() in this case) is currently simply a stub to call and will be filled in shortly.

Next add some sections of code to MazeConstructor to enable it to call the stub method. First add a private variable to store the data generator:

private MazeDataGenerator dataGenerator;

Then instantiate it in Awake(), storing the generator in the new variable by adding the following line to the top of the Awake() method.

    dataGenerator = new MazeDataGenerator();

Finally, call FromDimensions() in GenerateNewMaze(), passing along the grid size and storing the resulting data. Find the line containing // stub to fill in in GenerateNewMaze() and replace it with the following:

    if (sizeRows % 2 == 0 && sizeCols % 2 == 0)
    {
        Debug.LogError("Odd numbers work better for dungeon size.");
    }

    data = dataGenerator.FromDimensions(sizeRows, sizeCols);

Note the warning about odd numbers working better for size; that's because the generated maze will be surrounded by walls.

Play the game to see the correctly sized but otherwise empty maze data:

Great! Everything's in place to store and display the maze data! Time to implement the maze generation algorithm inside FromDimensions().

The algorithm described earlier iterates over every other space in the grid (no, not every single space!) to both place a wall and choose an adjacent space to block as well. The algorithm programmed here is a slight modification that also decides if the space should simply be skipped, resulting in open spaces to vary the maze. Since the algorithm doesn't need to store much, or know anything about the rest of the maze, such as a list of branch points to iterate over, the code becomes very simple.

To implement this maze generation algorithm, add the following code to FromDimensions() in MazeDataGenerator replacing the line that reads // stub to fill in.

    int rMax = maze.GetUpperBound(0);
    int cMax = maze.GetUpperBound(1);

    for (int i = 0; i <= rMax; i++)
    {
        for (int j = 0; j <= cMax; j++)
        {
            //1
            if (i == 0 || j == 0 || i == rMax || j == cMax)
            {
                maze[i, j] = 1;
            }

            //2
            else if (i % 2 == 0 && j % 2 == 0)
            {
                if (Random.value > placementThreshold)
                {
                    //3
                    maze[i, j] = 1;

                    int a = Random.value < .5 ? 0 : (Random.value < .5 ? -1 : 1);
                    int b = a != 0 ? 0 : (Random.value < .5 ? -1 : 1);
                    maze[i+a, j+b] = 1;
                }
            }
        }
    }

As you can see, the code gets the boundaries of the 2D array and then iterates through it:

1. For every grid cell, the code first checks if the current cell is on the outside of the grid (that is, if either index is on the array boundaries). If so, assign 1 for wall.
2. The code next checks if the coordinates are evenly divisible by 2 in order to operate on every other cell. There is a further check against the placementThreshold value described earlier, to randomly skip this cell and continue iterating through the array.
3. Finally, the code assigns 1 to both the current cell and a randomly chosen adjacent cell. The code uses a series of ternary operators to randomly add 0, 1, or -1 to the array index, thereby getting the index of an adjacent cell.

Display the maze data again in order to verify how the generated maze looks:

Restart the game to see that the maze data is different each time. Pretty cool!

The next big task is to generate a 3D mesh from the 2D maze data.

Generating the Maze Mesh

Now that the underlying data for the maze is being generated properly, you can construct the mesh based on that data.

Create another new script named MazeMeshGenerator. Much like MazeDataGenerator encapsulated the data generation logic, MazeMeshGenerator will contain the mesh generation logic and will be used by MazeConstructor to handle that step in generating the maze.

Or rather, it will eventually contain the mesh generation logic. First, you'll simply create a textured quad for demonstration purposes and then modify that code to generate the entire maze. In order to do that, you'll need to make a few minor adjustments within Unity's editor before diving into the code.

First, you need to link the materials that will be applied to the generated mesh.

Select the Graphics folder down in the Project window, then select Controller up in the Hierarchy window in order to see its Maze Constructor component in the Inspector.

Drag the materials from the Graphics folder over to the material slots in Maze Constructor. Use floor-mat for Material 1 and wall-mat for Material 2, while start and treasure go in the according slots.

Since you're already working in the Inspector, also add a tag called Generated: click on the Tag menu at the top of the Inspector and select Add Tag. When you generate meshes, you'll assign that tag in order to identify them.

Now that the needed adjustments have all been made in Unity's editor, open the new script and replace everything with:

using System.Collections.Generic;
using UnityEngine;

public class MazeMeshGenerator
{    
    // generator params
    public float width;     // how wide are hallways
    public float height;    // how tall are hallways

    public MazeMeshGenerator()
    {
        width = 3.75f;
        height = 3.5f;
    }

    public Mesh FromData(int[,] data)
    {
        Mesh maze = new Mesh();

        //1
        List<Vector3> newVertices = new List<Vector3>();
        List<Vector2> newUVs = new List<Vector2>();
        List<int> newTriangles = new List<int>();
        
        // corners of quad
        Vector3 vert1 = new Vector3(-.5f, -.5f, 0);
        Vector3 vert2 = new Vector3(-.5f, .5f, 0);
        Vector3 vert3 = new Vector3(.5f, .5f, 0);
        Vector3 vert4 = new Vector3(.5f, -.5f, 0);

        //2
        newVertices.Add(vert1);
        newVertices.Add(vert2);
        newVertices.Add(vert3);
        newVertices.Add(vert4);

        //3
        newUVs.Add(new Vector2(1, 0));
        newUVs.Add(new Vector2(1, 1));
        newUVs.Add(new Vector2(0, 1));
        newUVs.Add(new Vector2(0, 0));

        //4
        newTriangles.Add(2);
        newTriangles.Add(1);
        newTriangles.Add(0);

        //5
        newTriangles.Add(3);
        newTriangles.Add(2);
        newTriangles.Add(0);

        maze.vertices = newVertices.ToArray();
        maze.uv = newUVs.ToArray();
        maze.triangles = newTriangles.ToArray();

        return maze;
    }
}

The two fields at the top of the class, width and height, are just like placementThreshold from MazeDataGenerator: values, set with to default in the constructor, that are used by the mesh generation code.

The majority of the interesting code is inside FromData(); that's the method MazeConstructor calls to generate a mesh. At the moment the code just creates a single quad, in order to demonstrate how that works. You'll expand that to an entire level shortly.

This illustration shows what a quad is made of:

This code is long but fairly repetitive, with minor variations:

1. A mesh is comprised of three lists: the vertices, the UV coordinates and the triangles.
2. The list of vertices stores the position of each vertex...
3. The UV coordinates listed go with the corresponding vertex in that list...
4. And the triangles are indexes in the list of vertices (i.e. "this triangle is made from vertices 0, 1, and 2").
5. Note that two triangles were created; a quad is made of two triangles. Note also that List data types were used (in order to append to the list) but ultimately Mesh needs Arrays.

MazeConstructor needs to instantiate MazeMeshGenerator and then call the mesh generation method. Meanwhile it also needs to display the mesh, so here are the pieces of code to add:

First add a private field to store the mesh generator.

private MazeMeshGenerator meshGenerator;

Instantiate it in Awake(), storing the mesh generator in the new field by adding the following line to the top of the Awake() method:

    meshGenerator = new MazeMeshGenerator();

Next add the DisplayMaze() method:

private void DisplayMaze()
{
    GameObject go = new GameObject();
    go.transform.position = Vector3.zero;
    go.name = "Procedural Maze";
    go.tag = "Generated";

    MeshFilter mf = go.AddComponent<MeshFilter>();
    mf.mesh = meshGenerator.FromData(data);
    
    MeshCollider mc = go.AddComponent<MeshCollider>();
    mc.sharedMesh = mf.mesh;

    MeshRenderer mr = go.AddComponent<MeshRenderer>();
    mr.materials = new Material[2] {mazeMat1, mazeMat2};
}

Finally, in order to call DisplayMaze(), add the following line to the end of GenerateNewMaze():

    DisplayMaze();

By itself, a Mesh is simply data. It isn't visible until assigned to an object (more specifically, the object's MeshFilter) in the scene. Thus DisplayMaze() doesn't only call MazeMeshGenerator.FromData(), but rather inserts that call in the middle of instantiating a new GameObject, setting the Generated tag, adding MeshFilter and the generated mesh, adding MeshCollider for colliding with the maze, and finally adding MeshRenderer and materials.

Having programmed the MazeMeshGenerator class, and instantiated it in MazeConstructor, hit Play now:

You’ve built a textured quad completely from code! That's an exciting and important beginning, so pause here to review your work up to this point if you don't completely understand how it works.

Next up is a rather significant refactor of FromData(); replace it entirely with:

public Mesh FromData(int[,] data)
{
    Mesh maze = new Mesh();

    //3
    List<Vector3> newVertices = new List<Vector3>();
    List<Vector2> newUVs = new List<Vector2>();

    maze.subMeshCount = 2;
    List<int> floorTriangles = new List<int>();
    List<int> wallTriangles = new List<int>();

    int rMax = data.GetUpperBound(0);
    int cMax = data.GetUpperBound(1);
    float halfH = height * .5f;

    //4
    for (int i = 0; i <= rMax; i++)
    {
        for (int j = 0; j <= cMax; j++)
        {
            if (data[i, j] != 1)
            {
                // floor
                AddQuad(Matrix4x4.TRS(
                    new Vector3(j * width, 0, i * width),
                    Quaternion.LookRotation(Vector3.up),
                    new Vector3(width, width, 1)
                ), ref newVertices, ref newUVs, ref floorTriangles);

                // ceiling
                AddQuad(Matrix4x4.TRS(
                    new Vector3(j * width, height, i * width),
                    Quaternion.LookRotation(Vector3.down),
                    new Vector3(width, width, 1)
                ), ref newVertices, ref newUVs, ref floorTriangles);


                // walls on sides next to blocked grid cells

                if (i - 1 < 0 || data[i-1, j] == 1)
                {
                    AddQuad(Matrix4x4.TRS(
                        new Vector3(j * width, halfH, (i-.5f) * width),
                        Quaternion.LookRotation(Vector3.forward),
                        new Vector3(width, height, 1)
                    ), ref newVertices, ref newUVs, ref wallTriangles);
                }

                if (j + 1 > cMax || data[i, j+1] == 1)
                {
                    AddQuad(Matrix4x4.TRS(
                        new Vector3((j+.5f) * width, halfH, i * width),
                        Quaternion.LookRotation(Vector3.left),
                        new Vector3(width, height, 1)
                    ), ref newVertices, ref newUVs, ref wallTriangles);
                }

                if (j - 1 < 0 || data[i, j-1] == 1)
                {
                    AddQuad(Matrix4x4.TRS(
                        new Vector3((j-.5f) * width, halfH, i * width),
                        Quaternion.LookRotation(Vector3.right),
                        new Vector3(width, height, 1)
                    ), ref newVertices, ref newUVs, ref wallTriangles);
                }

                if (i + 1 > rMax || data[i+1, j] == 1)
                {
                    AddQuad(Matrix4x4.TRS(
                        new Vector3(j * width, halfH, (i+.5f) * width),
                        Quaternion.LookRotation(Vector3.back),
                        new Vector3(width, height, 1)
                    ), ref newVertices, ref newUVs, ref wallTriangles);
                }
            }
        }
    }

    maze.vertices = newVertices.ToArray();
    maze.uv = newUVs.ToArray();
    
    maze.SetTriangles(floorTriangles.ToArray(), 0);
    maze.SetTriangles(wallTriangles.ToArray(), 1);

    //5
    maze.RecalculateNormals();

    return maze;
}

//1, 2
private void AddQuad(Matrix4x4 matrix, ref List<Vector3> newVertices,
    ref List<Vector2> newUVs, ref List<int> newTriangles)
{
    int index = newVertices.Count;

    // corners before transforming
    Vector3 vert1 = new Vector3(-.5f, -.5f, 0);
    Vector3 vert2 = new Vector3(-.5f, .5f, 0);
    Vector3 vert3 = new Vector3(.5f, .5f, 0);
    Vector3 vert4 = new Vector3(.5f, -.5f, 0);

    newVertices.Add(matrix.MultiplyPoint3x4(vert1));
    newVertices.Add(matrix.MultiplyPoint3x4(vert2));
    newVertices.Add(matrix.MultiplyPoint3x4(vert3));
    newVertices.Add(matrix.MultiplyPoint3x4(vert4));

    newUVs.Add(new Vector2(1, 0));
    newUVs.Add(new Vector2(1, 1));
    newUVs.Add(new Vector2(0, 1));
    newUVs.Add(new Vector2(0, 0));

    newTriangles.Add(index+2);
    newTriangles.Add(index+1);
    newTriangles.Add(index);

    newTriangles.Add(index+3);
    newTriangles.Add(index+2);
    newTriangles.Add(index);
}

Whew — that last batch of code was long! But again, it’s pretty much the same thing over and over with a few numbers changed. In particular, the code to generate a quad was moved into a separate AddQuad() method in order to call that repeatedly for the floor, ceiling, and walls of each grid cell.

1. The final three parameters to AddQuad() are the same list of vertices, UVs, and triangles to append to. Meanwhile, the first line of the method gets the index to start from; as more quads are appended, the index will increase.
2. However, the first AddQuad() parameter is a transformation matrix, and that part may be confusing. Essentially, a position/rotation/scale can be stored in a matrix, and then applied to the vertices. That's what the MultiplyPoint3x4() calls are doing. That way, the exact same code to generate a quad can be used for floors, walls, etc. You only need to vary the transformation matrix being used!
3. Going back to FromData(), lists for vertices, UVs, and triangles are created at the top. This time, there are two lists of triangles. Unity's Mesh object can have multiple sub-meshes with a different material on each, so each list of triangles is a different sub-mesh. You declare two sub-meshes so that you can assign different materials to the floor and walls.
4. After that, you iterate through the 2D array and build quads for floor, ceiling, and walls at every grid cell. While every cell needs a floor and ceiling, there are checks of adjacent cells to see which walls are needed. Note how AddQuad() is being called repeatedly, but with a different transform matrix each time, and with different triangle lists used for floors and walls. Also note that width and height are used to determine where quads are positioned and how big they are.
5. Oh and one other subtle addition: RecalculateNormals() prepares the mesh for lighting.

Press Play to see the full maze mesh generated:

Congratulations; that was the entirety of maze generation, and the majority of the programming needed for Speedy Treasure Thief! You'll wrap up the rest of the game in the next section.