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

Question

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

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

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

Answer 1

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

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

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