Пользователь
0,0
рейтинг
15 апреля 2013 в 07:29

Разработка → Алгоритм Эллера для генерации лабиринтов перевод

Это топик-перевод статьи Eller's Algorithm. В ней рассказывается о способе программной генерации лабиринтов. Дальнейшее повествование идет от лица автора.

 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __  
|__   |__       __ __|__   |   __|  |  |  |  |
|__   |__   |__|   __ __|   __ __      |     |
|        |  |  |     |  |__      |__|  |  |  |
|__|__|  |  |   __|   __|__   |   __|__|  |__|
|   __|  |     |__ __ __|  |  |__|  |     |  |
|  |  |  |  |__|  |__   |  |   __|__ __|  |  |
|  |__    __    __ __    __|  |   __   |  |  |
|  |  |  |  |      __|  |   __|  |  |__|  |  |
|  |     |     |__   |  |  |  |  |  |__    __|
|  |  |__|__|__ __|  |     |  |  |      __|  |
|__ __|  |  |  |__   |__|   __|     |   __ __|
|   __|  |   __|__      |__   |__|  |__    __|
|  |  |     |  |     |__|  |   __    __|   __|
|   __|  |__ __|__|      __|  |  |     |  |  |
|   __ __   |      __|__|  |__   |  |  |__|  |
|__ __ __|__ __|__ __ __ __ __|__|__|__ __ __|


Алгоритм Эллера позволяет создавать лабиринты, имеющие только один путь между двумя точками. Сам по себе алгоритм очень быстр и использует память эффективнее, чем другие популярные алгоритмы (такие как Prim и Kruskal), требуя памяти пропорционально числу строк. Это позволяет создавать лабиринты большого размера при ограниченных размерах памяти.



В интернете очень мало информации об алгоритме Эллера. Лучший источник, который я смог найти (сайт Walter Pullen) имеет всего один параграф с описанием, которое полезно, но недостаточно для реализации алгоритма. Также, алгоритм описанный в книге Mathematics and Physics for Programmers, скорее всего, не работает. Я обдумал недостающие части и уверен, что алгоритм который я описал, в самом деле является алгоритмом Эллера. Кроме того, вы можете найти дополнительную информацию о нем в статье Maze Generation: Eller's Algorithm.

Описание алгоритма


Замечание: мы предполагаем, что самая левая ячейка имеет границу слева, а самая правая — справа.

  1. Создайте первую строку. Ни одна ячейка не будет являться частью ни одного множества.
  2. Присвойте ячейкам, не входящим в множество, свое уникальное множество.
  3. Создайте правые границы, двигаясь слева направо:
    1. Случайно решите добавлять границу или нет
      1. Если текущая ячейка и ячейка справа принадлежат одному множеству, то создайте границу между ними (для предотвращения зацикливаний)
      2. Если вы решили не добавлять границу, то объедините два множества в которых находится текущая ячейка и ячейка справа.
  4. Создайте границы снизу, двигаясь слева направо:
    • Случайно решите добавлять границу или нет. Убедитесь что каждое множество имеет хотя бы одну ячейку без нижней границы (для предотвращения изолирования областей)
      1. Если ячейка в своем множестве одна, то не создавайте границу снизу
      2. Если ячейка одна в своем множестве без нижней границы, то не создавайте нижнюю границу
  5. Решите, будете ли вы дальше добавлять строки или хотите закончить лабиринт
    1. Если вы хотите добавить еще одну строку, то:
      1. Выведите текущую строку
      2. Удалите все правые границы
      3. Удалите ячейки с нижней границей из их множества
      4. Удалите все нижние границы
      5. Продолжайте с шага 2
    2. Если вы решите закончить лабиринт, то:
      1. Добавьте нижнюю границу к каждой ячейке
      2. Двигаясь слева направо:
        1. Если текущая ячейка и ячейка справа члены разных множеств, то:
          1. Удалите правую границу
          2. Объедините множества текущей ячейки и ячейки справа
          3. Выведите завершающую строку


Пример


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

Шаг 1: Создание первой строки

	 ___ ___ ___ ___ ___ ___ ___ ___
	|                               |


Шаг 2: Присоединим все ячейки не принадлежащие множествам к свои новым множествам

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1   2   3   4   5   6   7   8 |


