How I implemented procedural maze generation in my game
Hello! My name is Denis, I develop games on Unity and today I would like to tell you about how maze generation works in the game that is currently in development.
This is not a commercial project (although there are plans to release the game on Google Play), but my personal one, so at the end of the article you will find a tech demo.
I would like to say right away that I do not consider myself an expert in game development in general and on the Unity engine in particular, some points may seem controversial and not optimal to you, but I still want to share my experience and am ready to answer your questions and take criticism into account.
Create a labyrinth map
I chose recursive backtracker as the generation algorithm, because it is quite easy to understand and at the same time creates complex mazes with long dead ends. It can also be used with any maze shape, not just orthogonal. If you want to study everything related to mazes and their generation in more detail, I recommend reading this article.
Before describing the algorithm's operation, several preliminary steps must be taken. The algorithm generates a map on the basis of which we will build the labyrinth. The map consists of cells connected to each other. The labyrinth map can be represented as a graph, where its vertices are cells, and its edges are connections between cells. Let's start with cells:
using UnityEngine;
public class Cell {
public bool inMaze;
public Vector2Int Position { get; set; }
private Cell UpperCell { get; set; }
private Cell LowerCell { get; set; }
private Cell RightCell { get; set; }
private Cell LeftCell { get; set; }
}Each cell can potentially be connected to 4 neighboring cells – above, below, right and left. At the code level, a connection is simply a reference to another cell. Field inMaze is used to check the presence of a cell in a graph, and by the property Position we can find the cell on the map. Now let's add the map:
using UnityEngine;
public class Map {
public Vector2Int Size { get; }
private readonly Cell[,] cells;
public Map (Vector2Int size) {
Size = size;
cells = new Cell[size.x, size.y];
for (var x = 0; x < size.x; x++) {
for (var y = 0; y < size.y; y++) {
cells[x, y] = new Cell {
Position = new Vector2Int(x, y)
};
}
}
}
}As you can see, the map contains the size Size and a two-dimensional array cellsIn the constructor we initialize the array and fill it with cells, indicating their positions.
Now it is worth telling directly about the operation of the recursive backtracker algorithm. In short, the execution steps can be described as follows:
We randomly select a cell from the map and make it part of the labyrinth (
cell.inMaze = true;).Among the neighboring cells (there are 4 in total), we randomly select one that is within the map, but is not yet part of the labyrinth.
If we did not select any cell in step 2, the algorithm returns to the previously selected cell; otherwise, we connect both cells, make the selected cell part of the labyrinth, and go to step 2. If we have reached the cell selected in step 1 (and therefore have no cells left to select), the algorithm stops working.
Now we need to encode all of this somehow. Let's start by creating a map generator:
using UnityEngine;
public class MapGenerator {
public Map GenerateMap (Vector2Int size, int seed) {
var map = new Map(size);
var random = new Random(seed);
Cell cell = map.GetRandomCell(random);
cell.inMaze = true;
MoveNext(cell, map, random);
return map;
}
}In the method GenerateMap() all 3 steps of the algorithm have already been implemented – the first in the method GetRandomCell() class Map and the second and third in the method MoveNext()which is executed recursively (hence the name of the algorithm). I will use the system Random with a given value seed to control map generation. Yes, as you may have noticed, both methods GetRandomCell() And MoveNext() not implemented yet, so let's fix that:
public Cell GetRandomCell (Random random) {
return this[random.Next(0, Size.x), random.Next(0, Size.y)];
}Here we take a cell from the array through the indexer at random x And y coordinates. We implement the indexer:
public Cell this [int x, int y] {
get {
if (x < 0 || Size.x <= x) {
throw new ArgumentOutOfRangeException(nameof(x), x,
"Argument was outside of bounds of the map"
);
}
if (y < 0 || Size.y <= y) {
throw new ArgumentOutOfRangeException(nameof(y), y,
"Argument was outside of bounds of the map"
);
}
return cells[x, y];
}
}
public Cell this [Vector2Int position] => this[position.x, position.y];In the indexer, we check the input vector that it does not go beyond the map, and simply return the cell from the array by its position. The indexer has 2 overloads – the first will be convenient to use when going through the entire map in cycles, and the second will be more convenient to use in the method MoveNext().
Now let's get back to the algorithm. We've already completed step 1, taking a random cell from the map. Now we need its neighbors. We can take neighbors from the map via the indexer, for this we just need to calculate their positions:
private void MoveNext (Cell cell, Map map, Random random) {
int x = cell.Position.x;
int y = cell.Position.y;
var upperPosition = new Vector2Int(x, y - 1);
var lowerPosition = new Vector2Int(x, y + 1);
var leftPosition = new Vector2Int(x - 1, y);
var rightPosition = new Vector2Int(x + 1, y);
}The positions in the map start from the top left corner, so to go up one cell we need to subtract one from y. Actually, this is not a mandatory rule, you could implement it differently, counting the map from the bottom left corner, it's just a matter of convenience.
Next, we need to determine what neighbors the cell has and whether they are part of the labyrinth. We will distinguish neighbors by which side they are located relative to cellFor this purpose we implement enum in class Cell and let's call it Side:
public class Cell {
/* ... */
public enum Side {
Top,
Bottom,
Left,
Right
}
}Then we implement the method CheckBounds() in class Map to check if a position is outside the map boundaries:
public bool CheckBounds (Vector2Int position) {
return position.x >= 0 && position.x < Size.x && position.y >= 0 && position.y < Size.y;
}Overall result trueif the position is within the map.
Now we select neighbors:
private void MoveNext (Cell cell, Map map, Random random) {
/* ... */
var sides = new List<Cell.Side>();
if (map.CheckBounds(upperPosition) && !map[upperPosition].inMaze)
sides.Add(Cell.Side.Top);
if (map.CheckBounds(lowerPosition) && !map[lowerPosition].inMaze)
sides.Add(Cell.Side.Bottom);
if (map.CheckBounds(leftPosition) && !map[leftPosition].inMaze)
sides.Add(Cell.Side.Left);
if (map.CheckBounds(rightPosition) && !map[rightPosition].inMaze)
sides.Add(Cell.Side.Right);
}If a cell has no available neighbors, we stop the algorithm:
private void MoveNext (Cell cell, Map map, Random random) {
/* ... */
var sides = new List<Cell.Side>();
/* ... */
if (sides.Count == 0)
return;
}All that remains for us is to select a random cell from the existing ones, connect the current cell with the selected one and move on to the next step. To connect the cells, we implement 4 methods in the class Cell:
public void ConnectUpperCell (Cell upperCell) {
UpperCell = upperCell;
upperCell.LowerCell = this;
upperCell.inMaze = true;
}
public void ConnectLowerCell (Cell lowerCell) {
LowerCell = lowerCell;
lowerCell.UpperCell = this;
lowerCell.inMaze = true;
}
public void ConnectRightCell (Cell rightCell) {
RightCell = rightCell;
rightCell.LeftCell = this;
rightCell.inMaze = true;
}
public void ConnectLeftCell (Cell leftCell) {
LeftCell = leftCell;
leftCell.RightCell = this;
leftCell.inMaze = true;
}Once connected, the cells should automatically become part of the maze. In addition, both cells are considered connected if they both refer to each other. This will prevent errors later.
Now let's get back to MoveNext() (remember that we need to choose a random cell, connect it to the current one and move on to the next step):
Cell.Side side = sides[random.Next(0, sides.Count)];
switch (side) {
case Cell.Side.Top:
Cell upperCell = map[upperPosition];
cell.ConnectUpperCell(upperCell);
MoveNext(upperCell, map, random); // <- здесь мы переходим к следующему шагу, рекурсивно вызывая метод
break;
case Cell.Side.Bottom:
Cell lowerCell = map[lowerPosition];
cell.ConnectLowerCell(lowerCell);
MoveNext(lowerCell, map, random); // <- здесь мы переходим к следующему шагу, рекурсивно вызывая метод
break;
case Cell.Side.Left:
Cell leftCell = map[leftPosition];
cell.ConnectLeftCell(leftCell);
MoveNext(leftCell, map, random); // <- здесь мы переходим к следующему шагу, рекурсивно вызывая метод
break;
case Cell.Side.Right:
Cell rightCell = map[rightPosition];
cell.ConnectRightCell(rightCell);
MoveNext(rightCell, map, random); // <- здесь мы переходим к следующему шагу, рекурсивно вызывая метод
break;
default:
throw new ArgumentOutOfRangeException();
}
sides.Clear(); // в конце очищаем список, т.к. он будет использоваться повторно при выходе из рекурсивного вызоваAnd let's not forget to wrap all this in a cycle. As a result, we get the following method:
MoveNext()
private void MoveNext (Cell cell, Map map, Random random) {
int x = cell.Position.x;
int y = cell.Position.y;
var upperPosition = new Vector2Int(x, y - 1);
var lowerPosition = new Vector2Int(x, y + 1);
var leftPosition = new Vector2Int(x - 1, y);
var rightPosition = new Vector2Int(x + 1, y);
var sides = new List<Cell.Side>();
while (true) {
if (map.CheckBounds(upperPosition) && !map[upperPosition].inMaze)
sides.Add(Cell.Side.Top);
if (map.CheckBounds(lowerPosition) && !map[lowerPosition].inMaze)
sides.Add(Cell.Side.Bottom);
if (map.CheckBounds(leftPosition) && !map[leftPosition].inMaze)
sides.Add(Cell.Side.Left);
if (map.CheckBounds(rightPosition) && !map[rightPosition].inMaze)
sides.Add(Cell.Side.Right);
if (sides.Count == 0)
return;
Cell.Side side = sides[random.Next(0, sides.Count)];
switch (side) {
case Cell.Side.Top:
Cell upperCell = map[upperPosition];
cell.ConnectUpperCell(upperCell);
MoveNext(upperCell, map, random);
break;
case Cell.Side.Bottom:
Cell lowerCell = map[lowerPosition];
cell.ConnectLowerCell(lowerCell);
MoveNext(lowerCell, map, random);
break;
case Cell.Side.Left:
Cell leftCell = map[leftPosition];
cell.ConnectLeftCell(leftCell);
MoveNext(leftCell, map, random);
break;
case Cell.Side.Right:
Cell rightCell = map[rightPosition];
cell.ConnectRightCell(rightCell);
MoveNext(rightCell, map, random);
break;
default:
throw new ArgumentOutOfRangeException();
}
sides.Clear();
}
}Well, that's it. At this stage we already have code that generates a map that can be used to build a mesh of the maze.
Create a mesh of the maze
Great! Now we are almost ready to generate the mesh of the maze and display it in the editor. But before that, it is worth telling how everything will be arranged:
We will create
MonoBehaviourcomponent and let's call itMaze. We will also createMeshBuilderAndMazeGenerator.IN
MeshBuilderWe encapsulate all the logic of grid construction.IN
MazeGeneratorwe will place walls on the map usingMeshBuilder.IN
Mazewe create a map of the maze usingMapGeneratorwe send it toMazeGeneratorand we get a ready mesh.
I would like to make a small digression regarding the creation of a mesh. In short, a mesh is simply a set of triangles and the vertices that form them. In fact, vertices are points in three-dimensional space, described by Vector3 structure. In order for Unity to display triangles correctly, the vertices need to be indexed in a certain order. It looks something like this:
In the image above, the blue triangle is visible to us when we look at it from this angle. Accordingly, we do not see the white triangle, since it is drawn from the opposite side. Numbers 012 And 021 – vertex indices, their order affects which side the triangle will be drawn from. For more information on creating meshes in Unity, I suggest reading this article.
MeshBuilder
Now let's get back to our labyrinth and start with creating MeshBuilderwhich we will use later to arrange the walls and floor in the generator. All it will do is accept input Vector3 positions of the vertices and their indices, and in the end it will create the grid itself from all of this. To be honest, I was inspired to create it by StringBuilder to create lines, and I decided to make a similar one to create a grid (except that it doesn't have methods for deleting vertices). Let's create MeshBuilder:
using System;
using UnityEngine;
public class MeshBuilder {
public int VerticesCount { get; private set; }
public int IndexesCount { get; private set; }
private Vector3[] m_vertices;
private int[] m_indexes;
}It will store the current number of vertices in VerticesCount and indices in IndexesCountas well as arrays of vertices and indices.
Next, in the constructor we implement the calculation of the number of vertices and indices based on more abstract information – the number of cubes and planes:
public MeshBuilder (int cubes, int planes, int vertices = 0, int indexes = 0) {
const int cubeSides = 5; // do not add a bottom plane
const int planeVertices = 4;
const int planeIndexes = 6;
const int cubeVertices = cubeSides * planeVertices;
const int cubeIndexes = cubeSides * planeIndexes;
int totalVertices = cubes * cubeVertices + planes * planeVertices + vertices;
int totalIndexes = cubes * cubeIndexes + planes * planeIndexes + indexes;
m_vertices = new Vector3[totalVertices];
m_indexes = new int[totalIndexes];
}We will also make it optional to add additional vertices and indices. Now methods for adding vertices and indices:
public void AddVertices (Vector3 v1, Vector3 v2, Vector3 v3, Vector3 v4) {
if (m_vertices.Length < VerticesCount + 4)
ExpandVerticesArray();
m_vertices[VerticesCount++] = v1;
m_vertices[VerticesCount++] = v2;
m_vertices[VerticesCount++] = v3;
m_vertices[VerticesCount++] = v4;
}
public void AddIndexes (int t1, int t2, int t3, int t4, int t5, int t6) {
if (m_indexes.Length < IndexesCount + 6)
ExpandIndexesArray();
m_indexes[IndexesCount++] = t1;
m_indexes[IndexesCount++] = t2;
m_indexes[IndexesCount++] = t3;
m_indexes[IndexesCount++] = t4;
m_indexes[IndexesCount++] = t5;
m_indexes[IndexesCount++] = t6;
}When adding each vertex, we will increase the vertex counter by one. Similarly for indices.
It will also expand the size of the vertex and index arrays in case we still miscalculate their final number. Array expansion methods:
private void ExpandVerticesArray () {
var newArray = new Vector3[m_vertices.Length * 2];
Array.Copy(m_vertices, newArray, VerticesCount);
m_vertices = newArray;
Debug.LogWarning("Vertices array expanded");
}
private void ExpandIndexesArray () {
var newArray = new int[m_indexes.Length * 2];
Array.Copy(m_indexes, newArray, IndexesCount);
m_indexes = newArray;
Debug.LogWarning("Indexes array expanded");
}When expanding arrays, we will write a warning to the log.
Basically, we will add planes, and since a plane contains 4 vertices and 6 indices (two vertices lying on the diagonal of the plane are marked with two indices, since they belong to two triangles at the same time), then in the method AddVertices() we accept 4 vertices, and in the method AddIndexes() – 6 indices.
We would also like to visually distinguish the floor and walls, for this we need 2 sub meshes, each of which will display its part of the mesh using a separate material. Let's create methods for generating sub meshes, a list of sub mesh descriptors, the index of the vertex from which the sub mesh begins, and a Boolean field for checking the current state of generation:
/* ... */
private List<SubMeshDescriptor> m_descriptors = new();
private int m_indexStart;
private bool m_begunFormation;
/* ... */
public void BeginFormSubMesh () {
if (m_begunFormation) {
throw new InvalidOperationException(
$"Impossible to start a new formation. Finish the previous formation by calling the '{nameof(EndFormSubMesh)}' method and try again"
);
}
m_begunFormation = true;
m_indexStart = IndexesCount;
}
public void EndFormSubMesh () {
if (!m_begunFormation) {
throw new InvalidOperationException(
$"Impossible to finish a formation. Begin the formation by calling the '{nameof(BeginFormSubMesh)}' method and try again"
);
}
m_descriptors.Add(new SubMeshDescriptor {
indexStart = m_indexStart,
indexCount = IndexesCount - m_indexStart
});
m_begunFormation = false;
}Descriptors are needed to specify the initial vertex from which the submesh begins, and their number through indexStart And indexCount.
And finally, creating the grid:
public Mesh BuildMesh (string name = null) {
if (string.IsNullOrEmpty(name))
name = $"mesh_{Guid.NewGuid()}";
if (VerticesCount < m_vertices.Length) {
m_vertices = m_vertices[..VerticesCount];
Debug.LogWarning("Vertices array contains empty elements");
}
if (IndexesCount < m_indexes.Length) {
m_indexes = m_indexes[..IndexesCount];
Debug.LogWarning("Indexes array contains empty elements");
}
var mesh = new Mesh {
name = name,
vertices = m_vertices,
triangles = m_indexes
};
if (m_descriptors.Count > 0)
mesh.SetSubMeshes(m_descriptors, 0, m_descriptors.Count);
mesh.RecalculateNormals();
return mesh;
}Here we pre-check for empty elements in arrays. If there are empty elements, we cut off the excess, and, as with expansion, we write a warning to the log.
To add a plane and a cube, we will create 2 more methods, but in order not to clutter the class code MeshBuilderlet's make them extension methods in the class MeshBuilderExtensions. At first AddPlane():
using UnityEngine;
public static class MeshBuilderExtensions {
/// <summary>
/// Adds a XY oriented plane
/// </summary>
public static void AddPlane (this MeshBuilder meshBuilder, Vector3 center, Quaternion rotation, Vector2 size) {
float x = size.x * 0.5f;
float y = size.y * 0.5f;
int prevCount = meshBuilder.VerticesCount;
meshBuilder.AddVertices(
center + rotation * new Vector3(-x, y, 0),
center + rotation * new Vector3(x, y, 0),
center + rotation * new Vector3(-x, -y, 0),
center + rotation * new Vector3(x, -y, 0)
);
meshBuilder.AddIndexes(
prevCount, prevCount + 1, prevCount + 2, prevCount + 2, prevCount + 1, prevCount + 3
);
}
}We arrange the 4 vertices of the plane relative to its center. The size of the plane depends on how far its vertices are from the center, so x And y The coordinates of the vertices are calculated from half the dimensions of the plane. To set the orientation of the plane, we multiply rotation to the coordinates of its vertices. The first vertex will be in the upper left corner, the second – in the upper right, the third – in the lower left and the fourth – in the lower right. Then we add the indices in the order in which the vertices should be drawn.
Now let's add AddCube():
/// <summary>
/// Adds a cube without bottom plane
/// </summary>
public static void AddCube (this MeshBuilder meshBuilder, Vector3 center, Quaternion rotation, Vector3 size) {
float x = size.x * 0.5f;
float y = size.y * 0.5f;
float z = size.z * 0.5f;
int prevCount = meshBuilder.VerticesCount;
// front plane
meshBuilder.AddVertices(
center + rotation * new Vector3(x, y, z),
center + rotation * new Vector3(-x, y, z),
center + rotation * new Vector3(x, -y, z),
center + rotation * new Vector3(-x, -y, z)
);
// back plane
meshBuilder.AddVertices(
center + rotation * new Vector3(-x, y, -z),
center + rotation * new Vector3(x, y, -z),
center + rotation * new Vector3(-x, -y, -z),
center + rotation * new Vector3(x, -y, -z)
);
// right plane
meshBuilder.AddVertices(
center + rotation * new Vector3(x, y, -z),
center + rotation * new Vector3(x, y, z),
center + rotation * new Vector3(x, -y, -z),
center + rotation * new Vector3(x, -y, z)
);
// left plane
meshBuilder.AddVertices(
center + rotation * new Vector3(-x, y, z),
center + rotation * new Vector3(-x, y, -z),
center + rotation * new Vector3(-x, -y, z),
center + rotation * new Vector3(-x, -y, -z)
);
// top plane
meshBuilder.AddVertices(
center + rotation * new Vector3(-x, y, z),
center + rotation * new Vector3(x, y, z),
center + rotation * new Vector3(-x, y, -z),
center + rotation * new Vector3(x, y, -z)
);
for (int i = prevCount; i < meshBuilder.VerticesCount; i += 4)
meshBuilder.AddIndexes(i, i + 1, i + 2, i + 2, i + 1, i + 3);
}Here, a third z coordinate is added to calculate the coordinates of the vertices. Note that the vertices of opposite planes are added in reverse order (0123 for forward plane and 1032 for the back plane). Forward direction of the cube corresponds to the direction of view, therefore, looking at the cube, we see its back plane in front of us, it also corresponds to the plane that is created by the method AddPlane(). Strictly speaking, the resulting figure is not a cube, since the bottom plane is missing. I did this intentionally, since it will not be visible anyway when placing the walls in the labyrinth.
MazeGenerator
We are done with MeshBuilder and now we can start creating the maze generator. In it we will simply create a floor, 4 outer walls and place some inner walls on the map:
using UnityEngine;
public class MazeGenerator {
public Mesh GenerateMesh (Map map) {
var wallsCount = 0;
for (var y = 0; y < map.Size.y; y++) {
for (var x = 0; x < map.Size.x; x++) {
Cell cell = map[x, y];
if (y < map.Size.y - 1 && !cell.IsConnectWithLowerCell())
wallsCount++;
if (x < map.Size.x - 1 && !cell.IsConnectWithRightCell())
wallsCount++;
}
}
}
}We need to pre-calculate the number of internal walls. If the cells are not connected to each other, then there is a wall between them. Let's add methods for checking connections in the class Cell:
public bool IsConnectWithLowerCell () {
return LowerCell != null;
}
public bool IsConnectWithRightCell () {
return RightCell != null;
}After this we will create meshBuilder and we will give him the number of cubes (wallsCount), planes (1), vertices of external walls (48) and indices of external walls (72):
public Mesh GenerateMesh (Map map) {
/* ... */
const int exteriorWallVertices = 12;
const int exteriorWallIndexes = 18;
var meshBuilder = new MeshBuilder(wallsCount, 1, exteriorWallVertices * 4, exteriorWallIndexes * 4);
}Then we add the floor, walls and build a grid:
public Mesh GenerateMesh (Map map) {
/* ... */
GenerateFloor(meshBuilder, map);
GenerateWalls(meshBuilder, map);
return meshBuilder.BuildMesh();
}All the logic of the arrangement of walls and floors is in the methods GenerateFloor() And GenerateWalls(). Let's start with GenerateFloor():
private void GenerateFloor (MeshBuilder meshBuilder, Map map) {
meshBuilder.BeginFormSubMesh();
meshBuilder.AddPlane(Vector3.zero, Quaternion.Euler(90, 0, 0), map.Size);
meshBuilder.EndFormSubMesh();
}Here everything is simple – we conclude the addition of the floor plane between the methods BeginFormSubMesh() And EndFormSubMesh() so that the floor belongs to the first subgrid and is displayed as a separate material. Since AddPlane() the method creates an XY-oriented plane, we need to unfold it in XZ, i.e. rotate it by 90° along the x-axis. The size of the floor is equal to the size of the entire labyrinth.
Now GenerateWalls():
private void GenerateWalls (MeshBuilder meshBuilder, Map map) {
meshBuilder.BeginFormSubMesh();
GenerateExteriorWalls(meshBuilder, map.Size);
GenerateInteriorWalls(meshBuilder, map);
meshBuilder.EndFormSubMesh();
}Internal and external walls will be generated separately, since internal ones need to be placed on the map and can be added via AddCube()and there will always be 4 external walls, and due to their shape they will be formed slightly differently.
GenerateExteriorWalls()
private void GenerateExteriorWalls (MeshBuilder meshBuilder, Vector2Int mapSize) {
const float wallThickness = 0.2f;
float x = mapSize.x * 0.5f;
float y = mapSize.y * 0.5f;
GenerateFrontWall();
GenerateBackWall();
GenerateLeftWall();
GenerateRightWall();
return;
void GenerateFrontWall () {
// front side
meshBuilder.AddPlane(
new Vector3(0, 0.5f, y + wallThickness),
Quaternion.Euler(0, 180, 0),
new Vector2((x + wallThickness) * 2, 1)
);
// back side
meshBuilder.AddPlane(
new Vector3(0, 0.5f, y),
Quaternion.identity,
new Vector2(x * 2, 1)
);
int i = meshBuilder.VerticesCount;
// top side
meshBuilder.AddVertices(
new Vector3(-(x + wallThickness), 1, y + wallThickness),
new Vector3(x + wallThickness, 1, y + wallThickness),
new Vector3(-x, 1, y),
new Vector3(x, 1, y)
);
meshBuilder.AddIndexes(i, i + 1, i + 2, i + 2, i + 1, i + 3);
}
void GenerateBackWall () {
// front side
meshBuilder.AddPlane(
new Vector3(0, 0.5f, -(y + wallThickness)),
Quaternion.identity,
new Vector2((x + wallThickness) * 2, 1)
);
// back side
meshBuilder.AddPlane(
new Vector3(0, 0.5f, -y),
Quaternion.Euler(0, 180, 0),
new Vector2(x * 2, 1)
);
int i = meshBuilder.VerticesCount;
// top side
meshBuilder.AddVertices(
new Vector3(x + wallThickness, 1, -(y + wallThickness)),
new Vector3(-(x + wallThickness), 1, -(y + wallThickness)),
new Vector3(x, 1, -y),
new Vector3(-x, 1, -y)
);
meshBuilder.AddIndexes(i, i + 1, i + 2, i + 2, i + 1, i + 3);
}
void GenerateLeftWall () {
// front side
meshBuilder.AddPlane(
new Vector3(-(x + wallThickness), 0.5f, 0),
Quaternion.Euler(0, 90, 0),
new Vector2((y + wallThickness) * 2, 1)
);
// back side
meshBuilder.AddPlane(
new Vector3(-x, 0.5f, 0),
Quaternion.Euler(0, -90, 0),
new Vector2(y * 2, 1)
);
int i = meshBuilder.VerticesCount;
// top side
meshBuilder.AddVertices(
new Vector3(-(x + wallThickness), 1, -(y + wallThickness)),
new Vector3(-(x + wallThickness), 1, y + wallThickness),
new Vector3(-x, 1, -y),
new Vector3(-x, 1, y)
);
meshBuilder.AddIndexes(i, i + 1, i + 2, i + 2, i + 1, i + 3);
}
void GenerateRightWall () {
// front side
meshBuilder.AddPlane(
new Vector3(x + wallThickness, 0.5f, 0),
Quaternion.Euler(0, -90, 0),
new Vector2((y + wallThickness) * 2, 1)
);
// back side
meshBuilder.AddPlane(
new Vector3(x, 0.5f, 0),
Quaternion.Euler(0, 90, 0),
new Vector2(y * 2, 1)
);
int i = meshBuilder.VerticesCount;
// top side
meshBuilder.AddVertices(
new Vector3(x + wallThickness, 1, y + wallThickness),
new Vector3(x + wallThickness, 1, -(y + wallThickness)),
new Vector3(x, 1, y),
new Vector3(x, 1, -y)
);
meshBuilder.AddIndexes(i, i + 1, i + 2, i + 2, i + 1, i + 3);
}
}The method turned out to be quite long. Here we have created separate local functions for each wall, since the outer walls do not have side planes, and therefore they cannot be added using the method AddCube(). We define the upper plane directly through AddVertices()because we want a trapezoid shape, not a rectangular one.
GenerateInteriorWalls():
private void GenerateInteriorWalls (MeshBuilder meshBuilder, Map map) {
const float wallThickness = 0.2f;
for (var x = 0; x < map.Size.x; x++) {
for (var y = 0; y < map.Size.y; y++) {
Cell cell = map[x, y];
if (y < map.Size.y - 1 && !cell.IsConnectWithLowerCell())
GenerateBottomWall(meshBuilder, map.MapToMazePosition(cell.Position), wallThickness);
if (x < map.Size.x - 1 && !cell.IsConnectWithRightCell())
GenerateRightWall(meshBuilder, map.MapToMazePosition(cell.Position), wallThickness);
}
}
}Here we run through the entire map and place walls between unconnected cells. Also here we introduce a new method Map – MapToMazePosition(). Walls must be placed relative to local cell positions, which must be obtained from map positions:
public Vector3 MapToMazePosition (Vector2Int position) {
return new Vector3(-Size.x * 0.5f + position.x, 0, Size.y * 0.5f - position.y);
}In this case, maze position is the position in local (object) coordinates of the maze.
This is a working option, but we could use a transformation matrix for the transformation. Let's rewrite the code:
public Vector3 MapToMazePosition (Vector2Int position) {
return m_mapToMazeMatrix * new Vector4(position.x, position.y, 0, 1);
}Then we create a matrix field and initialize it in the constructor:
private readonly Matrix4x4 m_mapToMazeMatrix;
public Map (Vector2Int size) {
Size = size;
cells = new Cell[size.x, size.y];
m_mapToMazeMatrix = new Matrix4x4(
new Vector4(1, 0, 0, 0),
new Vector4(0, 0, -1, 0),
new Vector4(0, 1, 0, 0),
new Vector4(-Size.x * 0.5f + 0.5f, 0, Size.y * 0.5f - 0.5f, 0)
);
/* ... */
}Here the upper left 3×3 part of the matrix is essentially a matrix of 90° rotation along the x-axis, and the fourth line encodes the offset of the center of the map coordinates relative to the coordinates of the maze.
Let's get back to the placement of the walls. We need to implement the placement of the lower and right walls:
private void GenerateBottomWall (MeshBuilder meshBuilder, Vector3 cellPosition, float wallThickness) {
var wallPosition = new Vector3(cellPosition.x, 0.5f, cellPosition.z - 0.5f);
var wallSize = new Vector3(1 + wallThickness, 1, wallThickness);
meshBuilder.AddCube(wallPosition, Quaternion.identity, wallSize);
}
private void GenerateRightWall (MeshBuilder meshBuilder, Vector3 cellPosition, float wallThickness) {
var wallPosition = new Vector3(cellPosition.x + 0.5f, 0.5f, cellPosition.z);
var wallSize = new Vector3(wallThickness, 1, 1);
meshBuilder.AddCube(wallPosition, Quaternion.identity, wallSize);
}Add the thickness of the walls to the size of the lower wall along the x-axis. This will eliminate gaps in the outer corners between the walls.
You can see that the walls are different in size, but their orientation is the same. The question is – why do we need the second parameter in AddCube()? In this case (when arranging walls in a rectangular labyrinth) we really don’t need it, but when creating MeshBuilder I wanted to show code that does more general operations (the original code uses it to create mazes of other shapes). We can create an overload that ignores the second parameter and only accepts a position and a size:
public static void AddCube (this MeshBuilder meshBuilder, Vector3 center, Vector3 size) {
meshBuilder.AddCube(center, Quaternion.identity, size);
}When replacing calls we get the following:
private void GenerateBottomWall (MeshBuilder meshBuilder, Vector3 cellPosition, float wallThickness) {
var wallPosition = new Vector3(cellPosition.x, 0.5f, cellPosition.z - 0.5f);
var wallSize = new Vector3(1 + wallThickness, 1, wallThickness);
meshBuilder.AddCube(wallPosition, wallSize);
}
private void GenerateRightWall (MeshBuilder meshBuilder, Vector3 cellPosition, float wallThickness) {
var wallPosition = new Vector3(cellPosition.x + 0.5f, 0.5f, cellPosition.z);
var wallSize = new Vector3(wallThickness, 1, 1);
meshBuilder.AddCube(wallPosition, wallSize);
}At this point, the mesh generation is complete. All that remains is to display it in the editor!
Putting it all together
To display the generated grid we will create a component Mazein it we will create a maze map through the map generator, then transfer it to the maze generator and insert the resulting grid into MeshFilter component. Let's create a component Maze and in it we implement the method CreateNewMaze():
using UnityEngine;
public class Maze : MonoBehaviour {
[SerializeField]
private MeshFilter meshFilter;
[SerializeField, HideInInspector]
private Vector2Int size = new(10, 10);
[SerializeField, HideInInspector]
private int seed;
public Vector2Int Size => size;
private readonly MapGenerator m_mapGenerator = new();
private readonly MazeGenerator m_mazeGenerator = new();
public void CreateNewMaze () {
meshFilter.mesh = m_mazeGenerator.GenerateMesh(m_mapGenerator.GenerateMap(Size, seed));
}
}We will call the method when we click on the button in the inspector. To do this, we need to create MazeEditor class in which we will configure the size of the maze and seed value. We will also display the map size in Scene View. Full code MazeEditor you can see it in the demo.
Now it's time to check everything in the editor. Let's create an empty object and add components to it Maze, MeshFilter And MeshRendererlet's create 2 materials and install them in MeshRenderer:
Now let's set the size of the maze and create it. With Maze Size = (10;10) and Seed = 0, I got this maze:
Great! We've finally finished writing the generation code and created the maze. We could have finished here, but there's more.
Optimization
When generating, we do not take into account one point – some horizontal and vertical walls are generated in one row, repeating several times. It would be logical to build them not as separate walls, but as one, with a length of several cells. This can significantly reduce the number of vertices in the final grid.
We will do the following. We will not rewrite the existing code, but simply add a more optimized one to it, so that we can then compare the two options. Our weak point is in the method GenerateInteriorWalls(). Let's make a more optimized version of it and call it OptimizedGenerateInteriorWalls():
private void OptimizedGenerateInteriorWalls (MeshBuilder meshBuilder, Map map) {
GenerateVerticalWalls(meshBuilder, map);
GenerateHorizontalWalls(meshBuilder, map);
}We will generate vertical and horizontal walls separately.
GenerateVerticalWalls():
private void GenerateVerticalWalls (MeshBuilder meshBuilder, Map map) {
const float wallThickness = 0.2f;
for (var x = 0; x < map.Size.x - 1; x++) {
for (var y = 0; y < map.Size.y; y++) {
if (!map[x, y].IsConnectWithRightCell()) {
Vector2Int startPosition = map[x, y].Position;
var wallLength = 0;
while (y < map.Size.y && !map[x, y].IsConnectWithRightCell()) {
wallLength++;
y++;
}
Vector2Int endPosition = map[x, y - 1].Position;
Vector3 wallCenter = Vector3.Lerp(
map.MapToMazePosition(startPosition), map.MapToMazePosition(endPosition), 0.5f
);
GenerateVerticalWall(meshBuilder, wallCenter, wallThickness, wallLength);
}
}
}
}We run vertically along the map, when we find a wall we move further until the wall ends. Between the two outer cells we select a point exactly in the middle between them – this will be the position of the entire wall along the cells. Similarly for GenerateHorizontalWalls():
private void GenerateHorizontalWalls (MeshBuilder meshBuilder, Map map) {
const float wallThickness = 0.2f;
for (var y = 0; y < map.Size.y - 1; y++) {
for (var x = 0; x < map.Size.x; x++) {
if (!map[x, y].IsConnectWithLowerCell()) {
Vector2Int startPosition = map[x, y].Position;
var wallLength = 0;
while (x < map.Size.x && !map[x, y].IsConnectWithLowerCell()) {
wallLength++;
x++;
}
Vector2Int endPosition = map[x - 1, y].Position;
Vector3 wallCenter = Vector3.Lerp(
map.MapToMazePosition(startPosition), map.MapToMazePosition(endPosition), 0.5f
);
GenerateHorizontalWall(meshBuilder, wallCenter, wallThickness, wallLength);
}
}
}
}Let's take the calculation of walls into a separate method:
private int CountWalls (Map map) {
var wallsCount = 0;
for (var y = 0; y < map.Size.y; y++) {
for (var x = 0; x < map.Size.x; x++) {
Cell cell = map[x, y];
if (y < map.Size.y - 1 && !cell.IsConnectWithLowerCell())
wallsCount++;
if (x < map.Size.x - 1 && !cell.IsConnectWithRightCell())
wallsCount++;
}
}
return wallsCount;
}Let's create a version of it with the calculation of longer walls:
private int OptimizedCountWalls (Map map) {
var wallsCount = 0;
// count vertical walls
for (var x = 0; x < map.Size.x - 1; x++) {
for (var y = 0; y < map.Size.y; y++) {
if (!map[x, y].IsConnectWithRightCell()) {
while (y < map.Size.y && !map[x, y].IsConnectWithRightCell())
y++;
wallsCount++;
}
}
}
// count horizontal walls
for (var y = 0; y < map.Size.y - 1; y++) {
for (var x = 0; x < map.Size.x; x++) {
if (!map[x, y].IsConnectWithLowerCell()) {
while (x < map.Size.x && !map[x, y].IsConnectWithLowerCell())
x++;
wallsCount++;
}
}
}
return wallsCount;
}Let's make some changes GenerateMesh():
public Mesh GenerateMesh (Map map, bool isOptimized) {
int wallsCount = isOptimized ? OptimizedCountWalls(map) : CountWalls(map);
const int exteriorWallVertices = 12;
const int exteriorWallIndexes = 18;
var meshBuilder = new MeshBuilder(wallsCount, 1, exteriorWallVertices * 4, exteriorWallIndexes * 4);
GenerateFloor(meshBuilder, map);
GenerateWalls(meshBuilder, map, isOptimized);
return meshBuilder.BuildMesh();
}IN GenerateWalls():
private void GenerateWalls (MeshBuilder meshBuilder, Map map, bool isOptimized) {
meshBuilder.BeginFormSubMesh();
GenerateExteriorWalls(meshBuilder, map.Size);
if (isOptimized)
OptimizedGenerateInteriorWalls(meshBuilder, map);
else
GenerateInteriorWalls(meshBuilder, map);
meshBuilder.EndFormSubMesh();
}And in the component Mazeadding a field isOptimized:
[SerializeField, HideInInspector]
private bool isOptimized;
public Vector2Int Size => size;
private readonly MapGenerator m_mapGenerator = new();
private readonly MazeGenerator m_mazeGenerator = new();
public void CreateNewMaze () {
meshFilter.mesh = m_mazeGenerator.GenerateMesh(m_mapGenerator.GenerateMap(Size, seed), isOptimized);
}Let's go back to our labyrinth in the editor and give it isOptimized and let's try to generate:
It can be seen that we have reduced the number of vertices by 680, i.e. by 40%.
Conclusion
Even though generating orthogonal mazes is fairly simple, it took me a while to implement it. The biggest development challenge was when constructing the grid, as I hadn't done procedural generation before.
Methods for calculating the uv coordinates of the grid are also not described here, it is impossible to apply a texture to such labyrinths. In addition, artifacts may appear at the intersections of walls during rendering, which are not visible if the walls are of the same color. This is exactly the option used in the game – the floor and walls have only color, only one plane under the floor has a texture for the bloom effect.
The original code also has an implementation of three other maze shapes, but I didn't include it here because it would have made the article four times longer.
As I have promised – technical demo link.
In the future, I also plan to write about how I implemented the placement of the player and targets in the labyrinth (up to 3) and finding the shortest path to the nearest target.
Best wishes!
