Документ: АиСД. Проектная работа, страницы 26-30

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

Для последнего ряда, мы соединяем первые две ячейки.

Вырезаем север и очистим набор.

Затем соединяем последние две ячейки:

И завершим это, добавив окончательное северное соединение:

26

1.1.12 Примеры лабиринтов

Следующие лабиринты сгенерированы алгоритмами генерации идеальных лабиринтов файла-программы perfect_maze.py (см. раздел «Код программы»).

Таблица 12

Алгоритм Олдоса–

Алгоритм Уилсона

Алгоритм двоичного

Бродера

дерева

█████████████████████

█

█ █ █ █

█ █ █

█

█ █████ ███ █████████

█ ███

█

█ █

███ █ █

█ ███ █

█████

█ ███ █

█ █

█

█ █

█ █ █ █ █ █

█

█ █

█ █ █

███ ███ █

███ █

█ █ █

█████ ███

█ █ █

█ █████

█

█████ █

███

█ █ █ █ █

█ █ █ █

█ █ █

█ █

█

█ █

█

█ █ █

███████ █

█ █ █

█ █ █████

███

█

█ █ █

█ ███ █

█

█ ███ █

█

█ █

█ █ █

█

█ █

█ █ █ █ █ █ █

█

█ █ █ █ █ █

█ █

█ ███

█ █ █ █ █

█████

█ ███

█

█ █

█

███ █

█ █ █ █████

█

█ █

███

█ █

█ █ █

█

█ █

█

█ █ █

█ █ █ █ █

███ ███ █ █████

█ █ █

█ █ ███████ ███████ █

█ ███████

█

█ █ ███

█

█ █ █

█ █

█

█ █

█

█ █ █ █ █ █

█ ███████ █ █ ███ █ █

█████████

███████ █ █

█ █ ███

███

█████████

█

█ █

█

█ █

█

█████

█ ███ ███

█ █ █

█ ███

███

█ ███

███ █

█ █ ███

█

█ ███ █

█

█ █

█

█ █ █

█ █

█ █ █

█

█ █ █ █ █ █ █

█ █

███ █████ ███ ███ █ █

█████

███

█ █

███████

█ █ █ ███

█

███

█ █

█

█ █ █

█

█ █

█

█ █ █

█ █

█ ███

█ ███████

███ █

█ █████

███████

█ █ █

█ █ █ ███

███

███ █ █

█

█ █ █ █

█ █ █

█

█ █ █

█████████████████████

Таблица 13

Алгоритм Recursive

Алгоритм рекурсивного

Алгоритм Эллера

Backtracking

деления

█████████████████████

█

█ █ █ █

█ █

█ █ █ █

█

█ █

█ █ ███ ███ ███████ █

█████

█

█ ███

█ █ █

█ █ █ ███

█

█ ███ █

█ █ █

█

█ █

█

█ █

█ █ █ █ █

█ █ █ █ █ █

█ █ █

███

█

███ ███ ███ ███

█ █ █

███

█ █ █

█ ███ █

█

███ █ █

█

█ █

█ █ █

█

█ █ █ █

█

█ █████ ███ ███

███ █

█ ███

█ █ █ █ █████ █

███ ███

█

███████

█ █

█ █ █ █

█

█ █

█

█ █ █ █

█ █ █

█ █ █ █ ███ █ █

███████████████████ █

███

█ █

█

███ █ █ █

█

█ █ █ █

█ █

█

█ █

█

█ █

█████████████ █

█ █ █

█ █ ███ █

█ ███

█████████

███

█ █ ███

█

█ █ █

█

█ █ █ █ █ █

█

█ █ █ █

█ ███

█ ███ █████ ███

███████ ███ █ █ █ ███

█ █ █ █

█████████ █ █

█

█ █

█

█ █

█

█ █ █ █ █ █ █ █

█ █

███ █████ ███████ █ █

█ █████ ███████

█████

█ █ █ █

█

███████

█

█ █ █

