Материал: АиСД. Проектная работа

1.1.1 Алгоритм Олдоса – Бродера Алгоритм Олдоса–Бродера — однородный алгоритм, то есть он с равной

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

Алгоритм:

1.Изначально все поле содержит стены.

2.Выбираем любую ячейку.

3.Перемещаемся в любую соседнюю ячейку в пределах поля.

4.Если мы попали в не вырезанную ячейку, то вырезаем в неё проход из предыдущей.

5.Пока не вырежем проходы во все ячейки (пока все ячейки не будут посещены), повторяем №3-4: продолжаем двигаться в соседние ячейки, пока не вырежем

проходы во все ячейки.

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

Таблица 2

Пример работы

Выбираем ячейку наугад

Идем к соседу

Поскольку соседа раньше не посещали, вырезаем проход между ними

Выбираем случайного соседа и делаем проход по нему.

Поскольку сосед был посещен ранее, мы не вырезаем проход к нему из предыдущей ячейки.

6

Пример работы

Далее по аналогии

1.1.2 Алгоритм Уилсона Алгоритм Уилсона — усовершенствованная версия алгоритма Олдоса-Бродера,

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

Алгоритм:

1.Изначально все поле содержит стены.

2.Выбираем любую ячейку и добавляем ее в UST.

3.Выбираем любую ячейку, которой еще нет в UST, и выполняем случайную прогулку, пока не встретим ячейку, которая находится в UST.

4.Добавляем ячейки и ребра, затронутые в случайном блуждании, к UST.

5.Повторяем №3-4, пока все ячейки не будут добавлены к UST.

UST (uniform spanning trees) — однородные остовные деревья. Остовное дерево — это дерево, которое соединяет все вершины графа.

Однородное остовное дерево — это любое из возможных остовных деревьев графа, выбранное случайным образом и с равной вероятностью.

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

7

Таблица 3

Пример работы

Начинаем со случайного добавления ячейки в лабиринт

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

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

Все остальные ячейки, которые были посещены во время прогулки, но которые не сделали «окончательный срез», просто сбрасываются.

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

8

Пример работы

Затем мы идем по пути и снова добавляем ячейки и ребра в лабиринт

К настоящему времени паттерн становится виден: каждый проход добавит еще одну случайную «ветвь» к дереву, пока все ячейки не будут добавлены в лабиринт.

1.1.3 Алгоритм двоичного дерева Алгоритм двоичного дерева — это самый простой и быстрый из возможных

алгоритмов. Однако создаваемые лабиринты имеют текстуру с очень высокой смещённостью.

Алгоритм:

1.Изначально все поле содержит стены.

2.Для каждой ячейки в сетке случайным образом разделяем проход на север или

запад (север или восток / юг или запад / юг или восток).

Причем: любой выбранный вами диагональный набор должен использоваться последовательно во всем лабиринте.

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

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

9

Таблица 4

Пример работы

Поскольку этот алгоритм не должен учитывать состояние каких-либо соседних ячеек, мы можем начать с любого угла.

Начнем с верхнего левого.

Для первой строки мы вырезаем весь проход.

Вырезать весь проход по первому столбцу можно сразу. Мы будем делать это последовательно.

Идем сверху-вниз, слева-направо. Подкидываем монетку — прорезаем

сверху-вниз. Могло быть так: (Мы могли бы прорезать слева-направо,

как представлено на втором рисунке.)

Далее снова подкидываем монетку. Прорезаем слева-направо.

10