Приветствую вас! Меня зовут Денис, я разрабатываю игры на Unity и сегодня хотел бы рассказать о том, как устроена генерация лабиринтов в игре, которая находится на данный момент в разработке. 

Это не коммерческий проект (хотя есть планы по выпуску игры в Google Play), а мой личный, так что в конце статьи вас ждёт технодемка.

Сразу хочу сказать, что я не считаю себя экспертом в разработке игр в общем и на движке Unity в частности, некоторые моменты вам могут показаться спорными и не оптимальными, но всё же я хочу поделиться своим опытом и готов ответить на ваши вопросы и принять к сведению критику.

Создаём карту лабиринта

В качестве алгоритма генерации я выбрал recursive backtracker, т.к. он достаточно прост в понимании и при этом создаёт сложные лабиринты с длинными тупиками. Также его возможно использовать с любыми формами лабиринта, не только с ортогональной. Если хотите более подробно изучить все, что связано с лабиринтами и их генерацией, рекомендую к прочтению эту статью.

Перед тем, как описать работу алгоритма, необходимо выполнить несколько предварительных действий. Алгоритм генерирует карту, на основе которой мы будем строить лабиринт. Карта состоит из клеток, соединённых между собой. Карту лабиринта можно представить в виде графа, где его вершины - это клетки, а рёбра - соединения между клетками. Начнём с клеток:

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; }

}

Каждая клетка потенциально может быть соединена с 4 соседними клетками - сверху, снизу, справа и слева. На уровне кода соединение - просто ссылка на другую клетку. Поле inMaze служит для проверки наличия клетки в графе, а по свойству Position мы сможем найти клетку на карте. Теперь добавим карту:

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)
                };
            }
        }
    }

}

Как видите, карта содержит в себе размер Size и двухмерный массив cells. В конструкторе мы инициализируем массив и заполняем его клетками, проставляя их позиции.

Теперь стоит рассказать непосредственно о работе алгоритма recursive backtracker. Если вкратце, шаги выполнения можно описать так:

1. Случайным образом выбираем клетку из карты, делаем её частью лабиринта (cell.inMaze = true;).

2. Среди соседних клеток (всего их 4) случайным образом выбираем ту, которая находится в пределах карты, но ещё не является частью лабиринта.

3. Если на шаге 2 мы не выбрали ни одну клетку - алгоритм возвращается к предыдущей выбранной клетке, в ином случае соединяем обе клетки, делаем выбранную клетку частью лабиринта и переходим к шагу 2. Если мы дошли до клетки, выбранной на шаге 1 (соответственно, у нас не осталось ни одной клетки для выбора) - алгоритм прекращает работу.

Теперь нам все это нужно как-то закодировать. Начнём с создания генератора карты:

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;
    }

}

В методе GenerateMap() уже реализованы все 3 шага алгоритма - первый в методе GetRandomCell() класса Map и второй и третий в методе MoveNext(), который выполняется рекурсивно (отсюда и название алгоритма). Я буду использовать системный Random с заданным значением seed для контроля генерации карты. Да, как вы могли заметить, оба метода GetRandomCell() и MoveNext() ещё не реализованы, так что исправим это:

public Cell GetRandomCell (Random random) {
   return this[random.Next(0, Size.x), random.Next(0, Size.y)];
}

Здесь мы берём клетку из массива через индексатор по случайным x и y координатам. Реализуем индексатор:

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];

В индексаторе мы проверяем входной вектор, что он не выходит за пределы карты, и просто возвращаем клетку из массива по её позиции. Индексатор имеет 2 перегрузки - первую будет удобно использовать при проходе по всей карте в циклах, а вторую будет удобнее использовать в методе MoveNext().

Теперь вернёмся к алгоритму. Мы уже выполнили шаг 1, взяв рандомную клетку из карты. Теперь нам нужны её соседи. Соседей мы можем взять из карты через индексатор, для этого нам достаточно посчитать их позиции:

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);
}

