Генератор лабиринтов

[Soplik]

Дано: лабиринт 64х64. Клеточка ест четыре байта:
0 -- начало и конец линии раздела (см. ниже)
1 -- пол и потолок в левом верхнем углу
2 -- пол и потолок в правом нижнем углу
3 -- материал стен и теги.
Линия раздела -- отрезок внутри клеточки, делящий ее на два сегмента. Он начинается в одной из 16 точек по периметру и заканчивается также в любой из 16 этих точек. В каждом из двух сегментов -- своя высота пола и потолка.
Один лабиринт без монстров, артефактов и порталов ест таким образом 16 килобайт -- треть сороквосьмой памяти и восьмую часть стодвадцатьвосьмой.

Хотелось бы научиться их генерировать. Нужны идеи.

NB: сам я возьмусь за эту игру не раньше, чем допишу белазики. Если кто возьмется развивать идею, буду только рад.

[Advertiser]

[TomCaT]

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

[Soplik]

Если вторая комната ненамного выше/ниже -- ничего страшного. Можно вставить спотыкание при маленькой энергии.
Если сильно ниже -- ушибаемся. Чем дальше падаем, тем сильнее бьёмся.
Если сильно выше -- это то же самое, что стенка. Если не сильно, но заметно выше -- запрыгиваем с разбегом или без оного.

[Barmaley_m]

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

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

[Soplik]

Монстров, думаю, тоже будет конечное число. Это не FPS.

---------- Post added at 00:57 ---------- Previous post was at 00:55 ----------

Если просто псевдослучайно генерировать, будет не лабиринт, а каша из обломков

---------- Post added at 01:28 ---------- Previous post was at 00:57 ----------

Хм, а вот если как-то продолжать стенку от клеточки к клеточке, расставлять колонны и лестницы, копировать комнаты в ряд...

---------- Post added at 01:55 ---------- Previous post was at 01:28 ----------

Я хочу что-то в духе уровней Doom, но без секторов. И без самой трехмерки.

[Andrew771]

Линия раздела -- отрезок внутри клеточки, делящий ее на два сегмента

А почему нельзя линию раздела делать по границам клеток?
Генератор лабиринтов: http://zx.pk.ru/showthread.php?t=15939

[Soplik]

Хочется диагональные стенки, тонкие двери, изгибающиеся коридоры.

[TomCaT]

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

По ссылке Andrew771 можно поискать в теме разные варианты генераторов лабиринтов в матрице, только с прямыми углами и с однообразными составляющими типа комнат с 4-мя стенками или однобитных блок/проход.

Твой тип лабиринта ближе к комнатному, но сложнее. Если усложнить комнатный генератор лабиринта с поднимающимися стенками, то можно:
1) начинать с пустого пространства и хорошего генератора чисел
2) выбрать случайное препятствие и для пробы установить на поле
3) проверить одним из методов, можно ли от одной стороны препятствия(стенки комнаты, линии раздела) добраться до другого. Если можно - препятствие не разрывает лабиринт на две части. Можно добавлять следующее с шага 2
4) если перебрать все возможные препятствия, получится лабиринт, в котором от каждой точки до другой можно добраться единственным путем. Это наиболее сложно, но не увлекательно. Часть допустимых препятствий стоит либо не ставить, либо поубирать потом, перове сложнее, второе - медленнее.
5) В получившемся лабиринте несколькими способами можно расставить материал стен. Совершенно случайно проще, но выделить зоны, чтобы стены сменялись по мере удаления от старта, можно, один раз проверив расстояния клеток (полу-клеток, т.е. треугольников, если одна половина клетки вышла намного ближе, чем другая половина, можно материал для половинок хранить отдельно). С этой точки зрения лучше реализовать "волну" в пункте 3, чтоб здесь использовать ее же.

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

Могут быть усложнения с линией раздела, в отличие от клеток-квадратов. Допустим, в комнате 4 двери. Если линия может поворачиваться по всем 360 градусам, и при этом либо отделять 2 двери от других 2-х, либо 1 дверь от 3-х остальных, возникает 6 (логических) вариантов раздела, точную точку из 16 потом можно выбрать случайно. Выбранный один вариант, конечно, отменяет остальные 5.

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

Высота пола при генерации может вызывать односторонние проходы тогда, когда разница на границе клеток велика для подъема, причем любыми средствами, но мала для того, чтобы без вариантов разбиться при падении - последнее уже есть непроходимое препятствие. Хотя если подъем очень сложен, как в Head over Heels типа, с предмета на голове монстра, но в теории осуществим, можно при небольших разницах в расстоянии от старта для двух соседних клеток игнорировать такой подъем при генерации лабиринта - пусть срезанный путь будет наградой за ловкость игрока.

С односторонними проходами нужна осторожность - они могут вести от старта к финишу, а в обратном направлении - только, когда есть другой проход, т.е. при проверке препятствия на шаге 3 нужно проверять проходимость от одной стороны к другой и отдельно - наоборот. Либо уже при первой проверке пользоваться только двусторонними проходимыми путями, а при их нехватке - односторонним в одном месте, отдельно отметив, существует ли односторонний в обратном направлении. Только такой головоломный поиск может выйти в разы дольше двух простых проверок в противоположных направлениях. А если проход все-таки вышел односторонний, то, увы, в этом алгоритме в процессе построения заранее неизвестно, какая сторона препятствия обращена старту, а какая - к финишу. Приходится препятствие убирать, разве что если есть возможность сделать проход двусторонним позже - если позволяет разница высот комнат, в которые можно пройти из этой пары, которая сейчас разделяется препятствием.

Еще про односторонние - если от старта к финишу пройти можно только через некоторый односторонний проход - это естественная граница зон, тут можно сменить материал стен. Прохождение такого места, если в дальнейшем понадобится предмет, или нужно будет нажатие кнопки где-то ранее до "границы", приводит в ловушку, которую можно оставить как есть (но игроки ругаются), про которую можно намекнуть как-нибудь, до ее пересечения (если генератор карты помечает это отдельным битом). В Кирандии 2 на ИБМ вообще обеспечивают дальнейшее прохождение игры самопоявлением предметов, и не только в рюкзаке, причем как ни странно, к этому привыкаешь, и напрягает мало. Если не задуматься, конечно... В общем, односторонние проходы - сплошная головная боль, то-то в Диабле их 0,0...1 %, и те заранее продуманы.

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

[Soplik]

Теперь второй вопрос: как этото лабиринт лучше всего отображать? Сверху, в изометрии Knight Lore или...

[Andrew771]

Теперь второй вопрос: как этото лабиринт лучше всего отображать? Сверху, в изометрии Knight Lore или...

как хочешь