Как генерировать тета-лабиринт?

Question

[Станислав Иванов]

Добрый день, недавно начал работать над игрой, где игроку в общих словах необходимо искать выход в лабиринте. Решил реализовать несколько их видов, удалось сделать прямоугольный и омега-лабиринт в виде треугольника. Наткнулся также на статью про виды лабиринт, среди них был тета-лабиринт в виде окружности, однако далее в статье не приводится описание алгоритма по его построению. Не подскажите ли каким образом можно реализовать подобное?

https://habr.com/ru/post/445378/

Comments

[Сергей Соколов]

идея: круглый спиралевидный лабиринт: сетка как рулон толстого скотча.

Answer 1

[Григорий Боев]

Примерно так же, как строятся классические лабиринты:
1) Разбить круг на окружности и секторы, образуется сетка узловых точек
2) Начинать на любой пустой узловой точке(которая не имеет пересечения с готовым лабиринтом), двигаться в случайном направлении (в пределах сетки).
3) Двигаться пока не упрёшься в стену
4) Перейти на п.2 и повторять пока не останется пустых узловых точек (или по таймауту)
Делал на Pascal в 8м классе игру "Лабиринт" на этом принципе, вполне работало.

PS: запустил этот древний код, вот такие лабиринты строит:

Comments

[Николай Савельев]

С прямоугольными понятно, а как быть с круговыми?

[Григорий Боев]

Точно так же. Двигайтесь не по декартовым координатам, а по полярным.

[Сергей Соколов]

Григорий Боев, упростили. С полярными угловая детализация зависит от радиуса. Дискретно, шагами. На рисунке в вопросе видны «волны» уплотнения-разрежения по мере удаления от центра

[Alexandroppolus]

Сергей Соколов, там на 10 круге количество секторов удваивается. И, похоже, ещё на третьем и шестом.

[Сергей Соколов]

Alexandroppolus, да, интересно как можно по чуть-чуть поднимать число клеточек на каждом круге. Угол между короткой радиальной стенкой и идеальным радиусом почти не будет заметен.

Answer 2

[Griboks]

Как вариант вы можете использовать уже реализованный вам алгоритм для прямоугольника, просто замкнуть его по горизонтали. После генерации выполнить преобразование координат вершин.

Answer 3

[mayton2019]

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

Это мне кажется интересная часть задачи которую можно обсудить. Остальное - уже решено.

Comments

[Сергей Соколов]

хороший комментарий. Но не ответ.

[mayton2019]

В роли коррекции может выступать длина окружности. По сути нам надо разбить круг на набор бубликов (количество и ширина задается как пользовательские параметры). Далее рассматривать эти бублики как независимые графы которые имеют точки соединения на границах бубликов.