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

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

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

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

Моя идея состоит в следующем:

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

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

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

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

10 голосов | спросил Splo 22 12010vEurope/Moscow11bEurope/MoscowMon, 22 Nov 2010 21:27:34 +0300 2010, 21:27:34

2 ответа


1

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

ответил Gastón 23 22010vEurope/Moscow11bEurope/MoscowTue, 23 Nov 2010 19:43:07 +0300 2010, 19:43:07
0

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

ответил Sparr 23 22010vEurope/Moscow11bEurope/MoscowTue, 23 Nov 2010 02:21:55 +0300 2010, 02:21:55

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132