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

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

Генерация

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

Recursive-division-method

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

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

RDM-1

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

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

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

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

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

 

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

  1. Александр

    При компиляции кода выбивает :»-1: ошибка: [ui_mainwindow.h] Error 216″ как от неё избавиться?

    Qt 5.2.1 windows 7 x64

    1. samuel_unknown (Автор записи)

      Хм.. у меня всё без ошибок собирается. Посмотри что редактор выводит в «консоль сборки».. + погугли «[ui_mainwindow.h] Error 216»

  2. shpik

    Откудо исходники или сам написал ??

    1. samuel_unknown (Автор записи)

      Сам

Добавить комментарий для Александр Отменить ответ

Ваш адрес email не будет опубликован. Обязательные поля помечены *

Капча * Лимит времени истёк. Пожалуйста, перезагрузите CAPTCHA.

Этот сайт использует Akismet для борьбы со спамом. Узнайте, как обрабатываются ваши данные комментариев.