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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Шаг 4: Перейдите к следующему ряду

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

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

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

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

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

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

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

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