█ █

█ █ █ █

█

█ █ █

█

█ █

█ ███

█████████

███ █

█ █ █

█ █ █ ███ █ █ █

█ █ ███

█

█ █ █ █

█ █

█

█ █

█

█ █ █

█ █

█ █ █

█ █ █ █ █ █

█ █ ███ ███████

█ █ █

█ ███████ ███ ███ ███

███ █████

███

█ ███ █

█

█ █

█

█ █

█

█████████████████████

27

Таблица 14

Алгоритм растущего

Алгоритм Краскала

Алгоритм Прима

дерева

(упрощённый)

█████████████████████

█

█ █

█

█ █

█

█ █ █ █

█

█ █ █

█ █

█ █ █ █ ███ █ ███ █ █

█ ███████ █ ███ █ █ █

███ ███ █ █████ ███ █

█ █

█

█ █ █

█ █

█

█ █

█

█ █ █

█ █ █ █

█ █ █████████ ███ █ █

███ ███ █████ █████

█

███

███ █ █ ███ █ █ █

█ █

█

█ █ █

█

█ █ █ █ █ █

█████ ███ █ ███

███ █

█ █ ███ █ ███ ███ ███

███

█████ █ █ █ █ █ █

█

█ █ █

█

█ █

█ █ █ █

█

█ █

█

█ █████████ █ ███ █ █

█ █ █ █ ███ █ █ █ ███

███ █ █████ █████ ███

█ █

█

█ █

█ █ █ █

█

█ █ █

█

█ █

█ █ █ ███ █████████ █

█ █ ███ ███ █████ █ █

███

███ █ ███████ █ █

█ █ █

█

█ █ █ █ █ █ █

█ █

█

█ █ ███ ███ ███ ███ █

█ █ █ █ █ ███████ █ █

███████ █ █ █████ █ █

█

█ █ █ █

█

█ █ █ █ █ █

█

█ █ █

█ █ █ ███ ███ ███ █ █

███

█ ███ █ █████ █ █

█████ ███ ███ ███ █ █

█ █ █ █ █

█ █

█

█ █ █ █

█

█ █ █

███ █ █ █ █ █ █ ███ █

█ ███ █ █ █ █ █████

█

█████ █████ █ ███ █ █

█ █ █

█ █

█ █ █ █ █ █ █

█

█ █

█ █████ ███ █████ █ █

█ █ █ ███ █ █ █ █ █ █

█ ███████ ███ █ ███ █

█

█ █ █ █ █ █

█ █

█

█ █

█████████████████████

Таблица 15

Алгоритм Прима

Алгоритм Sidewinder

(модифицированный)

█████████████████████

█

█ █ █

█

███ ███ ███ █ █ █████

█████

█████ █ █ █████

█ █

█

█ █

█

█ █████ █ █ █ █ █████

███ █████ █ █ █ █ ███

█

█ █ █ █

█

█ █ █ █ █ █

█ █ ███ █████ ███████

█ ███████ █ █████ █ █

█ █ █

█

█ █

█ ███ █ █ █ ███ ███ █

███ █████ ███ █████ █

█ █ █ █ █ █

█

███ ███ █████ ███████

█████

█ ███████████ █

█ █

█

█ █ █ ███ ███████ ███

█ █ ███████████ █ ███

█

█ █ █

█

█ █ █ ███ █████ █ █ █

█ ███

███ ███ ███ █ █

█ █ █ █

█

█ █ █

█ █

█

█ █ █ █

█ █████████ ███ █████

█ █ ███ █████ █████ █

█

█ █

█

█ █ █

█ █

█

█████ ███ █ ███ █ █ █

█ █ █ █████ █████ ███

█

█ █ █ █

█ █ █

█

█ █

█████████████████████

28

1.2 Алгоритмы генерации неидеальных лабиринтов Неидеальный лабиринт — лабиринт с петлями и (возможно) с недостижимыми

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

Таблица 16. Алгоритмы генерации неидеальных лабиринтов

