Проблема с упаковкой вновь - PullRequest
Новая
       66

Проблема с упаковкой вновь

3 голосов
/ 23 декабря 2010

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

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

+------------+---------+------------+
| 0          | 1       | 2          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 3          | 4       | 5          |
|            |         |            |
|            |         |            |
+------------+---------+------------+
| 6          | 7       | 8          |
|            |         |            |
|            |         |            |
|            |         |            |
+------------+---------+------------+

, в котором каждая угловая ячейка имеет размер 4x4, а центральная - 3x3 (так что оставшиеся ячейки имеют размер 3x4 и 4x3).Затем у меня есть набор элементов для размещения внутри этих блоков, которые могут варьироваться от 1x1 до 3x3 (я не думаю, что 4x4 нужен, но это ничего не должно изменить).Конечно, эти элементы не могут пересекать линии и должны полностью находиться в одном блоке.

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

Бонусный вопрос: если предположить другие блоки в дополнение к этим 9 (может быть, другие 3-4), как я мог бы расставить приоритеты по сравнению сновые?(Я имею в виду просто не использовать дополнительный блок, пока не будет достигнут порог заполнения) ..

Конечно, я ищу общую идею, без реализации:)

1 Ответ

7 голосов
/ 23 декабря 2010

Эта проблема 2D Bin Packing выглядит так: NP hard .

Вот несколько вариантов:

  • Грубая сила или, что еще лучше, ветвь и связка. Не масштабируется (вообще!), Но найдет для вас оптимальное решение (возможно, не при нашей жизни).

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

  • Метаэвристика, начиная с результата детерминированного алгоритма. Это даст вам очень хороший результат в разумные сроки, лучше, чем люди придумали. В зависимости от того, сколько времени вы уделяете этому и сложности проблемы, это может быть или не быть оптимальным решением. Существует несколько библиотек, таких как Drools Planner (java с открытым исходным кодом).

...