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

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

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

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

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

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

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

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

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

2 ответа

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