Процедурное генерирование здания определенной площади

15

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

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

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

Немного более актуальной информации: 2D сверху вниз. Некоторые из механизмов выполнены в стиле factorio, поэтому комнаты должны иметь разумную длину и ширину, чтобы было достаточно места для машин. В настоящее время в Java и Lua (при необходимости можно использовать встроенные библиотеки из любой из них)

Заранее спасибо!

РЕДАКТИРОВАТЬ: Когда я говорю «хорошие» или «плохие» выходы, плохой вывод будет любой вывод, который имеет место, неиспользуемое игроком. Заводская форма ограничивает место, где игрок может разместить фабричные машины, такие как конвейерные ленты. В идеале на фабрике не должно быть областей шириной всего 1-2 блока, форма не должна быть одним или двумя большими прямоугольниками с линией из 1-2 блоков, свисающих в одну сторону. Хорошим результатом будет то, что вся площадь пола «работоспособна», поэтому все области имеют ширину не менее 3-4 блоков. Хороший вывод не всегда должен быть сложным (1 или 2 прямоугольника в порядке), но он должен иметь хорошие шансы, если он состоит из более чем 1-2 прямоугольников.

user2129189
источник

Ответы:

7

Вы можете использовать предварительно сгенерированные polyominoes как мета-фигуры для построения ассортимента зданий.

Допустим, ваше минимально допустимое расстояние составляет 3 блока. Тогда наименьшая приемлемая строительная единица, которую мы рассмотрим, - 3х3. Для удобства я буду называть это ячейкой, и она дает площадь 9 блоков. Затем возьмите целевую начальную область и разделите ее на область ячейки. Используя начальное значение, которое вы дали, мы получим 3.333; таким образом, 3 клетки дадут вам немного меньше, чем вы хотите, а 4 клетки дадут вам больше.

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

Затем случайным образом выберите полиомино с нужным количеством клеток. Замените каждый квадрат на polyomino клеткой здания, и вы получите свою окончательную форму.

Для иллюстрации, скажем, мы решили округлить. Вот все полиномино 3-го размера (не включая вращения / сальто):

введите описание изображения здесь

Давайте предположим, что мы случайным образом выберем форму L и применим случайное вращение, ваше здание будет иметь следующую компоновку:

введите описание изображения здесь

Пара вопросов. Во-первых, существует ограничение на количество ячеек, которые вы можете использовать. Википедия даст вам все polyominoes до размера 8 ( octomino ). Он включает в себя сводные данные до 12 размера, но я не знаю, есть ли онлайн-список для всех них. Во-вторых, приведенное выше решение работает только для размеров здания, кратных 9. Существует несколько способов обойти некоторые из этих проблем:

1) Используйте другой размер ячейки. Например, 3х4, 4х4 и т. Д.

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

3) Разметьте здание, чтобы оно стало больше. Возвращаясь к примеру, если вы использовали 3 ячейки, ваше здание будет иметь площадь в 27 квадратов, а вы останетесь коротким на 3. Затем вы можете отсканировать периметр, чтобы найти место для склеивания группы квадратов размером 1x3. До тех пор, пока ваша группа макияжа будет, по крайней мере, AxB, где A - это, по крайней мере, ваше минимально допустимое расстояние, ваш результат не будет нарушать ограничение минимально приемлемого расстояния. На примере выше приведен пример возможного результата:

введите описание изображения здесь

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

Некоторые другие комментарии:

То, что вы можете использовать все возможные полиомино данного размера, не означает, что вы должны это делать. Если некоторые из них неинтересны, нарушают вашу тему, оскорбительны для вашей аудитории (шаблоны свастики) или вызывают другие проблемы, уберите их. Кроме того, вы можете взвесить вашу процедуру выбора, если некоторые шаблоны интересны, но слишком странны, чтобы регулярно появляться. Наконец, вы можете использовать это решение в сочетании с вашей текущей стратегией. Может быть, 70% времени вы создаете прямоугольные здания и 30% времени вы используете подход polyomino. Или, может быть, вы начинаете с прямоугольного здания и приклеиваете небольшое полиомино снаружи.

Pikalek
источник
16

