Реализация циклической генерации подземелий «изнутри»: да что тут сложного?

Благодарю за критику, но позвольте не согласиться. Требование планарности графа выглядит скорее нужным, чем нет. Без этого как мы узнаем, влезет ли наш уровень на сетку? Если не обращать на это внимания, проблема появится на этапе расположения комнат. При отсутствии планарности (с учётом телепортов) у нас появится очень уж много вариантов такого расположения, и таким образом нам потребуется вдобавок какая-либо эвристика, которая поможет размещать комнаты так, чтобы телепортов было не слишком много (ведь разные варианты расположения одного и того же графа потребуют разного их количества). Если, просто для наглядности, доведём ситуацию до крайности, то получим просто пачку геометрически несвязанных участков с кучей телепортов. Это не будет выглядеть рукотворно, это не будет выглядеть особенно логично, и, более того, по уровню с таким количеством телепортов будет трудно перемещаться игроку. Планарность помогает избежать этого заранее.

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

По поводу бэктрекинга: возможно, это моя проблема с формулировкой. Недостатком является трудность с "дозированием" бэктрекинга в рамках древовидных генераторов, а не его наличие как таковое. Плюс, бэктрекинг бэктрекингу рознь - ведь есть разница между шорткатом а-ля Dark Souls и банальным хождением из тупика по в точности тому же маршруту, по которому мы пришли в этот тупик. "Обоснованное возвращение" в рамках циклической генерации более обоснованно, чем в древовидных уровнях - ведь у вас появляется возможность вернуться в уже посещённую комнату более чем одним маршрутом.

...если эти правила не могут пересекаться друг с другом, то мне кажется,
шаблон быстро станет заметен. Например, в вашем примере, игрок один раз
увидит, что после тревоги спящий монстр, второй раз, а на третий он уже в курсе. - в том и суть метода подстановки, что правила многократно применимы, в том числе к уже изменённым частям карты. Другими словами, подстановка на графах используется именно ради того, чтобы множество как можно более простых (в терминах левелдизайна) правил могли пересекаться друг с другом. В вашем примере, после комнаты-тревоги, но до спящего монстра, вполне может быть вставлен подграф с поиском ключа или вообще какая-нибудь развилка. Если правил достаточно много, вариантов их сочетаний будет столько, что вряд ли игрок привыкнет к ним всем. Примерно это я назвал "эмерджентным левелдизайном" за неимением лучшего термина.

Например, в вашем примере, игрок один раз увидит, что после тревоги спящий монстр, второй раз, а на третий он уже в курсе.

Это же вроде как считается эталоном хорошего геймдизайна? Та же ситуация с тем, когда кладут гору аптечек и патронов перед боссом - игрок видит эту гору и уже готов сражаться.
И одна из проблем процедурной генерации - такое там очень трудно сделать. (окей, конкретно навалить патронов в предбанник с боссом просто :) но я про общую ситуцию "решение => проблема") Особенно если чутка разнести их в простанстве - всё, сейчас большинство игр с процедурной генерацией такое не тянут.

Благодарю за интерес к статье!

Подскажите, а в вашем варианте сам граф (до размещения) случайный, или же задан целиком рукотворно?

Расположение графа на плоскости я делаю через сильно модифицированный WFC

Вот это очень интересно! Такого подхода я ещё не встречал.

Как решите закосы под метроидванию, когда один ключ открывает несколько дверей в разных, не связанных частях карты? Очень хочется иметь такую генерацию.

В целом, это сейчас уже решено. Есть отдельные правила, запирающие дверь - и для дверей с общим ключом правила такие же, как для обычной запертой двери, с одним только нюансом: такой многоразовый "мастер-ключ" ставится только тогда, когда его ещё нет на карте. Если вы хотите иметь несколько, но разных мастер-ключей на одном уровне, есть правила "добавить запертую дверь для ключа, который на карте уже есть".

Не думали, что такая модель противоречит типичной игровой ситуации как "монстр в комнате с ключом"?

Думаю, не противоречит. Разрешения ситуации тут два, можно выбрать любой или оба сразу:

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

2. Тэги ведь будет использовать другой генератор - генератор самих комнат (следующий этап после создания графа). На этом этапе можно подобавлять монстров или ловушек в любые комнаты, где есть ключ или сокровище, или наоборот, пропускать этап их добавления на отдельных тэгах вроде спящего монстра.

Пункт 1 уже есть в моём варианте, но это осталось за рамками статьи, на примере одного тэга на комнату демонстрация получается нагляднее.

Больной для анексплоред вопрос с тем, что делать если игрок очутился за запертой дверью. Считаю в оригинальной игре это решено довольно топорно

На данном этапе заметил, что наличие подобной проблемы связано с набором правил, а не с самим алгоритмом. Такие ситуации порождают либо одноразовые проходы, либо "самозапирающиеся" двери. Текущий набор правил, какой есть у меня, таких ситуаций не порождает - что ж, возможно, всё ещё впереди.

Мне кажется, можно избежать такой проблемы, если запретить правилам взаимодействовать с узлами графа, где есть подобные "временны́е" тэги.

Нет ли идеи отказаться от планарности совсем? Сделать комнаты по типу Биндинг Оф Исаак, но все равно выигрывать в интересе за счет продвинутой генерации игровых ситуаций?

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

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

Если же вы имеете в виду не планарность, а непрерывность уровня (то есть, все комнаты существуют как бы одновременно, без перехода наподобие загрузки между ними), то да, она в общем-то не обязательна. Моё субъективное мнение в том, что с непрерывными уровнями интереснее (те же Unexplored или Dead Cells выдают из-за этого более интересные для меня уровни, чем айзек).

чтобы оправдать <...> непрерывность уровня, необходимо её
использовать в игровом процессе больше чем "ну просто чел идет и между
комнатами нет черного экрана".

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

Интересно, благодарю!
Да, самой сложной частью при таком способе раскладки будет узнать, когда граф всё ещё этой самой раскладке поддаётся.

По идее, у каждого правила должен быть соответствующий черный / белый список совместимости с другими правилами / группами правил.

И у каждого узла должен быть (белый / чёрный / текущий) (список / списки) используемых (групп) правил.

И перед добавлением правила в узел (общий уровень или конкретная комната) идет проверка по этому списку на совместимость.

Интересно, спасибо! Идея и в самом деле схожа.

Интересно было бы почитать про выработанную грамматику и типы приписываемых к вершинам и рёбрам семантических признаков

Подскажите, что для вас выглядит интереснее - механизм работы и применения этой самой грамматики, или же конкретные примеры применимых правил? Оба пункта достаточно объёмны и интересны для отдельной статьи, но первый из них у меня несколько хромает, мне не нравится моя реализация (хотя для её улучшения как раз и есть смысл ей поделиться).