Я разрабатываю игру со случайно сгенерированными подземельями. Я хотел бы рассматривать это как связанный, неориентированный граф, в котором узлы - это комнаты, а ребра - это двери или коридоры. Затем я выбираю «боковой» узел в качестве входа в подземелье, вычисляю расстояние между этим входом и всеми остальными узлами и решаю, что один из самых дальних узлов является «целью» подземелья (местоположение сокровища, босс, принцесса и т. д.).
Я видел 2 способа создания окончательной топографии подземелья:
- Сначала сгенерируйте случайный график, затем попытайтесь заполнить 2-й мир комнатами в случайных местах, соблюдая граничные связи. Я полагал, что это иногда будет трудно, потому что поколение комнат может быть «заперто», пытаясь приспособить комнаты в невозможных местах.
- Создайте первые комнаты, расположив их случайным образом там, где они подходят, затем сопоставьте результат с узлами и ребрами. Я решил попробовать это.
Моя идея заключается в:
- Сначала создайте большую комнату, в которой будет целое подземелье.
- Поместите стену в большую комнату, в случайном месте, разделив большую комнату на 2 комнаты поменьше разной площади.
- Затем я продолжаю делить каждую комнату на 2, пока они не станут слишком маленькими или пока общее количество комнат не достигнет максимума (или любого другого условия). Каждая новая комната - это узел.
- Закончив, я проверяю каждую комнату и нахожу все смежные другие комнаты, отмечая 2 узла как соединенные ребром.
Таким образом, я гарантирую, что все комнаты имеют возможное местоположение в 2D-мире и правильно отображаются в связанном графике.
Моя проблема в том, что слишком много дверей и коридоров, соединяющих комнаты.
Поэтому я бы хотел алгоритм, который уменьшает количество ребер связного неориентированного графа , но в конце сохраняет его подключенным (все узлы остаются достижимыми).
Ответы:
Используйте алгоритм Прима для получения минимального остовного дерева для вашего графа (добавьте рандомизированные веса, или добавьте более высокие веса возле входа, или создайте алгоритм по вашему выбору) и заново добавьте некоторые двери / ребра наугад. Таким образом, у вас будут все соединенные комнаты и несколько лишних путей.
источник
Вы также можете попробовать алгоритм Крускала
источник
Некоторые из генераторов подземелий из этого списка от Inkwell Ideas имеют открытый исходный код или предоставляют документацию по своим алгоритмам. Google также даст вам много с помощью поиска «[имя_программирования] генератора подземелий». К сожалению, мой любимый не может быть найден ни одним из этих методов, несмотря на то, что он наиболее хорошо задокументирован, с которым я когда-либо сталкивался, и я не могу вспомнить его имя, так как недавно потерял его из-за сбоя жесткого диска. Я обновлю этот ответ после выполнения восстановления на этом диске.
источник