@Gebrauchsanweis

Алгоритм Эллера для генерации лабиринтов генерирует петли

Стараюсь на java написать генератор лабиринтов с использованием алгоритма Эллера, алгоритм смотрел здесь: habrahabr.ru/post/176671

Исходя из того, что встретил ещё сайт, где лабиринт по этому алгоритму строится нормально, значит мой косяк, но там код на java script и я ничего не понял :(

вот какие куски у меня получаются не правильно:
(точками пустые места обозначаю, иначе пробелы схлопываются)
первый:
__ __ __
|__ .... ....|
|.... .... ....|

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

второй:
__ __ __
|__ .... ....|
|__ ....|....|
|....|.... ....|
в этом куске в первом ряду множества опять 1 1 1, во втором 4 4 1, т.е. множества разделяются, но в третьей строке они снова объединяются (5 4 4), что приводит к петле.

Подскажите, пожалуйста, какое условие я пропустил?
  • Вопрос задан
  • 6039 просмотров
Пригласить эксперта
Ответы на вопрос 1
Deerenaros
@Deerenaros
Программист, математик, задрот и даже чуть инженер
Читал про алгоритм Эллера, так и не понял его красоту. Имхо, намного лучше использовать обход в глубину и в качестве лабиринта использовать остовное дерево. В коде увидеть его можно здесь (извиняюсь за ужасный код).
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы