Видел кто-нибудь быстрый алгоритм динамической генерации бесконечного пещерного лабиринта?
Условие простое: чтобы всегда был выход нужно сохранять зазор разворота - минимум 2 тоннеля рядом. Разворот - делать вдоль своего "тела" наружу, чтобы не упереться в тупик.
(Т.е., тут алгоритм предотвращения запутывания змейки)
Вроде тот же алгоритм, с той лишь разницей, что генерация ведется не до тех пор, когда пространство для генерации кончится, а до тех пор, когда будет достигнута заданная глубина (или расстояние) от текущей позиции.
А дальше начинаются оптимизационные моменты, которые зависят от нюансов задачи. К примеру, в 2D вам, скорее всего, нужно заполнить экран и немного за экраном. А в 3D прямой коридор придется делать бесконечно, пока он наконец не повернет, ведь пользователь от первого лица должен увидеть конец коридора, а не пустоту, каким бы длинном он ни был.
Далее не понятно, как вы данные храните. Если у вас нет поля заданного размера, то хоть какое-то поле есть? Или каждая клетка/комната/соединение у вас представлены отдельным объектом в куче? И лабиринт по сути не сетка, а граф? От этого алгоритм тоже зависит.