Позиции в карте начинаются с левого верхнего угла, таким образом, чтобы подняться на одну клетку выше, нам нужно вычесть из y единицу. На самом деле, это необязательное правило, вы бы могли реализовать иначе, отсчитывая карту от левого нижнего угла, это лишь вопрос удобства.

Далее нам нужно определить, какие у клетки есть соседи и не являются ли они частью лабиринта. Различать соседей будем по тому, с какой стороны они находятся относительно cell. Для этого мы реализуем enum в классе Cell и назовём его Side:

public class Cell {

	/* ... */

    public enum Side {

        Top,
        Bottom,
        Left,
        Right

    }

}

Затем реализуем метод CheckBounds() в классе Map для проверки выхода позиции за границы карты:

public bool CheckBounds (Vector2Int position) {
	return position.x >= 0 && position.x < Size.x && position.y >= 0 && position.y < Size.y;
}

Общий результат true, если позиция находится в пределах карты.

Теперь выбираем соседей:

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);
}

Если у клетки нет доступных соседей - прекращаем работу алгоритма:

private void MoveNext (Cell cell, Map map, Random random) {
	/* ... */
	
	var sides = new List<Cell.Side>();
	
	/* ... */

	if (sides.Count == 0)
		return;
}

Всё, что нам осталось - выбрать случайную клетку из имеющихся, соединить текущую клетку с выбранной и перейти к следующему шагу. Для соединения клеток реализуем 4 метода в классе 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;
}

После соединения клетки автоматически должны стать частью лабиринта. К тому же обе клетки считаются соединёнными, если они обе ссылаются друг на друга. В дальнейшем это избавит от ошибок. 

Теперь вернёмся к MoveNext() (напомню, что нам нужно выбрать случайную клетку, соединить её с текущей и перейти к следующему шагу):

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(); // в конце очищаем список, т.к. он будет использоваться повторно при выходе из рекурсивного вызова

И не забудем завернуть всё это в цикл. В итоге у нас получается такой метод:

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();
	}
}

В общем-то, это всё. На данном этапе у нас уже имеется код, генерирующий карту, по которой можно строить mesh лабиринта.

Создаём mesh лабиринта

Отлично! Теперь мы почти готовы к тому, чтобы сгенерировать mesh лабиринта и отобразить его в editor. Но перед этим стоит рассказать, как будет всё устроено:

1. Мы создадим MonoBehaviour компонент и назовём его Maze. Также создадим MeshBuilder и MazeGenerator.

2. В MeshBuilder инкапсулируем всю логику построения сетки.

3. В MazeGenerator мы будем расставлять стены по карте, используя MeshBuilder.

4. В Maze мы создаём карту лабиринта, используя MapGenerator, отправляем её в MazeGenerator и получаем готовую mesh.

Хотел бы сделать небольшое отступление касаемо создания сетки. Если кратко, то mesh - это просто набор треугольников и вершин, которые их образуют. Фактически вершины - это точки в трёхмерном пространстве, описываемые Vector3 структурой. Чтобы Unity смог правильно отобразить треугольники, нужно в определённом порядке проиндексировать вершины. Выглядит это примерно так:

На изображении выше синим обозначен треугольник, который для нас виден, когда мы смотрим на него с данного ракурса. Соответственно, белый треугольник мы не видим, т.к. он отрисовывается с противоположной стороны. Цифры 012 и 021 - индексы вершин, их порядок влияет на то, с какой стороны будет отрисовываться треугольник. Для более подробной информации о создании сеток в Unity предлагаю к прочтению эту статью.

MeshBuilder

Теперь вернёмся к нашему лабиринту и начнём с создания MeshBuilder, который мы в дальнейшем будем использовать для расставления стен и пола в генераторе. Всё, что он будет делать - это принимать на вход Vector3 позиции вершин и их индексы, а в конце он создаст из всего этого саму сетку. Честно сказать, на его создание меня вдохновил StringBuilder для создания строк, и я решил сделать аналогичный для создания сетки (разве что только в нём нет методов удаления вершин). Создадим 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;

}

Он будет хранить в себе текущее количество вершин в VerticesCount и индексов в IndexesCount, а также массивы вершин и индексов. 

Далее в конструкторе реализуем подсчёт количества вершин и индексов на основе более абстрактной информации - количестве кубов и плоскостей:

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];
}

Также сделаем опциональную возможность добавлять дополнительные вершины и индексы. Теперь методы для добавления вершин и индексов:

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;
}

При добавлении каждой вершины мы будем увеличивать счётчик вершин на единицу. Аналогично для индексов.

Также будет расширять размер массивов вершин и индексов на случай, если мы всё таки неверно рассчитаем их итоговое количество. Методы расширения массивов:

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");
}

При расширении массивов будем записывать в лог предупреждение.

В основном мы будем добавлять плоскости, а поскольку плоскость содержит 4 вершины и 6 индексов (две вершины, лежащие на диагонали плоскости, маркируются двумя индексами, т.к. принадлежат одновременно двум треугольникам), то и в методе AddVertices() мы принимаем 4 вершины, а в методе AddIndexes() - 6 индексов.

Нам бы ещё хотелось визуально различать пол и стены, для этого нам нужны 2 подсетки (sub meshes), каждая из которых будет отображать свою часть сетки, используя отдельный материал. Создадим методы формирования подсеток, список дескрипторов подсеток, индекс вершины, с которой начинается подсетка, и булево поле для проверки текущего состояния формирования:

/* ... */

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;
}

Дескрипторы нужны для того, чтобы задать начальную вершину, с которой начинается submesh, и их количество через indexStart и indexCount.

И, наконец, создание сетки:

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;
}

Здесь мы предварительно делаем проверку на наличие незаполненных элементов в массивах. Если есть пустые элементы - отсекаем лишнее, и также, как при расширении, пишем в лог предупреждение.

Для добавления плоскости и куба создадим ещё 2 метода, но чтобы не загромождать код класса MeshBuilder, сделаем их методами расширения в классе MeshBuilderExtensions. Сначала 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
       );
   }

}

4 вершины плоскости мы расставляем относительно её центра. Размер плоскости зависит от того, насколько далеко её вершины будут от центра, поэтому x и y координаты вершин считаем из половины размеров плоскости. Для задания ориентации плоскости умножаем rotation на координаты её вершин. Первая вершина будет в левом верхнем углу, вторая - в правом верхнем, третья - в левом нижнем и четвёртая - в правом нижнем. Затем добавляем индексы в том порядке, в котором должны отрисовываться вершины.

Теперь добавим 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);
}

Здесь для вычисления координат вершин добавляется третья z координата. Заметьте, что вершины противоположных плоскостей добавляются в обратном порядке (0123 для forward plane и 1032 для back plane). Forward направление куба соответствует направлению взгляда, поэтому, смотря на куб, мы видим его заднюю плоскость перед собой, она же соответствует той плоскости, которая создаётся методом AddPlane(). Строго говоря, получающаяся фигура не является кубом, т.к. нижняя плоскость отсутствует. Я сделал это намеренно, поскольку её всё равно не будет видно при расстановке стен в лабиринте.

MazeGenerator

Мы закончили с MeshBuilder и теперь можем приступить к созданию генератора лабиринта. В нём мы просто создадим пол, 4 крайние стены и расставим несколько внутренних стен по карте:

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++;
           }
       }
   }

}

Нам нужно предварительно посчитать количество внутренних стен. Если клетки не имеют соединения между собой - значит между ними есть стена. Добавим методы проверки связей в классе Cell:

public bool IsConnectWithLowerCell () {
   return LowerCell != null;
}


public bool IsConnectWithRightCell () {
   return RightCell != null;
}

После этого создадим meshBuilder и передадим ему количество кубов (wallsCount), плоскостей (1), вершин внешних стен (48) и индексов внешних стен (72):

