Алгоритм Эллера

Алгоритм Эллера — это математический генератор, позволяющий создавать лабиринты, в которых между каждыми двумя точками существует единственный путь, то есть лабиринты не содержат циклов.[1] По сравнению с другими генераторами, этот алгоритм является одним из самых быстрых и требует небольшое количество оперативной памяти — пропорциональную длине строки лабиринта. Нужно хранить в памяти только последний созданный ряд, что позволяет генерировать лабиринты с неограниченным количеством рядов.

Описание

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

Примечания
  1. Алгоритм Эллера для генерации лабиринтов / Хабр

Ссылки
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.