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

74

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

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

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

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

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

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

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

Типичный генератор подземелий Подземелье без коридоров Дом генератор результат

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

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

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

пекин
источник
2
Странная рекомендация: я настоятельно рекомендую ознакомиться с книгами Кристофера Александра « Вневременный путь построения и язык шаблонов» , книгами по архитектуре, которые легли в основу понятия (программного) шаблона; они по существу описывают явный язык для зданий и жилых помещений, который можно превратить в методический метод построения сверху вниз.
Стивен Стадницкий,
Лично я бы попытался создать алгоритм, подобный ответу Егарсиаса. Начните с создания заполнителей комнат (больших площадей, которые могут быть заполнены различным количеством комнат. Каждый заполнитель комнат должен иметь определенный (или случайный, с нижними границами) разрыв между ними. Пространство «промежутка» - это то, что будет рассматривается как прихожая, т. е. пространство, которое находится в доме, но не в комнате, и заполнители комнат будут заполнены комнатами произвольного размера, подобными примеру «темница без коридоров»
Бенджамин Дэнджер Джонсон,
@pek Пожалуйста, создайте ответ для своего решения, не включайте его в вопрос.
MichaelHouse
@ Byte56 Готово. Просто чтобы прояснить, я сделал это, потому что я не хотел получать кредит, потому что я делал только то, что предлагали другие люди. Хотя я понимаю, почему это не идеально подходит для формата сайта, поэтому я добавил свой ответ.
Пек
Спасибо @pek. Не беспокойтесь о получении кредита, это заслуженно и полезно для людей, которые приходят на сайт, чтобы увидеть решение (и увидеть его там, где его ожидают, лучше всего).
MichaelHouse

Ответы:

50

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

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

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

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

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

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

последний выстрел

Тени под дождем
источник
Вот где мои исследования привели к разделению пространства. Ваш пример с кодом дал мне очень хорошее начало. Я сейчас читаю об алгоритмах. Хотя один вопрос: одно из моих требований заключается в том, что комнаты предопределены (то есть есть 2x2 комнаты с одной дверью, 1x1 с двумя дверями, но нет 2x2 с тремя дверями), поэтому я не могу начать перегородку и затем решить, где я буду размещать двери , Я думаю, что я должен помнить о своих ограничениях, пока я делаю разделы. У вас есть предложение, как бы я поступил по этому поводу? В любом случае, большое спасибо за ваш ответ и усилия!
пекин
@pek Я не уверен, сможет ли простой смертный найти академическое решение этой проблемы. Вы можете попробовать установить дополнительные условия для разделителя фрагментов и разделителя блоков, а затем генерировать и сбрасывать уровни, пока не найдете тот, где будут выполнены все условия.
Shadows In Rain
да, я надеялся, что что-то упустил. Мой первый подход был с использованием A *, чтобы выяснить, как разместить комнаты в заданном пространстве, но для залов не хватало логики. Теперь я думаю, что могу использовать BSP для размещения залов, а затем использовать A * для блоков. Больше всего меня беспокоит то, что это может быть слишком дорого и не всегда дает результат. Но я должен сначала проверить это. Может быть, все будет не так плохо?
pek
2
@pek Я нашел что-то полезное, если тебе все еще интересно. Посмотрите на это , также Google L-system.
Shadows In Rain
24

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

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

2 шага

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

egarcia
источник
15

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

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

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

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

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

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

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

пекин
источник
11

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

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

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

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

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

    • Вес семян используется, чтобы влиять на размер комнаты. Семена добавляются в двери и окна. Добавляются дополнительные семена, как правило, по одному на каждую комнату; хотя это прямо не указано, похоже, что семена размещены вдоль наружных стен квартиры.
    • Начиная с самой дальней точки, вычисляется линия между данным начальным и всеми остальными точками, а затем делится пополам расстояние относительно соответствующих весов конечных точек (например, если A & B имеет веса 1 и 4, точка деления будет 1/4 пути от А до Б). Набор пополам линий вместе с внешней стенкой образует ячейку для семени.
    • Затем создается скелет стены S-Space (согласно Peponis et al. 1997) путем разделения области линиями, начинающимися перпендикулярно из средних точек между соседними парами элементов внешней стены (окна или двери).
    • Наконец, стены выбираются из скелета S-пространства, который «максимально соответствует клеточным стенкам Вороного».
Pikalek
источник
3
Можете ли вы включить фотографии? Это было бы прекрасно. Я просмотрел бумагу, и комнаты, которые они сгенерировали, выглядели хорошо с точки зрения архитектуры.
congusbongus
Очень интересный метод, мне придется самому изучить его более тщательно для любых идей, которые я смогу от него отнять.
Draco18s
Я пришел сюда, чтобы отдохнуть от работы ... Сюрприз, моя тема исследования выходит. Я слишком ленив, чтобы написать ответ, основанный на моих собственных исследованиях (я еще только разработал основы алгоритма, так что оно того не стоит) или на описании подходов Данила Надя к проблеме, поэтому я просто оставлю это здесь autodeskresearch.com/publications/…
Фелипе Гутьеррес