public Mesh GenerateMesh (Map map) {
   /* ... */

    const int exteriorWallVertices = 12;
    const int exteriorWallIndexes = 18;
    var meshBuilder = new MeshBuilder(wallsCount, 1, exteriorWallVertices * 4, exteriorWallIndexes * 4);

}

Затем добавим пол, стены и построим сетку:

public Mesh GenerateMesh (Map map) {
   /* ... */

   GenerateFloor(meshBuilder, map);
   GenerateWalls(meshBuilder, map);

   return meshBuilder.BuildMesh();
}

Вся логика расставления стен и пола находится в методах GenerateFloor() и GenerateWalls(). Начнём с GenerateFloor():

private void GenerateFloor (MeshBuilder meshBuilder, Map map) {
   meshBuilder.BeginFormSubMesh();
   meshBuilder.AddPlane(Vector3.zero, Quaternion.Euler(90, 0, 0), map.Size);
   meshBuilder.EndFormSubMesh();
}

Здесь всё просто - мы заключаем добавление плоскости пола между методами BeginFormSubMesh() и EndFormSubMesh() для того, чтобы пол принадлежал первой подсетке и отображался отдельным материалом. Поскольку AddPlane() метод создаёт XY-ориентированную плоскость, нам нужно её развернуть в XZ, т.е. повернуть по x-оси на 90°. Размер пола равен размеру всего лабиринта.

Теперь GenerateWalls():

private void GenerateWalls (MeshBuilder meshBuilder, Map map) {
   meshBuilder.BeginFormSubMesh();

   GenerateExteriorWalls(meshBuilder, map.Size);
   GenerateInteriorWalls(meshBuilder, map);

   meshBuilder.EndFormSubMesh();
}

Внутренние и внешние стены будут генерироваться отдельно, поскольку внутренние необходимо расставлять по карте и их можно добавлять через AddCube(), а внешних стен всегда будет 4, и из-за их формы они будут формироваться несколько иначе.

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);
   }
}

Получился достаточно длинный метод. Здесь мы для каждой стены завели отдельные локальные функции, поскольку у внешних стен нет боковых плоскостей, соответственно, их нельзя добавить методом AddCube(). Верхнюю плоскость задаём напрямую через AddVertices(), поскольку нам нужна трапециевидная форма, а не прямоугольная.

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);
       }
   }
}

Здесь пробегаемся по всей карте и расставляем стены между несоединёнными клетками. Также здесь мы вводим новый метод у Map - MapToMazePosition(). Стены необходимо расставлять относительно локальных позиций клеток, которые нужно получить из позиций на карте:

public Vector3 MapToMazePosition (Vector2Int position) {
   return new Vector3(-Size.x * 0.5f + position.x, 0, Size.y * 0.5f - position.y);
}

В данном случае maze position представляет собой позицию в локальных (объектных) координатах лабиринта.

Это рабочий вариант, но для преобразования мы могли бы использовать матрицу трансформации. Перепишем код:

public Vector3 MapToMazePosition (Vector2Int position) {
   return m_mapToMazeMatrix * new Vector4(position.x, position.y, 0, 1);
}

Затем создадим поле матрицы и инициализируем его в конструкторе:

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)
   );

   /* ... */
}

Здесь левая верхняя 3х3 часть матрицы является по сути матрицей поворота на 90° по x-оси, а в четвёртой строке закодировано смещение центра координат карты относительно координат лабиринта.

Вернёмся к расстановке стен. Нам нужно реализовать расстановку нижних и правых стен:

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);
}

К размеру нижней стены по x-оси добавляем толщину стен. Это избавит от зазоров во внешних углах между стенами.

Можно заметить, что стены отличаются размерами, но ориентация у них одинакова. Вопрос - для чего нам тогда второй параметр в AddCube()? В данном случае (при расстановке стен в прямоугольном лабиринте) нам он действительно не нужен, но при создании MeshBuilder я хотел показать код, выполняющий более общие операции (в оригинальном коде он используется при создании лабиринтов других форм). Мы можем создать перегрузку, которая игнорирует второй параметр и принимает только позицию и размер:

