Выравнивание по пространству по оси: разделить пространство на случайные прямоугольники?

11

Мне нужен метод, чтобы разделить трехмерное пространство на выровненные по случайной оси фигуры. На данный момент я делю 2d пространство для тестирования. Самый непосредственный подход, который я предложил, - определить прямоугольник размером (1, 1), а затем рекурсивно разделить все существующие прямоугольники на два неравных прямоугольника, чередующихся между осями X и Y.

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

Проблема здесь очевидна. Этот подход приводит к длинным линиям растяжения (отмечены красным)

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

То, что я хотел бы, это что-то более органично выглядящий (я включил пример)

Видите, никаких длинных прямых линий сверху вниз или слева направо.

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

Единственное ограничение заключается в том, что я могу ограничить минимальный размер прямоугольника, не влияя на детализацию размеров. т. е. если наименьший прямоугольник равен 1 квадратным сантиметрам, то наименьшее количество секунд не должно составлять 2 квадратных единицы.

Поэтому в идеале алгоритм должен соответствовать всем трем следующим ограничениям:

  1. Прямоугольники не бесконечно малы.
  2. Размеры прямоугольника не являются дискретным умножением наименьшего размера прямоугольника. т. е. если наименьший прямоугольник равен 3 квадратным единицам, то более крупные прямоугольники не ограничиваются 6, 9, 12 и т. д. квадратными единицами и вместо этого могут составлять 3,2 или 4,7).
  3. Алгоритм работает за полиномиальное время (нужно быстро вычислять).
AturSams
источник

Ответы:

12

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

  1. Случайно размещайте различные точки в пространстве вашей карты. Нормализуйте их распределение (избегая некрасивой кластеризации), используя распределение Гаусса или применяя алгоритм итеративной релаксации для перемещения случайно расположенных точек друг от друга, согласно релаксации Ллойда для диаграмм Вороного . Эти точки представляют центроиды ваших будущих комнат.
  2. (Параллельный / повторный циклический перебор для всех комнат) Из каждой точки вырастите 4 вершины наружу (прямоугольная комната), перемещаясь от центральной точки за глобальную итерацию (вы можете выращивать разные комнаты с разной скоростью на каждой оси, а не для все, и посмотрите, как это получается - возможно, для более органичного / разнообразного результата). В какой-то момент некоторые ваши прямоугольники начнут давить друг на друга. На этом этапе ограничьте рост по этой оси, убедитесь, что смежные края двух комнат точно соприкасаются, и продолжайте.
  3. Повторите шаг 2, постепенно увеличивая каждую комнату, пока весь рост не будет ограничен соседними комнатами или границами карты.
  4. Это все еще оставит некоторые пустые места. Теперь проблема заключается в поиске и размещении комнат из незанятых помещений. На самом деле, если вашим базовым пространством является (целочисленная) сетка (и каждая итерация роста привязывается к этой сетке), то с этим гораздо проще иметь дело, поскольку вы можете поддерживать списки занятых и незанятых ячеек сетки: как только вы Разместив и вырастив все свои комнаты, ищите в незанятом списке отдельные места, состоящие из групп соседних ячеек. Поскольку многие неиспользуемые пространства будут иметь непрямоугольные формы, вам нужно будет выбрать ячейку случайным образом из этого непрямоугольного пространства и увеличить ее до максимального размера так же, как вы делали это с комнатами на шаге 2. Повторите в пределах указанного не прямоугольное пространство, пока оно не будет полностью заполнено.
  5. Повторите шаг 4, пока ваша карта не будет занята на 100%.
инженер
источник
Это хороший совет. Недостатком является то, что он, возможно, ничего не делает, чтобы защитить меня от бесконечно малых размеров. Мне нужно каким-то образом ограничить, насколько малы и насколько велики риты. В настоящее время я нахожусь в процессе работы над другим методом. Я буду сравнивать результаты и обновлять.
AturSams
@ArthurWulfWhite Тогда ваш вопрос был недостаточно конкретизирован и должен быть обновлен. Ваш минимальный размер комнаты определяется разрешением ячейки карты; поэтому, если вы сделаете это достаточно крупным, чтобы соответствовать минимальному размеру комнаты, вы можете затем отрегулировать оси с плавающей запятой, возвращая более органичный вид.
инженер
Ты прав! Я думал, что написал эту часть. Но у меня нет. Я прошу прощения за эту ошибку. Да, я в курсе размера сетки. Комната может быть настолько маленькой, насколько позволяет сетка.
AturSams
ОК - надеюсь, вы найдете подходящее решение. Кстати, я имел в виду «настроить линии сетки», а не «настроить оси».
инженер
1
На самом деле я делаю что-то в точности подобное, основываясь на концепциях, которые вы мне подумали. Я также опубликую результаты здесь.
AturSams
2

Как видите, мне удалось избавить мир от этих артефактов. Идея очень похожа.

  1. Разделите 2d пространство на неоднородную сетку. Если две линии слишком близки, удалите одну.
  2. Выберите прямоугольник случайным образом, проверьте, был ли он изменен по оси Y (по высоте) и был ли изменен его прямой сосед по оси Y. Я не был изменен, пусть они пересмотрят сегмент между ними (один даст некоторое пространство другому).
  3. Сделайте то же самое, что и в шаге 2, только на другой оси.
  4. Повторяйте процесс, пока вы не измените как можно больше.

Неравномерная сетка (1):

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

Переговоры по оси х (2):

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

Переговоры по оси y (3):

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

Результат (4):

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

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

AturSams
источник
Это было свободно вдохновлено пониманием @Nick Wiggill
AturSams
2
Это можно еще улучшить, если сначала произвольно объединить группы из n * m соседних ячеек в один прямоугольник. Это маскирует базовую сетку, все еще видимую в выводе выше. Переговоры с этими большими прямоугольниками теперь должны работать на всех ячейках вдоль одного из его краев.
DMGregory
ОК. Еще очень много коллинеарных границ, я бы работал над этим дальше, но хорошо, что вы нашли свое решение! Рад помочь.
инженер
@DMGregory Я подумал об этом, но хотел, чтобы соотношение между маленькими и большими ритами было несколько согласованным. Если бы это была текстура или уровень, я бы определенно сделал это (на самом деле есть предыдущий пример, который делает это).
AturSams
@NickWiggill Я могу полностью устранить коллинеарные линии. Это всего лишь вопрос настройки алгоритма. Должен быть способ улучшить его (обновить с последними изменениями)
AturSams