Генератор лабиринта алгоритма Эллера
Опубликовано: 16 февраля 2025 г. в 20:02:05 UTC
Генератор лабиринтов, использующий алгоритм Эллера для создания идеального лабиринта. Этот алгоритм интересен тем, что он требует только сохранения текущей строки (а не всего лабиринта) в памяти, поэтому его можно использовать для создания очень, очень больших лабиринтов даже на очень ограниченных системах.Eller's Algorithm Maze Generator
Алгоритм Эллера — это алгоритм генерации лабиринтов, который эффективно создает идеальные лабиринты (лабиринты без петель и с одним путем между любыми двумя точками) с использованием подхода «строка за строкой». Он создает лабиринты, похожие на алгоритм Краскала, но делает это, генерируя только одну строку за раз, без необходимости хранить весь лабиринт в памяти. Это делает его полезным для создания очень больших лабиринтов на очень ограниченных системах и для процедурной генерации контента.
Идеальный лабиринт - это лабиринт, в котором есть ровно один путь из любой точки лабиринта в любую другую точку. Это значит, что вы не сможете ходить по кругу, но часто будете сталкиваться с тупиками, вынужденными разворачиваться и идти обратно.
Созданные здесь карты лабиринтов включают в себя версию по умолчанию без стартовых и финишных позиций, так что вы можете решить их сами: из любой точки лабиринта в любую другую найдется решение. Если вам нужно вдохновение, вы можете включить предлагаемые стартовую и финишную позиции - и даже увидеть решение между ними.
Об алгоритме Эллера
Алгоритм Эллера был представлен Дэвидом Эллером.
Алгоритм примечателен своим эффективным подходом к генерации лабиринтов построчно, что делает его идеальным для бесконечных лабиринтов или лабиринтов, генерируемых в реальном времени. Он часто цитируется в литературе по процедурной генерации контента и генерации лабиринтов, но мне не удалось найти первичные источники, подробно описывающие его оригинальную публикацию.
Как работает алгоритм Эллера для генерации лабиринтов
Алгоритм Эллера обрабатывает одну строку за раз, поддерживая и изменяя наборы связанных ячеек. Он обеспечивает связность, избегая петель, и эффективно расширяет лабиринт вниз.
Теоретически его можно использовать для генерации бесконечных лабиринтов, однако для того, чтобы гарантировать, что сгенерированный лабиринт действительно разрешим, необходимо в какой-то момент переключиться на логику «последнего ряда», чтобы завершить лабиринт.
Шаг 1: Инициализация первой строки
- Присвойте каждой ячейке в строке уникальный идентификатор набора.
Шаг 2: Соедините несколько соседних ячеек по горизонтали.
- Случайным образом объединяйте соседние ячейки, устанавливая для них одинаковый идентификатор набора. Это гарантирует наличие горизонтальных проходов.
Шаг 3: Создание вертикальных соединений со следующим рядом.
- Для каждого набора, который появляется в строке, по крайней мере одна ячейка должна быть соединена сверху вниз (для обеспечения связности).
- Случайным образом выберите одну или несколько ячеек из каждого набора для соединения со следующей строкой.
Шаг 4: Переход к следующей строке.
- Перенесите вертикальные связи, присвоив тот же идентификатор набора соответствующим ячейкам ниже.
- Назначьте новые идентификаторы наборов всем неназначенным ячейкам.
Шаг 5: Повторяйте шаги 2–4, пока не достигнете последнего ряда.
- Продолжайте обработку строка за строкой.
Шаг 6: Обработка последнего ряда
- Убедитесь, что все ячейки в последней строке принадлежат одному набору, объединив все оставшиеся отдельные наборы.