Алгоритм	%	Фокус	Отсутствует	Однородн	Память
Алгоритм	тупиков	Фокус	смещенность	ость	Память
	тупиков		смещенность	ость
Алгоритм
змеевидного	≈0	Проходы	Нет	Никогда	0
лабиринта	≈0	Проходы	Нет	Никогда	0
лабиринта
Решение: 26%
Алгоритм
маленьких	39	Проходы	Да	Никогда	0
комнат	39	Проходы	Да	Никогда	0
комнат
Решение: 2%
Алгоритм
спирального	≈0	Проходы	Нет	Никогда	C
лабиринта	≈0	Проходы	Нет	Никогда	C
лабиринта
Решение: 2%

1.2.1 Алгоритм змеевидного лабиринта Алгоритм змеевидного лабиринта — алгоритм генерации неидеального

лабиринта с циклами без недостижимых областей.

Алгоритм:

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

2.Выбираем направление движения (вверх – вправо – вниз – вправо / влево – вниз

–вправо – вниз).

3.В соответствии с направлением выбираем исходную ячейку (нижняя левая / верхняя правая).

4.Передвигаемся по лабиринту в первую сторону, прорезая стены.

5.Если достигли одного из краёв лабиринта:

•Если ячейка находится в нижнем правом углу, то генерация завершена, переход к №6.

•Делаем два шага по второй стороне.

•Передвигаемся по лабиринту в третью сторону, прорезая стены.

•Если достигли одного из краёв лабиринта:

o Если ячейка находится в правом нижнем углу, то генерация завершена.

o Сделаем два шага по четвертой стороне.

oПереходим к №4.

6.Прорезаем случайное количество стен в лабиринте.

Алгоритм тривиален, поэтому пример работы не приводится. Увидеть пример такого лабиринта можно в «1.2.4. Примеры лабиринтов».

1.2.2 Алгоритм маленьких комнат Алгоритм связанных маленьких комнат — алгоритм генерации неидеального

лабиринта с циклами без недостижимых областей.

Алгоритм:

29

1.Изначально все поле содержит стены, стартовая ячейка (0, 0).

2.Прорезаем две стены между текущей и следующей, и следующей и последующей ячейками.

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

4.Смещаемся на 4 ячейки вперёд от текущей.

5.Повторяем №2-4 пока не будет достигнут край.

6.Переходим на 2 строки вниз, к левой стороне лабиринта.

7.Повторяем №5-6 пока не будет достигнут нижний край.

8.Прорезаем случайное количество стен в лабиринте.

Алгоритм тривиален, поэтому пример работы не приводится. Увидеть пример такого лабиринта можно в «1.2.4. Примеры лабиринтов».

1.2.3 Алгоритм спирального лабиринта Алгоритм спирального лабиринта — алгоритм генерации неидеального

лабиринта с циклами без недостижимых областей.

Алгоритм:

1.Изначально все поле содержит стены, стартовая ячейка (0, 0).

2.Передвигаемся по лабиринту «вправо», прорезая стены.

•Если все соседи текущей ячейки были обработаны, то генерация завершена, переходим к №6.

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

3.Передвигаемся по лабиринту «вниз», прорезая стены.

•Если все соседи текущей ячейки были обработаны, то генерация завершена, переходим к №6.

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

4.Передвигаемся по лабиринту «влево», прорезая стены.

•Если все соседи текущей ячейки были обработаны, то генерация завершена, переходим к №6.

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

5.Передвигаемся по лабиринту «вверх», прорезая стены.

•Если все соседи текущей ячейки были обработаны, то генерация завершена, переходим к №6.

•Если достигли края лабиринта или стены со следующей уже обработанной ячейкой, переходим к №2.

6.Прорезаем случайное количество стен в лабиринте.

Алгоритм тривиален, поэтому пример работы не приводится. Увидеть пример такого лабиринта можно в «1.2.4. Примеры лабиринтов».

30

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

Смотрите также: