Видел кто-нибудь быстрый алгоритм динамической генерации бесконечного пещерного лабиринта?

Question

[Александр Синицын]

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

Может кто подскажет название готового алгоритма, работающего по такой схеме, или направление в котором рыть инфу для построения нужной пещеры ))

Answer 1

[xmoonlight]

Условие простое: чтобы всегда был выход нужно сохранять зазор разворота - минимум 2 тоннеля рядом. Разворот - делать вдоль своего "тела" наружу, чтобы не упереться в тупик.
(Т.е., тут алгоритм предотвращения запутывания змейки)

Answer 2

[dollar]

Вроде тот же алгоритм, с той лишь разницей, что генерация ведется не до тех пор, когда пространство для генерации кончится, а до тех пор, когда будет достигнута заданная глубина (или расстояние) от текущей позиции.

А дальше начинаются оптимизационные моменты, которые зависят от нюансов задачи. К примеру, в 2D вам, скорее всего, нужно заполнить экран и немного за экраном. А в 3D прямой коридор придется делать бесконечно, пока он наконец не повернет, ведь пользователь от первого лица должен увидеть конец коридора, а не пустоту, каким бы длинном он ни был.

Далее не понятно, как вы данные храните. Если у вас нет поля заданного размера, то хоть какое-то поле есть? Или каждая клетка/комната/соединение у вас представлены отдельным объектом в куче? И лабиринт по сути не сетка, а граф? От этого алгоритм тоже зависит.

Comments

[Александр Синицын]

Лабиринт самый простой, скорее даже не лабиринт, а бесконечная пещера по клеткам или прорытый ход без ответвлений, которые генерируются не заранее, а по мере продвижения.

Хранение одномерный массив с направлениями (вперед, влево, вправо) для 2D-визуализации.

Понимаю, что каждый ход можно генерировать рендомайзом, но надо как-то избегать петель в стену и тупиков из которых нет свободных направлений. Первое можно отсеять отбрасывая ячейки, уже находящиеся в массиве и ходить по свободным направлениям. Второе сложнее... тут у меня тупик )

[dollar]

А какой ограничитель генерации? Т.е. по какому критерию генерация останавливается и ожидает изменения ситуации?

Насчет формата не до конца понял. К примеру, хранится направление "вправо" в ячейке массива с индексом 5, и какой это имеет смысл?

[Александр Синицын]

dollar, Ограничитель пещеры - пользователь, как перестал двигаться вперед, создание пещеры прекращается.

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

[Руслан .]

Александр Синицын, Можно попробовать задавать ячейку не двумя координатами, а тремя.
Третья координата - номер слоя.
Т.е. строим лабиринт случайным образом, но как только наступает самопересечение увеличиваем номер слоя на единицу и начинаем все с чистого листа и с координаты, где наступило пересечение.

Answer 3

[Александр Скуснов]

Если есть формула, то по аналогии с фракталами (можно и генератор случайных чисел подключить).

Comments

[xmoonlight]

Ролик - супер: КРАСОТИЩА! Почему такая малая глубина?! Хочу ЕЩЁ на пару часиков!!!
Вот :)