Генератор лабиринтов

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


Итак, посмотрим на сам алгоритм:

using System.Collections;
using System.Collections.Generic;
using UnityEngine;

public static class Maze {

	struct Node
	{
		public bool path, check;
	}

	public static int Round(int value) // если число четное, возвращаем нечетное
	{
		if(value % 2 == 0) return value + 1; else return value;
	}

	public static int[,] Generate(int width, int height)
	{
		if(width < 10 || height < 10) return null;

		width = Round(width);
		height = Round(height);

		int x, y;
		bool finish = false;

		List<string> dir = new List<string>();
		Node[,] field = new Node[width, height];

		int j = Round(Random.Range(0, height-1));

		field[1, j].path = true; // развилка
		field[1, j].check = true; // проходимое место

		while(true)
		{
			finish = true;

			for(y = 0; y < height; y++)
			{
				for(x = 0; x < width; x++)
				{
					if(field[x, y].path) // ищем флажок развилки
					{
						finish = false;

						if(x-2 >= 0)
						if(!field[x-2, y].check) dir.Add("Left"); // если путь свободен, добавляем направление

						if(y-2 >= 0)
						if(!field[x, y-2].check) dir.Add("Down");

						if(x+2 < width)
						if(!field[x+2, y].check) dir.Add("Right");

						if(y+2 < height)
						if(!field[x, y+2].check) dir.Add("Up");

						if(dir.Count > 0)
						{
							switch(dir[Random.Range(0, dir.Count)]) // выбираем случайное направление
							{
							case "Left":
								field[x-1, y].check = true;
								field[x-2, y].check = true;
								field[x-2, y].path = true;
								break;

							case "Down":
								field[x, y-1].check = true;
								field[x, y-2].check = true;
								field[x, y-2].path = true;
								break;

							case "Right":
								field[x+1, y].check = true;
								field[x+2, y].check = true;
								field[x+2, y].path = true;
								break;

							case "Up":
								field[x, y+1].check = true;
								field[x, y+2].check = true;
								field[x, y+2].path = true;
								break;
							}
						}
						else // если направление добавить невозможно, убираем флажок развилки
						{
							field[x, y].path = false;
						}

						dir.Clear(); // чистим массив
					}
				}
			}

			if(finish) break; // если не нашлось ни одного флажка развилки, выходим
		}

		int[,] result = new int[width, height];

		// создаем новый массив, где 1 проходимое место, а -1 стена
		for(y = 0; y < height; y++)
		{
			for(x = 0; x < width; x++)
			{
				if(field[x, y].check)
				{
					result[x, y] = 1;
				}
				else
				{
					result[x, y] = -1;
				}
			}
		}

		return result;
	}
}

Логика работы в следующем. Изначально, все элементы массива считаются как "стена", а в процессе делается "вырубка" прохода. На старте выбирается элемент массива, делается две отметки: это проход и это развилка. Далее, переходим в цикл, во время прохода по массиву, находим элемент с флагом "развилка". Затем, в четыре стороны делам проверку, проходили мы там или нет, если нет то добавляем проверяемое направление как возможное, сама проверка делается на два хода сразу, таким образом автоматически решается проблема, при которой вся область может быть отмечена как "проход". После проверки, мы выбираем случайное направление и делаем "вырубку" в эту сторону на два хода и конечный элемент помечается как "развилка". Если во время проверки обнаружилось, что направления у текущей "развилки" нет, то соответствующий флажок снимаем. Так цикл повторяется пока в массиве есть "развилки", после чего цикл будет завершен.

Постройка лабиринта на основе данных алгоритма:

using System.Collections;
using UnityEngine;

public class MazeGenerator : MonoBehaviour {

	[SerializeField] private int width;
	[SerializeField] private int height;
	[SerializeField] private SpriteRenderer sample;
	[SerializeField] private float sampleSize = 1;
	private int[,] map;

	void Start()
	{
		CreateMap();
	}

	public void Clear()
	{
		SpriteRenderer[] ren = GetComponentsInChildren<SpriteRenderer>();
		for(int i = 0; i < ren.Length; i++)
		{
			DestroyImmediate(ren[i].gameObject);
		}
	}
	
	public void CreateMap()
	{
		Clear();

		map = Maze.Generate(width, height); // генерируем лабиринт

		if(map == null) return;

		width = Maze.Round(width); // проверка на четные/нечетные
		height = Maze.Round(height);

		float posX = -sampleSize * width / 2f - sampleSize / 2f;
		float posY = sampleSize * height / 2f - sampleSize / 2f;
		float Xreset = posX;
		int z = 0;
		for(int y = 0; y < height; y++)
		{
			for(int x = 0; x < width; x++)
			{
				posX += sampleSize;
				SpriteRenderer clone = Instantiate(sample, new Vector3(posX, posY, 0), Quaternion.identity, transform) as SpriteRenderer;
				clone.transform.name = "Block-" + z;
				clone.color = (map[x, y] == 1) ? Color.white : Color.gray; // красим проходимые клетки в белый, а стены в серый цвет
				z++;
			}
			posY -= sampleSize;
			posX = Xreset;
		}
	}
}

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

Кнопка для редактора:

#if UNITY_EDITOR
using System.Collections;
using UnityEngine;
using UnityEditor;
[CustomEditor(typeof(MazeGenerator))]
public class MazeEditor : Editor {

	public override void OnInspectorGUI()
	{
		DrawDefaultInspector();
		MazeGenerator t = (MazeGenerator)target;
		GUILayout.BeginHorizontal();
		if(GUILayout.Button("Создать / Обновить")) t.CreateMap();
		if(GUILayout.Button("Очистить")) t.Clear();
		GUILayout.EndHorizontal();
	}
}
#endif

Отметим одну деталь, что с учетом того, что каждый цикл делается ход сразу на два клетки, то все развилки нам нужно делать на нечетных числах, так мы сохраняем закрытый вид лабиринта. Для проверки четности, есть отдельная функция. Например, если вы зададите размеры лабиринта 10х10, то он автоматом будет исправлен на 11х11.

Скачать демо:

Внимание! Посетители, находящиеся в группе Гости, не могут скачивать файлы.
Тестировалось на: Unity 2017.1.0

Комментариев 1

Офлайн
нормальные уроки как всегда в деле!
Информация
Посетители, находящиеся в группе Гости, не могут оставлять комментарии к данной публикации.
  • Яндекс.Метрика