Генератор лабиринта алгоритма Эллера

Алгоритм Эллера — это алгоритм генерации лабиринтов, который эффективно создает идеальные лабиринты (лабиринты без петель и с одним путем между любыми двумя точками) с использованием подхода «строка за строкой». Он создает лабиринты, похожие на алгоритм Краскала, но делает это, генерируя только одну строку за раз, без необходимости хранить весь лабиринт в памяти. Это делает его полезным для создания очень больших лабиринтов на очень ограниченных системах и для процедурной генерации контента.

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

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

Об алгоритме Эллера

Алгоритм Эллера был представлен Дэвидом Эллером.

Алгоритм примечателен своим эффективным подходом к генерации лабиринтов построчно, что делает его идеальным для бесконечных лабиринтов или лабиринтов, генерируемых в реальном времени. Он часто цитируется в литературе по процедурной генерации контента и генерации лабиринтов, но мне не удалось найти первичные источники, подробно описывающие его оригинальную публикацию.

Как работает алгоритм Эллера для генерации лабиринтов

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

Теоретически его можно использовать для генерации бесконечных лабиринтов, однако для того, чтобы гарантировать, что сгенерированный лабиринт действительно разрешим, необходимо в какой-то момент переключиться на логику «последнего ряда», чтобы завершить лабиринт.

Шаг 1: Инициализация первой строки

• Присвойте каждой ячейке в строке уникальный идентификатор набора.

Шаг 2: Соедините несколько соседних ячеек по горизонтали.

• Случайным образом объединяйте соседние ячейки, устанавливая для них одинаковый идентификатор набора. Это гарантирует наличие горизонтальных проходов.

Шаг 3: Создание вертикальных соединений со следующим рядом.

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

Шаг 4: Переход к следующей строке.

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

Шаг 5: Повторяйте шаги 2–4, пока не достигнете последнего ряда.

• Продолжайте обработку строка за строкой.

Шаг 6: Обработка последнего ряда

• Убедитесь, что все ячейки в последней строке принадлежат одному набору, объединив все оставшиеся отдельные наборы.

Дополнительное чтение

Если вам понравился этот пост, вам также могут понравиться эти предложения:

• Рекурсивный генератор лабиринтов с обратным отслеживанием
• Генератор лабиринтов на основе алгоритма Уилсона
• Генератор лабиринтов с алгоритмом растущего дерева