Не боги атласы пакуют

Риторический ответы

Уже традиционная рубрика “Меня постоянно спрашивают подписчики, которых нет”

1. Что с DI?

   Ничего. Стоит на холде. В данный момент функционально там все готово. Все биндится, все ресолвится и вообще по красоте работает. Нет красивостей типа MonoContext, поддержки загрузки сцен при парентинге. Из запланированного не закончен плеер луп и месадж пайпы. Но так как это не двигает ни один из моих проектов, кроме как сам DI… я решил заморозить это все до лучших времен… А именно появления у меня прототипа игры, а не только идеи. Тогда можно будет обмазываться

2. Что с игрой?

   Да… я дропнул идею пилить игру командой, потому как все равно не вывезем в том объеме что было задумано. В данный момент курс примерно такой:

   • Учимся рисовать пиксель арт… это в целом уже в процессе и даже вроде получается
   • Переводим проект в статус “Миша все херня, давай по новой”. Упрощаем концепцию, переводим в другую плоскость геймплей (буквально, из 3d в 2d)
   • Клепаем прототип и не отвлекаемся на утилитарную разработку (кроме случаев, когда это нужно для прототипа)

3. Пока не придумал о чем еще можно написать… давайте к следующему блоку

Мы не пишем утилиты… ну почти не пишем

Актуальный мемчик про меня

Пока я учился рисовать в 2d используя замечательную программу aseprite (за которую можно и монетку занести, если хочется… что я и сделал) я задумался над некоторыми вопросами:

1. Импорт в наш любимый Unity.
   • Можно экспортировать png файлы, нарезать в юнити на спрайты… Но возникает проблема, как это дело склеивать в анимации. Каждый раз когда я меняю количество кадров делать это ручками? Чёт не весело…
   • Можно импортировать непосредственно файл *.ase. У Unity есть встроенный импорт с поддержкой слоев, анимаций и так далее… НО, мне плюсом к стандартному импорту, нужно уметь импортить дополнительные текстурки из самого файла: карты свечения, нормали (да, в 2d) и может еще чего… да и юнити анимации… но об этом в пункте 2
2. Анимации… в чем проблема анимаций Unity для 2d. То что они заточены под 3d. Это комбайн с расчетом блендингов, переменных, параметров, триггеров… когда со спрайтами всего лишь надо раз в какое то время менять спрайт в рендерере. Плюс есть проблема перехода. Стандартом в пиксельных спрайт анимациях считается 12 или (реже) 24 кадра в секунду. Этого достаточно, чтоб анимация выглядела плавно, но при этом резкой и стилистически корректной для пиксель арта. Переход из одной анимации в другую нужно осуществлять только на границах кадров, иначе возникает ощущения статтеров, но юнити аниматор так не умеет… переход можно настроить только на определенный таймнг после срабатывания условия, но в само условие нельзя воткнуть длину кадра и так далее.
3. Дополнительные данные… Мне нужны эвенты, данные о хитбоксах, данные о дамадж боксах и прочие дополнительные меты, которые удобнее размечать непосредственно на кадрах анимации. То есть делать некий доп слой с разметкой.

Из всего этого я сделал вывод: мне нужен свой формат анимаций, с кастомным редактором и возможностью автоматического импорта из aseprite. В итоге, так как к самой програмульке можно писать расширения на lua (тут даже есть api), я сделал экспорт в свой формат:

• Разметку файла пишу в папку как json
• Нужные изображения пишу рядом как png
• Зипую папочку
• Переименовываю зип в *.nts (neon tanto spritesheet)
• В Unity пишу свой импорт для данного расширения

Все шло бы хорошо, если бы я не наткнулся на проблему упаковки текстур в атласы. В Unity есть два варианта, на которые я делал ставку:

• Texture2D.GenerateAtlas. Этот вариант не работает. Даже если попросите упаковать его текстуру размером 100500 на 100500 в атлас не больше чем 256 на 256, оно вернет true и невалидные данные. К тому же надо знать размер атласа заранее… а я как бы не знаю.
• Texture2D.PackTextures. Уже лучше. Вариант работает, атлас генерируется… Но есть минусы, надо заранее прочитать все текстуры пакуемые, что не очень удобно в плане расходуемой памяти, так как все эти текстуры потом уйдут в утиль. Формат текстуры внутрянка устанавливает сама… например включает mip map и npot, а мне это вообще не надо… как сгенерировать нормал мапы с верным импортом - вообще не ясно.

На оба эти варианта я рассчитывал очень сильно, но не выгорело. Начал гуглить решения… и оказалось это NP полная задача… Она же Bin packing problem. Нет оказывается алгоритма, который гарантированно сделает круто кроме как полным перебором вариантов… есть куча эврестических и не очень методов, которые могут упаковать, но не факт что сработает. Давайте о них поподробнее… хотя… я лучше дам ссылки на статьи, которые читал - нежели буду их пересказывать:

• Про двумерную упаковку: offline алгоритмы
• Про двумерную упаковку: online алгоритмы
• Exploring rectangle packing algorithms
• И по мелочи кучка мелких артиклей, но самые важные эти три… так же интернет предлагает кучу мощных математических трудов с описанием алгоритмом в строгой научной манере… но я такое не люблю с вуза… проще надо как то быть, что ли

В общем что я выбрал:

• За основу берется алгоритм grid splitting. Это когда каждый новый прямоугольник делит область на несколько новых. Получается этакая динамическая сетка… примерно так
• В оригинальной статье с реализацией мужик сильно намудрил, потому упрощаем. На сетку делим хитрее и в то же время проще:
  • Работаем с целыми числами… мы не можем поделить пиксель пополам, потому и усложнения с вычислениями нам не нужны
  • Храним массивы вертикальных и горизонтальных линий для текущего атласа
  • При добавления нового прямоугольника добавляем правую и нижнюю координату как новые линии
  • Для каждой из пар линий формируем новые точки и сохраняем их в соответствующий массив в случае если точки не перекрыты уже размещенными прямоугольниками
  • Очищаем массив точек от точек, которые были перекрыты новым прямоугольником
  • Для линий и точек используем связанные списки, так как вставка в них происходит дешевле, чем в обычные списки, а нам надо будет обеспечивать частую вставку в середину списка, чтоб поддерживать нужную сортировку
  • Для каждого прямоугольника обходим все атласы по точкам слева направо, сверху вниз и если он влезает - вставляем, если нет, ищем атлас вставка в который возможна расширением общей области и при этом увеличение площади минимально
  • Стараемся держать атласы более “квадратными”

На словах казалось сложным, но по факту алгоритм был реализован примерно за один день… И даже опубликован на GitHub: Atlas Packer. Но скорее чисто чтоб поделится кодом с вами, а не чтоб распространить данную вещь. Примерно вот так оно работает, если делать все это дело по шагам:

Развитие

Сейчас штука не очень производительная. Сам алгоритм достаточно тяжелый, но все что проще выдает упаковку похуже (во всяком случае, все что я видел и пробовал). Бенчить я это не буду, мне нужно оно чисто в редакторе для импорта, который будет случаться не то чтоб часто. Но… тут можно подумать над оптимизациями хотя бы по памяти, например перейти на нативные коллекции, благо уже все нужные структуры данных в этих ваших интернетах имеются… но не факт что я этим займусь, надо прототип писать, не забываем!

Вместо послесловия

Вот вам робот. Вероятно именно он будет прыгать и бегать в прототипах… Точнее его блокаут, анимировать его я пока не стану.