Процедурный… дом с комнатным генератором

Я просматривал некоторые алгоритмы и статьи о процедурном создании подземелья. Проблема в том, что я пытаюсь создать дом с комнатами, и они, кажется, не соответствуют моим требованиям.

Во-первых, в подземельях есть коридоры, где в домах есть залы. И хотя изначально они могут показаться одинаковыми, зал - это не что иное, как пространство, которое не является комнатой, а коридор специально разработан для соединения одной зоны с другой.

Еще одно важное отличие от дома в том, что у вас есть определенная ширина и высота, и вы должны заполнить все это комнатами и залами, тогда как в подземелье есть пустое пространство.

Я думаю, что коридоры в доме - это нечто среднее между коридором темницы (приводит вас в другие комнаты) и пустым пространством в темнице (это явно не определено в коде).

В частности, требования следующие:

• Есть набор предопределенных комнат,
  я не могу создавать стены и двери на лету.
• Комнаты можно поворачивать, но
  не изменять их размер. Опять же, поскольку у меня есть предопределенный набор комнат, я могу только вращать их, но не изменять их размер.
• Размеры домов заданы и должны быть полностью заполнены комнатами (или залами),
  т. Е. Я хочу заполнить дом 14х20 доступными комнатами, следя за тем, чтобы в нем не было пустого пространства.

Вот несколько изображений, чтобы прояснить ситуацию:

Как вы видите, в доме «пустое пространство» все еще можно пройти, и оно доставит вас из одной комнаты в другую.

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

Вот где я хотел бы получить вашу помощь: не могли бы вы дать мне советы о том, как разработать этот алгоритм? Есть мысли о том, какие шаги он предпримет? Если бы вы создали генератор подземелий, как бы вы изменили его в соответствии с моими требованиями? Вы можете быть настолько конкретным или общим, как вам нравится. На самом деле, я собираюсь выбрать твои мозги.

Я думаю, что это хороший случай для использования двоичного или троичного пространства раздела.

На первом проходе разделите пространство дома на залы и {блоки комнат}. Возьмите следующий большой кусок, разделите его на {зал и кусок} или {2 блока и зал между ними}. На каждом шаге поворачивайте направление нарезки на 90 градусов. Остановитесь, когда {больше не осталось больших кусков} или {общая площадь зала достигла предела}.

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

Если какой-либо зал обращен к более старому залу, разместите там стену (или стену с дверью).

Соедините комнаты с залами напрямую или через другие уже соединенные комнаты.

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

Вы можете воспользоваться тем, что желаемый дизайн смешивает комнаты в прямоугольных комнатах, окруженных коридорами. Имея это в виду, я бы сделал это:

1. Дизайн коридоров и «больших пространств» для помещений
2. Заполните каждое «большое пространство» комнатами

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

Итак, вот как я решил эту проблему. Но сначала я хотел бы поблагодарить @Shadows In Rain и @egarcia за их ответы. Они дали мне хорошее направление, которое помогло мне получить некоторые результаты.

Я использовал пространственное разбиение Shadows In Rain для создания простого дома, а затем последовал совету egarcia, чтобы заполнить пространство комнатами.

Разделение пространства было довольно простым, поскольку 90% кода было сделано Shadows. Часть «заполнить комнаты» была немного более сложной. Я решил использовать систему планирования псевдо-ИИ, которая использует A * для правильного расположения комнат. Преимущество использования планирования вместо просто A * заключается в том, что предварительные условия помогают значительно сократить пространство поиска.

Вот несколько скриншотов с результатами:

Этап генерации плана этажа

Этап размещения помещения

Теперь с соединительными дверями!

У Dahl & Rinde есть дипломная работа по процедурной генерации внутренней среды, в которой используется скелетный и региональный подход для наполнения интерьеров зданий комнатами и коридорами. В статье приведены диаграммы классов для их прототипа. В их библиографии также есть несколько хороших ссылок, в том числе вышеупомянутый A Pattern Language .

Их работа была разработана вокруг следующих упрощающих допущений:

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

Вот краткий обзор их процесса:

• Найдите скелет для конверта. Коридоры затем размещаются вдоль скелета на основе расстояния от огибающей, близости к дверям или лестнице и близости к ранее размещенным коридорам.
• Затем оставшееся не коридорное пространство разделяется на максимально связанные области, каждая из которых имеет одну непрерывную границу. В некоторых случаях это потребует вставки стены.
• Эти регионы затем делятся на квартиры, пытаясь выделить хотя бы одно окно на квартиру. В некоторых случаях меньшие подразделения будут объединяться, чтобы избежать слишком маленьких квартир. Регионы без окон просто игнорируются.

• Наконец, квартиры делятся на комнаты, используя взвешенную диаграмму, подобную Вороному, в качестве основы для следующего:

  • Вес семян используется, чтобы влиять на размер комнаты. Семена добавляются в двери и окна. Добавляются дополнительные семена, как правило, по одному на каждую комнату; хотя это прямо не указано, похоже, что семена размещены вдоль наружных стен квартиры.
  • Начиная с самой дальней точки, вычисляется линия между данным начальным и всеми остальными точками, а затем делится пополам расстояние относительно соответствующих весов конечных точек (например, если A & B имеет веса 1 и 4, точка деления будет 1/4 пути от А до Б). Набор пополам линий вместе с внешней стенкой образует ячейку для семени.
  • Затем создается скелет стены S-Space (согласно Peponis et al. 1997) путем разделения области линиями, начинающимися перпендикулярно из средних точек между соседними парами элементов внешней стены (окна или двери).
  • Наконец, стены выбираются из скелета S-пространства, который «максимально соответствует клеточным стенкам Вороного».