Простой способ построить процедурный генератор:

  1. Случайно строить вещи
  2. Запустите функцию, которая проверяет, хорош ли вывод
  3. Если вывод не очень хороший, перейдите к шагу 1

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

Вы перечислили некоторые объективные показатели того, хорош ли результат; этого должно быть достаточно для создания быстрого и грязного генератора. Разместите прямоугольники случайным образом внутри области и отклоните вывод, например, если есть области шириной всего 1-2 блока.

Начните с этого, улучшайте и оптимизируйте потом.

congusbongus
источник
Спасибо! Я помню об этом, но мысль о том, что есть шанс на несколько секунд + время загрузки, остановила меня. Теперь я понимаю, насколько невероятно мал этот шанс. Я должен попробовать это, но я мог бы подождать, чтобы увидеть, есть ли у кого-то более прямое решение в первую очередь.
user2129189
@ user2129189 Когда вы запустили генератор, вы все равно можете настроить его диапазоны случайных чисел, чтобы избежать генерации раскладок, которые вряд ли пройдут тест. Также возможно распараллелить этот алгоритм генерации проб и ошибок по нескольким ядрам, заставляя каждое ядро ​​генерировать один макет за раз.
Филипп
3
Сам я не фанат методов генерации брака и повторения. Они достаточно быстры, когда ваш генератор делает только одну простую вещь, но для игровых уровней мы обычно начинаем накапливать больше функций и этапов генерации, чтобы сделать более богатые карты. В этот момент вероятность попадания в жизнеспособную карту является произведением вероятности каждого последующего шага, который может быстро уменьшаться. Это не просто академическая проблема - я разговаривал с разработчиками, которым нужно было внедрить систему кеширования хороших / плохих семян, чтобы избежать избыточного времени генерации, когда бы проще было создать корректный по конструкции генератор за один проход.
DMGregory
@DMGregory, да, я определенно вижу это. В моем случае базовый генератор случайных чисел работал бы как 99% времени за несколько проходов, но если я захочу добавить больше сложности позже, он может значительно замедлиться. Кто-нибудь знает какие-либо реальные приложения для программирования / игр, основанные на модели «угадывай и проверяй»?
user2129189
Может быть, могут быть уровни функций и проверок поколений, стараясь согласовать формулировку условий с текущим уровнем генерации. Таким образом, весь уровень не нужно заново генерировать целиком только из-за найденной ошибки, при которой элемент помещается немного неправильно.
Пизис
7

Учитывая ограничение «все области имеют ширину не менее 3-4 блоков», первая мысль, которая приходит мне в голову, выглядит примерно так:

  1. выберите один из 3х3, 3х4, 4х3 или 4х4
  2. поместите блок такого размера в центр сетки
  3. выбрать направление (вверх, влево, вправо, вниз)
  4. попытаться разместить блок 3х3 рядом с ранее размещенными блоками в этом направлении
  5. в случае успеха, с некоторой вероятностью, попробуйте расширить блок до блока 4x3 в одном из направлений, которые вы не выбрали
  6. с некоторой вероятностью переместить случайный край заполненных блоков
  7. повторите шаги с 3 по 6, пока площадь не станет достаточно большой

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

Ryan1729
источник
4
Я бы упростил задачу, всегда начиная с блока 3х3, затем добавляя блоки 3х1 в случайных позициях, где каждый квадрат смежен с существующим. При добавлении к блоку 3х3 возможны четыре позиции. Все дают вам блок 3х4 с шестью возможными позициями для следующего. Оттуда становится все сложнее, но не так плохо.
JollyJoker
0

Попробуйте использовать логические выражения NOT и UNION и выбирать между ними случайным образом.

  1. Поместите случайный прямоугольник.
  2. Поместите второй случайный прямоугольник.
  3. Произвольно выберите, объединить ли их или вычесть второе из первого.
  4. Повторите для нескольких прямоугольников. Хотя только два или три могут дать достаточно разумные результаты.

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

Осьминог
источник
Ваша идея масштабирования, чтобы получить желаемую область, на самом деле довольно умна. Я мог бы реализовать что-то тихое, как это.
user2129189