Материал: АиСД. Проектная работа
7.В последнем ряду: (1) объединяем смежные ячейки различных множеств, (2) не удаляем границу между двумя смежными ячейками одного множества.
Проблема этого алгоритма заключается в несбалансированности обработки разных краёв лабиринта; чтобы избежать пятен в текстурах нужно выполнять соединение и пропуск соединения ячеек в правильных пропорциях.
|
|
|
|
|
|
|
|
|
Таблица 7 |
|
|
|
|
|
|
|
|
|
|
||
Пример работы |
|
|
|
|
|
|
|
|||
|
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
Создаём первую строку |
| |
|
|
|
|
|
|
|
| |
|
|
|
|
|
|
|
|
|
|
|
|
Инициализируем ячейки первой строки, |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
чтобы каждая существовала в своем |
|
|||||||||
| |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 | |
||
собственном наборе |
||||||||||
|
|
|
|
|
|
|
|
|
||
|
|
___ ___ |
___ ___ ___ ___ ___ ___ |
|||||||
|
|(1 |
2) |
3 |
4 |
5 |
6 |
7 |
8 | |
||
Далее объединяем или создаем границы |
|
|
|
|
|
|
|
|
|
|
— выбор производится случайно. |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
| |
1 |
(1 |
3) |
4 |
5 |
6 |
7 |
8 | |
||
НО объединять ячейки одного набора |
||||||||||
|
|
|
|
|
|
|
|
|
||
нельзя! (Первой строки не касается.) |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
|
| 1 1 |
(1 | 4) 5 6 7 8 | |
||||||||
|
|
|
|
|
… … … |
|
|
|
||
Результат |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
| 1 1 1 | 4 4 | 6 6 6 | |
||||||||||
|
||||||||||
Добавляем нижние границы. |
|
|
|
|
|
|
|
|
|
|
Убедимся, что каждый набор имеет хотя |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
бы одну ячейку без нижней границы. |
|
|||||||||
| 1 _1_ _1_| 4 |
_4_| 6 |
6 _6_| |
||||||||
Если это условие не будет выполнено, |
||||||||||
|
|
|
|
|
|
|
|
|
||
то мы создадим изолированные области. |
|
|
|
|
|
|
|
|
|
|
Перемещаем на следующий ряд те |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
ячейки наборов, которые не имели |
| 1 |
_1_ |
_1_| 4 |
_4_| 6 |
6 |
_6_| |
||||
нижних границ. |
| 1 |
|
|
4 |
|
6 |
6 |
| |
||
|
|
|
|
|
|
|
|
|
||
Присоединим ячейки, не |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
принадлежащие множествам к своим |
| |
|
___ |
___| |
|
___| |
|
|
___| |
|
уникальным множествам |
| |
1 |
2 |
3 |
4 |
5 |
6 |
6 |
7 | |
|
|
|
|
|
|
|
|
|
|
||
|
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
Далее объединяем или создаем границы |
| |
|
___ |
___| |
|
___| |
|
|
___| |
|
— выбор производится случайно. |
|(1 | 2) |
3 |
4 |
5 |
6 |
6 |
7 | |
|||
|
|
|
|
|
… |
|
|
|
||
НО объединять ячейки одного набора |
|
|
|
|
|
|
|
|
||
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
|||||||
нельзя! |
| |
|
___ |
___| |
|
___| |
|
|
___| |
|
|
| 1 | 2 |
2 |
2 |(5 | 6) |
6 |
7 | |
|||||
Следующие две ячейки — члены одного |
|
|
|
|
|
|
|
|
|
|
набора, поэтому мы должны добавить |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
| |
|
___ ___| |
|
___| |
|
|
___| |
|||
границу. Если не добавим, то это |
|
|
|
|
||||||
| 1 | 2 |
2 |
2 | 5 |(6 | 6) |
7 | |
|||||||
приведет к циклам |
|
|
|
|
|
|
|
|
|
|
|
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
6 и 7 объединяем |
| |
|
___ |
___| |
|
___| |
|
|
___| |
|
|
| 1 | 2 |
2 2 | 5 | 6 |(6 |
7)| |
|||||||
Добавляем нижние границы. |
|
___ ___ |
___ ___ |
___ ___ ___ ___ |
||||||
Убедимся, что каждый набор имеет хотя |
| |
|
___ |
___| |
|
___| |
|
|
___| |
|
бы одну ячейку без нижней границы. |
| 1 | 2 |
_2_ _2_| 5 |_6_| 6 _6_| |
||||||||
|
|
|
|
|
|
|
|
|
||
16
Пример работы
Таким образом мы можем добавить |
|
|
|
|
|
||||||
столько строк, сколько захотим |
___ ___ |
___ ___ ___ ___ ___ ___ |
|||||||||
Номера множеств сами по себе роли не |
| |
___ ___| |
___| |
___| |
|||||||
| |
| |
___ ___| |
|___| |
___| |
|||||||
играют, поэтому их можно менять на те, |
|||||||||||
| 1 |
1 | 3 3 | 7 7 | 8 |
8 | |
|||||||||
которых нет в текущей строке. |
|
|
|
|
|
||||||
|
|
|
… |
|
|
|
… |
|
|||
|
Завершение лабиринта. |
|
|
|
|
|
|||||
Последняя |
строка |
отличается от |
|
|
|
|
|
||||
обычных тем, что: |
|
|
|
|
|
|
|
||||
1) Каждая ячейка имеет границу снизу. |
___ ___ |
___ ___ ___ ___ ___ ___ |
|||||||||
2) Каждая ячейка должна принадлежать |
| |
___ ___| |
___| |
___| |
|||||||
| |
| |
___ ___| |
|___| |
___| |
|||||||
одному множеству. |
|
|
|||||||||
|
|
|___ |
| |
| |
___ ___| |
| |
|||||
В последнем ряду: (1) объединяем |
|_1_ _1_|_3_|_3_|_7_ _7_|_8_ _8_| |
||||||||||
смежные ячейки различных множеств, |
|
|
|
|
|
||||||
(2) не удаляем границу между двумя |
|
|
|
|
|
||||||
смежными ячейками одного множества. |
|
|
|
|
|
||||||
|
___ ___ ___ ___ ___ ___ ___ ___ |
___ ___ |
___ ___ ___ ___ ___ ___ |
||||||||
| |
|
___ ___| |
___| |
___| |
| |
___ |
___| |
___| |
___| |
||
| |
| |
|
___ ___| |
|___| |
___| |
| |
| |
___ ___| |
|___| |
___| |
|
|___ |
| |
| |
___ ___| |
| |
|_ _ |
| |
| |
___ ___| |
| |
||
|_1_ (1_|_3)|_3_|_7_ _7_|_8_ _8_| |
|_1_ _1_ |
_1_|(1_|_7) _7_|_8_ _8_| |
|||||||||
|
___ ___ ___ ___ ___ ___ ___ ___ |
___ ___ |
___ ___ ___ ___ ___ ___ |
||||||||
| |
|
___ ___| |
___| |
___| |
| |
___ |
___| |
___| |
___| |
||
| |
| |
|
___ ___| |
|___| |
___| |
| |
| |
___ ___| |
|___| |
___| |
|
|___ |
| |
| |
___ ___| |
| |
|___ |
| |
| |
___ ___| |
| |
||
|_1_ _1_ _1_|_1_ _1_ (1_|_8) _8_| |
|_1_ _1_ _1_|_1_ _1_ _1_ _1_ _1_| |
||||||||||
1.1.7 Алгоритм растущего дерева Алгоритм растущего дерева — обобщённый алгоритм, способный создавать
лабиринты с разной текстурой. Требуемая память может достигать размера лабиринта.
Алгоритм:
1.Изначально все поле содержит стены.
2.Пусть будет списком ячеек, изначально пустым.
3.Добавляем любую ячейку к .
4.Берем ячейку из и прорезаем проход к любому не посещённому соседу этой ячейки, добавив этого соседа также в . Если соседей нет, удаляем текущую ячейку из .
5.Повторяем №4, пока не станет пустым.
Интересно в алгоритме то, что в зависимости от способа выбора ячейки из списка можно создавать множество разных текстур. Например, если всегда выбирать последнюю добавленную ячейку, то этот алгоритм превращается в Recursive Backtracking. Если всегда выбирать ячейки случайно, то он ведёт себя похоже (но не одинаково) на алгоритм Прима. Если всегда выбирать самые старые ячейки, добавленные в список, то мы создадим лабиринт с наименьшим возможным показателем текучести, даже ниже, чем у алгоритма Прима. Если обычно выбирать самую последнюю ячейку, но время от времени выбирать случайную ячейку, то лабиринт будет иметь высокий показатель текучести (короткое и прямое решение).
17
Если случайно выбирать одну из самых последних ячеек, то лабиринт будет иметь низкий показатель текучести (долгое и извилистое решение).
Таблица 8
Пример работы
Будем использовать метод выбора ячеек «выбрать самую новую».
Алгоритм начинается с добавления произвольной ячейки в список.
Кроме того, ячейки красного цвета находятся в списке «живых» ячеек; они станут белыми, как только они будут удалены из списка.
Далее мы выбираем новую ячейку из списка, случайным образом выбираем одного из ее не посещённых соседей, вырезаем путь к ней и добавляем соседа в список.
Давайте сделаем это снова, еще раз выбрав самую новую ячейку из списка:
Видите образец? Всегда выбирая ячейку, последнюю из которых добавили в список, каждый последующий шаг просто продлевает переход еще на один шаг, эффективно выполняя случайный обход. Но как ведет себя алгоритм, когда переход не может быть расширен дальше?
Давайте перенесемся немного вперед и посмотрим на поведение.
Еще шесть итераций, и мы зашли в тупик
вячейке № 9.
Вэтот момент алгоритм выберет самую новую ячейку №9, а затем попытается
найти соседнюю ячейку, которая не посещалась. Нет ни одной!
Итак, клетка №9 удалена из списка .
18
Пример работы
Затем алгоритм снова обходит, отбирая самую новую ячейку из списка. На этот раз это №8, и, конечно же, есть соседняя не посещённая ячейка, в которую мы можем перейти:
Шаг 8→10 не был преднамеренным; просто случилось так, что алгоритм выбора ячейки был тем же, что и алгоритм возврата. Вместо этого мы могли бы выбрать не 8, а любую другую, если бы мы использовали метод выбора ячеек «выбрать случайную». Таким образом алгоритм будет продолжать генерацию лабиринта до тех пор, пока каждая ячейка не будет посещена.
1.1.8 Алгоритм Краскала Алгоритм Краскала — алгоритм, создающий минимальное связующее дерево.
Он не «выращивает» лабиринт подобно дереву, а скорее вырезает проходы по всему лабиринту случайным образом, и тем не менее в результате создаёт идеальный лабиринт. Для его работы требуется объём памяти, пропорциональный размеру лабиринта, а также возможность перечисления каждого ребра или стены между ячейками лабиринта в случайном порядке (обычно для этого создаётся список всех рёбер и перемешивается случайным образом).
Алгоритм:
1.Изначально все поле содержит стены.
2.Помечаем каждую ячейку уникальным идентификатором.
3.Добавляем все ребра в множество .
4.Берем случайное ребро из множества .
•Если ячейки с обеих сторон от взятого ребра имеют разные идентификаторы, то удаляем ребро (из и в лабиринте) и задаем всем ячейкам с одной стороны тот же идентификатор, что и ячейкам с другой.
•Если ячейки с обеих сторон от взятого ребра имеют одинаковые идентификаторы, то между ними уже существует какой-то путь, поэтому текущее ребро пропускаем (удаляем только из ).
5.Повторяем №4, пока множество не станет пустым.
Примечание. Объединение двух множеств по обеим сторонам стены будет медленной операцией, если у каждой ячейки есть только номер и они объединяются в цикле. Объединение, а также поиск можно выполнять почти за постоянное время благодаря использованию алгоритма объединения-поиска (union-find algorithm): помещаем каждую ячейку в древовидную структуру, корневым элементом является идентификатор. Объединение выполняется быстро благодаря сращиванию двух деревьев. При правильной реализации этот алгоритм работает достаточно быстро, но медленнее большинства из-за создания списка рёбер и управления множествами.
19
Таблица 9
Пример работы
Выбираем ребро случайным образом и соединяем ячейки, которые он соединяет, если они еще не соединены путем. Мы можем знать, подключены ли ячейки, если они находятся в одном наборе.
Итак, давайте выберем грань между (2, 2) и (2, 3). Ячейки находятся в разных наборах, поэтому мы объединяем их в один набор и соединяем ячейки.
Давайте сделаем еще несколько проходов алгоритма, чтобы перейти к интересной части:
Обратите внимание, что происходит с ребром между (2, 1) и (2, 2).
Два дерева и , были объединены в один набор .
Объединяем (1, 2) и (1, 3).
Теперь рассмотрим ребра
(1, 1) – (1, 2) и (1, 2) – (2, 2)
В обоих случаях ячейки по обе стороны После еще одного прохода у нас будет: от ребер принадлежат одному и тому же
набору. Соединение ячеек в любом случае приведет к циклу, поэтому мы
20