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

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

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

СсылкиПравить

• Eller’s Algorithm (англ.)