Эффективное размещение коробок в воксельной среде

Question

У меня есть произвольный набор вокселей, которые определяют комнату для игры. Моя цель - разместить в этой комнате различные предметы (привязанные к размеру вокселей) в соответствии с определенными правилами для пропеллера. Несколько простых примеров правил (размеры вокселей - xyz, а реквизитов гораздо больше, чем только эти три):

• Книжная полка (2x3x1) должна быть размещена у стены и земли.
• Стол (4x1x2) должен быть размещен на земле.
• Настенную лампу (1x1x1) необходимо разместить у стены.

Реквизит не может пересекаться с другими реквизитами или с существующими вокселями. Я пытаюсь найти некоторые эффективные структуры данных и / или алгоритмы, которые могут позволить мне сделать это довольно быстро. Мой текущий метод таков:

• Создайте набор S из возможных положений пропеллера, который представляет собой набор пустых вокселей, которые находятся рядом с заполненными вокселями.
• Отметьте каждый элемент в S, если это пол, стена, угол и т. Д.
• Выберите опору P для размещения.
• Выберите подмножество S' S, которое соответствует правилам размещения опоры (только стена, угол и т. Д.).
• Выберите произвольный элемент E из S'.
• Вот неоптимальная часть: попытайтесь как-то подогнать P вокруг E. Посмотрите, позволяет ли граница P поместить его поверх E, не пересекаясь с другими подпорками и вокселями. Если он не подходит, попробуйте повернуть и / или перевести границы P, пока он не окажется в допустимом месте, содержащем E.
• Если это может соответствовать, тогда обновите S, чтобы включить новую опору, и начните размещать больше опоры.
• Если он по-прежнему не подходит, выберите другой произвольный элемент из S' и попробуйте снова.

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

Было бы идеально, если бы я мог как-то учесть размеры P при выборе E. Я пытался создать трехмерную карту свертки воксельной сетки (по сути, создавая размытое изображение сетки), чтобы у каждого вокселя были некоторые приблизительные данные о том, сколько места вокруг него, но проблема в том, что мне нужно обновить карту каждый раз, когда я ставлю новую опору, которая звучит дорого.

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

TLDR: Как бы ты программно украсил дом в Minecraft, используя украшения, которые могут быть больше, чем один воксель?

Answer 1

Если у вас не так много вокселей в S, после создания стен и полов вы можете просто создать 3 исчерпывающих набора допустимых мест размещения, по одному для каждого типа пропеллера. Давайте назовем множество допустимых мест размещения для реквизита типа p ValidPlacements(p).

Затем, когда вы успешно поместите новый объект в мир, для каждого типа пропера p сгенерируйте набор мест размещения типа p, которые будут пересекаться по крайней мере в 1 вокселе с только что размещенным объектом, и удалите их из ValidPlacements (p)., (Некоторые из этих размещений могут уже отсутствовать, потому что они, как уже было известно, невозможны из-за ранее размещенных объектов - это не условие ошибки, его можно просто игнорировать.) Используйте хеш-таблицу или сбалансированную древовидную структуру для хранения каждого набор мест размещения, так что каждое из них можно найти и удалить за время O(1) или O(log n) соответственно

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

Пример: размещение книжной полки с верхним левым-крайним передним углом в точке (x, y, z) исключит 2*3*1 = 6 возможных размещений ламп (т. Е. 1 размещение для каждого вокселя, теперь занятого таблицей), и большее количество мест на столах и книжных полках (т.е. 1 место на каждое возможное место, которое каким-либо образом перекрывалось бы с только что размещенной книжной полкой).