Шаг 3: Создадим границы справа

	 ___ ___ ___ ___ ___ ___ ___ ___
	|(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 |


Шаг 4: Создание нижних границ

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

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|


Шаг 5А: Создание новой строки

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 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  _1_ _1_  4  _4_  6   6  _6_|


Если ячейка имеет нижнюю границу, удалим ее из множества:

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1  ___ ___  4  ___  6   6  ___|


Удалим нижние границы

	 ___ ___ ___ ___ ___ ___ ___ ___
	| 1  _1_ _1_| 4  _4_| 6   6  _6_|
	| 1           4       6   6     |


Продолжая с шага 2:

Шаг 2: Присоединим ячейки, не принадлежащие множествам к своим уникальным множествам

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___| 
	| 1   2   3   4   5   6   6   7 |


Шаг 3: Добавим границы справа

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|(1 | 2)  3   4   5   6   6   7 | <-- добавлена граница


	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 |(2   3)  4   5   6   6   7 | <-- граница не добавлена, объединим множества 2 и 3


	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  (2   4)  5   6   6   7 | <-- граница не добавлена, объединим множества 2 и 4


	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2  (2 | 5)  6   6   7 | <-- добавлена граница


	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 |(5 | 6)  6   7 | <-- добавлена граница


Следующие две ячейки члены одного множества, поэтому мы ОБЯЗАНЫ добавить границу. Если не добавим, то это приведет к циклам в нашем лабиринте

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 |(6 | 6)  7 | <-- должны добавить границу


	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 |(6   7)| <-- граница не добавлена, объединим множества 6 и 7


Шаг 4: нижние границы

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2   2   2 | 5 | 6 | 6   6 |


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

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	| 1 | 2  _2_ _2_| 5 |_6_| 6  _6_|


Вы можете добавить столько строк, сколько захотите

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|_1_  1 | 3   3 | 7  _7_ _7_| 8 |


Шаг 5Б: Завершение лабирина

Последняя строка отличается от обычных тем, что 1) каждая ячейка имеет границу снизу 2) каждая ячейка должна принадлежать одному множеству.

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

Начнем с создания обычной строки и добавления нижней границы к каждой ячейке.

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_1_ _1_|_3_|_3_|_7_ _7_|_8_ _8_|


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

	 ___ ___ ___ ___ ___ ___ ___ ___
	|    ___ ___|    ___|        ___|
	|   |    ___ ___|   |___|    ___|
	|___    |       |    ___ ___|   |
	|_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_|


В конце должен получиться идеальный лабиринт, в котором нет циклов (между двумя ячейками есть только один путь) и изолированных частей (ячейки или групп ячеек, которые не связаны с другими частями лабиринта). Теперь вы можете назначить любые две ячейки соответственно «входом» и «выходом».
Перевод: Eller's Algorithm
Serg @deadkrolik
карма
67,2
рейтинг 0,0
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Реклама

Самое читаемое Разработка

