Прямоугольная упаковка со статическими прямоугольниками

Question

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

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

Есть ли другой алгоритм, который я должен рассмотреть, или, возможно, более эффективный способ сделать это?

Answer 1

Я бы сказал, что хорошее место для начала было бы здесь: http://en.wikipedia.org/wiki/Bin_packing_problem

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

Надеюсь, это поможет. Приветствия.