Процедурная генерация подземелий: существует ли простой алгоритм, чтобы все эти комнаты были соединены с использованием минимальных коридоров?

Можно ли получить улей-подобную структуру, соединяющую все комнаты без слишком большого количества коридоров? (Слишком много из 3-4 комнат, идущих из одной комнаты)

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

Что я надеюсь получить в коридоре.

Ну, самый простой способ, который я могу придумать, начинается с того, что все комнаты соединены хотя бы одним коридором:

1. Начните с последней или первой комнаты.
2. Возьмите случайную комнату на расстоянии 1 расстояние, которое еще не связано с какой-либо комнатой (все комнаты начинают отключаться, поэтому вы будете следить за этим по ходу дела).
3. Если такой комнаты нет, пройдите на расстояние +1. Если можно проложить туннель над / под другой комнатой, это проще, если вы не хотите соединять коридоры.
4. Проходите псевдослучайно, пока все комнаты не соединятся.

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

В качестве последнего шага вы можете добавить правила, которые бы изменили ваши результаты для соответствия различным ситуациям. Например, вы можете заметить, что любая комната с одним коридором по определению является тупиком; Вы можете сделать больше тупиков, или вы можете устранить их все, убедившись, что у всего есть как минимум 2 соединения. Вы можете сделать тупики иметь секретный проход. Вы могли бы убедиться, что комната босса - тупик. Вы можете убедиться, что ваша начальная комната тупиковая, но затем убедитесь, что вторая комната имеет минимум X соединений. До бесконечности.

Каждое предположение и правило могут радикально изменить внешний вид ваших уровней, но это часть веселья! Это должно, по крайней мере, дать вам комнаты, похожие на улья / пещеры.

Просто постройте свои комнаты уже подключенными. Начните с одной комнаты, затем построите 1-3 коридора в другие комнаты. Затем повторяйте, пока не добавите достаточно комнат.

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

Вы вычисляете края (длины коридора) между всеми комнатами. Вы сортируете их по длине. Вы добавляете кратчайший коридор, если только он не создает цикл или не увеличивает степень вершины (комнаты) над желаемым максимальным значением (3-4) (повтор). Чтобы проверить циклы, вы можете применить UnionFind или сделать быстрый BFS на небольших данных.