Генерация лабиринта и его прохождение

samuel_unknown 29.11.2014 4 Комментарии

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

Генерация

Генерировать мы будем методом «рекурсивного деления».

1. Комната делится на 4 секции
2. На любых трёх границах прорезаются двери в произвольных местах
3. Рекурсивно выполняем 1. и 2. пункты для каждой из четырёх полученных секций, рекурсия не выполняется в тех секциях в которых хотя бы одна из сторон оказывается равной 1 ячейке.

В результате получится вот такой лабиринт:

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

Поиск пути между двумя точками

Поиск пути между двумя точками мы будем производить алгоритмом Ли (алгоритм волновой трассировки).

1. Путь ищем от красной точки до жёлтой
   
2. Зададим всем ячейкам кроме тех в которых находятся точки одинаковый атрибут = -1. Исходной точке атрибут = 0, конечной = -2.
3. «Распространяем волну»: все ячейки соседние с исходной меняют значение своего атрибута на значение атрибута исходной ячейки + 1 (т.е. на 1), но только в том случае, если в соседнюю ячейку можно беспрепятственно перейти из исходной.Продолжаем распространение волны: теперь для всех ячеек с атрибутом = 1 (т.е. для тех ячеек в которые удалось перейти из исходной) производим ту же операцию, вокруг таких ячеек появятся ячейки с атрибутом равным 2.Операцию продолжаем до тех пор, пока не попадём в конечную точку.
   
4. Восстанавливаем путь: движемся от конечной точки по тем ячейкам, атрибут которых меньше на единицу атрибута ячейки в которой находимся в данный момент. При этом учитываем, что перемещаться в новую ячейку можно только при условии отсутствия барьеров.

Дабы не загромождать статью кодом, вот ссылка на исходники программы:  https://Samuel-Unknown@bitbucket.org/Samuel-Unknown/maze.git