Уменьшите количество ребер графа, оставив его подключенным

10

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

Я видел 2 способа создания окончательной топографии подземелья:

  • Сначала сгенерируйте случайный график, затем попытайтесь заполнить 2-й мир комнатами в случайных местах, соблюдая граничные связи. Я полагал, что это иногда будет трудно, потому что поколение комнат может быть «заперто», пытаясь приспособить комнаты в невозможных местах.
  • Создайте первые комнаты, расположив их случайным образом там, где они подходят, затем сопоставьте результат с узлами и ребрами. Я решил попробовать это.

Моя идея заключается в:

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

Таким образом, я гарантирую, что все комнаты имеют возможное местоположение в 2D-мире и правильно отображаются в связанном графике.

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

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

Splo
источник
Ваша идея - это в основном бинарное дерево поиска, если вы хотите знать. Я использовал это; это делает довольно хорошие темницы и легко. :)
Коммунистическая Утка
2
К сведению: у полного графа есть ребра между всеми парами вершин, поэтому (при условии, что повторяющиеся ребра недопустимы) вы не можете удалить ребра и по-прежнему иметь полный граф. Правильный термин - связный граф .
Майкл Мэдсен
Двоичное дерево поиска, связный граф, справа. Мне так плохо с обычным названием вещей.
Спло

Ответы:

13

Используйте алгоритм Прима для получения минимального остовного дерева для вашего графа (добавьте рандомизированные веса, или добавьте более высокие веса возле входа, или создайте алгоритм по вашему выбору) и заново добавьте некоторые двери / ребра наугад. Таким образом, у вас будут все соединенные комнаты и несколько лишних путей.

r2d2rigo
источник
1
Ах да, минимальное остовное дерево, конечно! Хорошая идея, спасибо.
Splo
1

Вы также можете попробовать алгоритм Крускала

Gastón
источник
0

Некоторые из генераторов подземелий из этого списка от Inkwell Ideas имеют открытый исходный код или предоставляют документацию по своим алгоритмам. Google также даст вам много с помощью поиска «[имя_программирования] генератора подземелий». К сожалению, мой любимый не может быть найден ни одним из этих методов, несмотря на то, что он наиболее хорошо задокументирован, с которым я когда-либо сталкивался, и я не могу вспомнить его имя, так как недавно потерял его из-за сбоя жесткого диска. Я обновлю этот ответ после выполнения восстановления на этом диске.

Sparr
источник