Комментарии (34)

  • +3
    Хм, а с каких пор алгоритмы Прима и Краскала являются алгоритмами генерации лабиринтов? Нет, я понимаю, что генерация лабиринта — это по сути нахождение остовного дерева в графе, но лабиринты в таком случае будут получаться несколько… странными, особенно если используемая в одном из них сортировка случайно окажется устойчивой.
    • +10
      Я не силён в математике, но в XScreensaver лабиринты строятся обоими этими способами и выглядят круто.
  • +3
    А тут ещё давно лежал какой-то алгоритм генерации и обхода лабиринта. Примеры со статьи не работают, но пример 4 был взят для эксперимента и, как ни странно, запустился на коде 2006 года без правок.

    Пример: liveweave.com/17JST3, проверен в Хроме, Fx, Опера.

    Видно лишь, что не по алгоритму Эллера, но получается легко и занятно, видимо, случайным подбором.
  • +3
    Так мы что же, всегда делаем проход по нижней линии? Ведь состояния множеств из верхних линий мы в памяти не держим, что, как я понимаю, нам память и экономит…
    • +1
      Состояния множеств из верхних линий мы не держим в памяти не потому что экономим память, а потому что нам они не нужны — состояния текущей линии достаточно для принятия решения.
      • +2
        Да, но прохождение лабиринта насколько я понимаю будет сводиться к тому чтобы

        1) Пройти от выхода к нижней линии
        2) пройти от входа к нижней линии
        3) соединить точки (должно быть очень просто).
        • +1
          Нет. В нижней линии тоже могут быть стенки. Более того, данный алгоритм может выдать на выходе абсолютно любой корректный лабиринт, хотя и не все лабиринты равновероятны.
          • 0
            Да, но глобальный проход через все секции всегда будет через нижнюю линию — останется только банально перешагивать стенки.
            • +3
              Посмотрите на первый лабиринт в посте. Чтоб пройти из левой нижней ячейки в правую нижнюю, нужно дойти чуть ли не до самого верха.
              • +1
                Да, вы правы. Однако же я хочу заметить что в любом случае у нас все множества вертикальные и идут до самого низа, так что как только дошел до низа — дальше уже все все равно просто. Лабиринт бстро проходится методом правой руки.
                • +1
                  Любой лабиринт со связной стеной можно весь обойти, пользуясь методом правой руки.
                  • +1
                    Я это понимаю. Но тут на этом практически не теряется время, насколько я понимаю.
                    • +1
                      Не совсем понял, что вы хотите сказать. Этот маршрут однозначно не оптимален, и далеко не оптимален — можно пройти весь лабиринт просто чтобы попасть в соседнюю клетку, а это колоссальная потеря времени, если вы об этом.
                      • +1
                        Наверное вы правы.
  • +10
    Пару лет назад сделал такую программку, если кому интересно, можете скачать исходники: aivanov.com/maze-generator/
    или просто поиграться: aivanov.com/maze/ :)
    • +1
      А какой алгоритм был заложен в вашем коде: использовали что-то своё или готовое?
      • +5
        Сам придумал. Идея простая: создаются ветви определённой длины и по завершению начинаются новые ветви ближе к началу пути.
        Это больше похоже на дерево с ветвями и создаёт более сложные лабиринты, где много длинных ответвлений, по которым приходится возвращаться назад.

        Если взглянуть на примеры лабиринтов, построенные на алгоритме Эллера, то можно визуально найти путь за несколько секунд, если видишь весь лабиринт т.к. мало запутанности (очень короткие тупики).
        Также я рассматривал лабиринты, которые сделаны через рекурсию, но они получаются совсем дебильными — как правило, у них один длинный путь, который покрывает почти весь лабиринт и оооочень мало коротких ответвлений, которые по остаточному принципу созданы.
        В таких лабиринтах практически невозможно «заблудиться» :)
        • +2
          Ни на сайте, ни в самом коде не указано под какой лицензией вы его распространяете. Было бы удобно, если бы вы это уточнили.
          • +3
            В тексте есть пометка «вы можете скачать и использовать так, как захотите». Если моего слова будет достаточно, то обещаю только радоваться за тех, кому этот код будет полезен и никогда не предъявлю никаких претензий. Упоминания об авторстве совершенно не обязательны.
            Не хочется ради таких мелочей сейчас правками заниматься :)

            P.S. Кстати, там если включить режим анимации, то видно, что красными квадратиками показывается стек маршрута. Лишние точки (откуда уже нет пути ни в одном из 4-х направлений) можно убрать, чтобы занимало меньше памяти. Сделать просто проверкой в методе addRoute, но я не стал заморачиваться, т.к. это вопрос всего нескольких килобайт.

            P.P.S. В предыдущем комментарии я написал «создаются ветви определённой длины». На самом деле обманул. Такой вариант был, но я почему-то заменил на другой: создаётся ветвь, пока не зайдёт в тупик. Как только выхода нет — начинается ветвь как можно ближе к началу.
            • +1
              А подскажите, зачем вы делаете & (0xFFFF ^ direct) и & (0xFFFF ^ backDirect(direct)? Почему пометки как CELL_VISITED недостаточно?
              • +1
                Уф) Хороший вопрос. В обоих случаях идёт сброс бита в «0» отвечающего за стенку. Это можно было бы оптимизировать, но памяти тут не сэкономишь, если не паковать биты, поэтому я поступил довольно просто:
                — Ячейка массива содержит в себе информацию о стенах, которую её окружают (биты 1-4)
                — Если ячейка уже посещена генератором, то устанавливается бит 7
                — По умолчанию, весь массив состоит из одних стен (в каждой клетке 4 стенки)
                — Каждый ход «ломается» по одной стене, но бит гасится для двух соседних клеток. Т.е. если мы пошли вправо и сломали правую стенку, то нужно убрать бит правой стенки в данной клетке и убрать бит левой стенки в клетке справа.
    • 0
      Спасибо!
      Удивился, как быстро даже 33x34 прохожу. Остался навык из детства — очень любил лабиринты, научился некоторым хитростям :)
  • –12
    Простите. Но может быть все таки Эйлера?
    • +10
      Eller и Euler — это разные фамилии
      • +1
        Euler читается как Ойлер
        • +3
          Читается, как Ойлер, а по-русски всё равно Эйлер. То же и к Айнштайну относится, и к прочим немцам и швейцарцам. Трудности перевода.
  • +4
    На основе идеального алгоритма Эллера можно сделать кучу головоломок.
    Одна из них типа netwalk.
    Будет популярной под айпад (в айфон сетка 9 на 9 не влезет).
    Нужен дизайнер и успех обеспечен.
  • +1
    Я использовал такой алгоритм. (Возможно изобрёл чей то велосипед) :-)
    1. Рисуем рамочку лабиринта
    2. Генерируем список все нечётных координат внутри рамочки
    3. Случайно выбираем любую точку из списка (тут я использовал алгоритм случайного выбора без повторов).
    4. Если случайно выбранная клетка занята, то ничего не делаем. Иначе чертим в случайную сторону линию лабиринта не доходя до стены.
    5. Повторять с п. 3 пока список не опустеет.

    Модификации — прерывая черчение стены лабиринта на шаге 4 можно делать частично «пустые» лабиринты.
  • +4
    Вот очень хорошая ссылка на алгоритмы генерации лабиринтов: Think Labyrinth. Я когда-то реализовал один из первых в списке алгоритмов Recursive Backtracker. Этот алгоритм характерен тем, что получающиеся лабиринты могут иметь очень длинные тупиковые ответвления, так что проходить такой лабиринт вручную — сложная задача.

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

    Наличие циклов в лабиринте иногда бывает полезным. Например, это может запутать некоторые простые алгоритмы прохождения лабиринтов.
    • +3
      Ну, циклы-то получить просто — берем лабиринт без циклов и удаляем N стенок случайным образом. Правда, таким образом мы имеем больше шансов получить длинный цикл, чем короткий, но иногда это даже полезно.
  • +2
    Удивлён, что никто ещё не пошутил про это (лабиринт в пару строк JS, оригинальная идея была написана на терминалах, в одну строку). Изначально, конечно, сама идея шуточная. Там, конечно, речи нет ни о гарантированной полной связности лабиринта, ни о чём-то ещё детерминированном, т.к. рандом.
    Зато, например, настраивать «общую направленность» или степень заполнения можно уже там, а затем, для придания нужной формы и свойств, детерминированными методами склеивать отдельные участки лабиринта (с разной «общей направленностью»), а также «прорубать» проходы для обеспечения требуемой связности участков. Так, для восстановления связности можно выбирать не жадным способом, а именно минимальное число проходов; для связи между блоками — выбирать область с прицелом на наименьший (а может, лучше наибольший?) общий путь прохождения.

    … Или про это: генератор уровней для классических шутеров Oblidge.
    Кстати, автор последнего, уже без шуток, генерирует именно проходимые уровни. По своему опыту отмечу, что порой не такие уж и плохие, а иногда и вовсе неплохие. Особенно радует в нём функция «сгенерировать полный комплект уровней», которая создаёт целую игру (например, 32 уровня для второго дума), с возрастающими сложностью, размерами карт и количествами врагов, а также учитывает стилистические особенности отдельных уровней (map07, map30...). Впрочем, это уже очень узконаправленная штука. Да и упора на сложность лабиринта там особо никто не делал. Жду — не дождусь, когда автор всё-таки выведет из беты на сносный уровень HL1/CS16.

    А если без шуток, то да, очень занятно. Вкупе с материалом про прохождение лабиринта «в условиях тумана» (когда у программы нету карты) может получиться отличная пара (генератор лабиринтов-заданий и программы-Тесеи). Если с красивым визуализатором, то можно будет и speedrun-ы смотреть.
    • +1
      … Ещё, наверное, неплохо было бы рекурсивно применить эту рандомную процедурку уже для генерации квадратных блоков лабиринта разной скважности и направленности. Полученный лабиринт (где-нибудь 3х5 блоков), наверное, уже будет весьма интересной штуковиной.
  • +1
    Есть дырки, нет петель, но задача выполнена, вполне себе лабиринт, пусть и без входа и выхода.
    Самые интересные лабиринты получаются по алгоритмам никак не связанным с теорией графов.
  • 0
    Ломаю голову над последней строкой.

    У Вас в алгоритме в пункте 5 подразумевается, что если это последняя строка, то мы НЕ выполняем 5.1, а сразу переходим к 5.2, верно? Но в примере про последнюю строку написано так «Начнем с создания обычной строки...», это имеются в виду пункты 2, 3 и 4? Включая 5.1 или нет? Если возможно, напишите подробный план генерации именно последней строки с пункта использования предыдущей строки. Или хотя бы опишите порядок по номерам из Вашего алгоритма.

    Спасибо.

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