public static void AddCube (this MeshBuilder meshBuilder, Vector3 center, Vector3 size) {
   meshBuilder.AddCube(center, Quaternion.identity, size);
}

При замене вызовов получаем следующее:

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);
}

На этом генерация сетки закончена. Осталось только отобразить её в редакторе!

Соединяем всё вместе

Для отображения сгенерированной сетки мы создадим компонент Maze, в нём мы будем создавать карту лабиринта через генератор карты, затем передавать её в генератор лабиринта и полученную сетку вставлять в MeshFilter компонент. Создадим компонент Maze и в нём реализуем метод 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));
   }

}

Вызывать метод будем при нажатии на кнопку в инспекторе. Для этого нам нужно создать MazeEditor класс, в котором будем настраивать размер лабиринта и seed значение. Также сделаем отображение размера карты в Scene View. Полный код MazeEditor можно будет посмотреть в демо.

Теперь самое время проверить всё в редакторе. Создадим пустой объект и добавим к нему компоненты Maze, MeshFilter и MeshRenderer, создадим 2 материала и установим их в MeshRenderer:

Теперь зададим размер лабиринта и создадим его. При Maze Size = (10;10) и Seed = 0 у меня получился такой лабиринт:

Отлично! Мы, наконец, полностью завершили написание кода генерации и создали лабиринт. На этом можно бы было закончить, но есть кое-что ещё.

Оптимизация

При генерации мы не учитываем один момент - некоторые горизонтальные и вертикальные стены генерируются в один ряд, повторяясь несколько раз. Было бы логично строить их не как отдельные стены, а как одну, с длиной в несколько клеток. Это может значительно сократить количество вершин в итоговой сетке.

Мы поступим следующим образом. Мы не будем переписывать существующий код, а просто добавим к нему более оптимизированный, чтобы затем можно было сравнить 2 варианта. Наше слабое место находится в методе GenerateInteriorWalls(). Сделаем его более оптимизированный вариант и назовём OptimizedGenerateInteriorWalls():

private void OptimizedGenerateInteriorWalls (MeshBuilder meshBuilder, Map map) {
   GenerateVerticalWalls(meshBuilder, map);
   GenerateHorizontalWalls(meshBuilder, map);
}

Вертикальные и горизонтальные стены будем генерировать отдельно.

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);
           }
       }
   }
}

Пробегаемся вертикально по карте, при обнаружении стены продвигаемся дальше до тех пор, пока стена не закончится. Между двумя крайними клетками выбираем точку ровно посередине между ними - это будет позиция всей стены вдоль клеток. Аналогично для 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);
           }
       }
   }
}

Вынесем подсчёт стен в отдельный метод:

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;
}

Создадим его вариант с подсчётом более длинных стен:

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;
}

Внесём изменения в 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();
}

В 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();
}

И в компонент Maze, добавив поле 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);
}

Вернёмся к нашему лабиринту в редакторе, поставим ему isOptimized и попробуем сгенерировать:

Видно, что мы сократили количество вершин на 680, т.е. на 40%.

Заключение

Несмотря на то, что генерация ортогональных лабиринтов достаточно простая, лично мне потребовалось время для её реализации. Больше сложностей при разработке возникало во время построения сетки, поскольку до этого я не занимался процедурной генерацией.

Здесь также не описаны методы подсчёта uv-координат сетки, на такие лабиринты не получится наложить текстуру. К тому же на пересечениях стен могут возникнуть артефакты при рендере, которых не видно, если стены одного цвета. В игре используется именно такой вариант - пол и стены имеют только цвет, текстуру имеет только один plane под полом для bloom-эффекта.

В оригинальном коде также есть реализация трёх других форм лабиринта, но я не стал включать её сюда, поскольку статья вышла бы тогда вчетверо больше.

Как и обещал - техническое демо по ссылке.

В будущем я планирую написать также о том, как я реализовал расстановку игрока и целей в лабиринте (до 3-х штук) и нахождение кратчайшего пути до ближайшей цели.

Всего хорошего!