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

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

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

вывод сетчатых комнат, помещенных случайным образом

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

http://i.imgur.com/9GUi6Yy.png

9 голосов | спросил Blenderer 6 PM000000100000004131 2013, 22:25:41

3 ответа


6

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

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

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

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

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

ответил BrianH 7 AM00000030000002131 2013, 03:36:21
3

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

ответил Nicol Bolas 6 PM000000110000005431 2013, 23:52:54
2

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

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

ответил wolfdawn 21 PM000000120000000831 2015, 12:26:08

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

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

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