[Из песочницы] Изометрический плагин для Unity3D27.10.2015 21:03

Сказ о том, как написать плагин для Unity Asset Store, поломать голову над решением известных проблем изометрии в играх, да еще и немного денег на кофе с этого поиметь, а так же понять на сколько Unity имеет расширяемый редактор. Картинки, реализации, графики и мысли под катом.

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

Выделил день для изучения ассет-стора: модели, скрипты, интеграции с различными сервисами, с первого взгляда казалось, что всё уже написано, интегрировано, да ещё и в различных вариантах, различного качества исполнения и проработки, с разными ценами и поддержкой. Сразу сузил свой круг поиска:

только код (так как программист)
только 2D (так как чертовски люблю 2D + его вменяемая поддержка "из коробки" в Unity только-только появилась)

И тут вспомнилось мне сколько кактусов я съел и сколько мышей умерло, когда делали мы изометрическую игру, сколько времени было убито на поиск хороших решений и сколько копий сломано в попытках эту саму изометрию отсортировать и отрисовать. Унимая дрожь в руках, искал по разным ключевым и не очень словам и не видел ничего, кроме кучи арта в изометрии. Что ж, решено, будет плагин для изометрии.
Первое что необходимо было сделать — коротко описать какие проблемы будет решать этот плагин и чем же он будет помогать в нелегком труде разработчика изометрической игры. Проблемы изометрии:

сортировка объектов по удалённости для правильной их отрисовки
расширение редактора для создания, расположения и передвижения изометрических объектов в редакторе

Основные задачи на первую версию были поставлены, срок я себе отвел 2-3 дня для первой черновой версии. Затягивать было нельзя, энтузиазм — штука хрупкая и если не видеть чего-то готового в первые дни, легко загубить его. Да и новогодние праздники не такие длинные как может показаться, а хотелось бы успеть выкатить первую версию именно в них.
Коротко изометрия — это попытка 2D спрайтам прикинуться и выглядеть 3D моделями, что выливается в различного рода проблемы. Основная проблема в том, что спрайты должны быть отсортированы в порядке их отрисовки, для избежания неверного взаимного перекрытия.

На скриншоте сначала рисуется зеленый спрайт (2,1), потом сверху него синий (1,1)

На скриншоте показана неверная сортировка, когда сначала рисуется синий

Сортировка, в данном простом случае, не составит труда и существуют различные варианты, например:

сортировать по экранной позиции Y, которая = (isoX + isoY) * 0.5 + isoZ
рисовать от самой дальней изометрической ячейки слева-направо, сверху-вниз [(3,3),(2,3),(3,2),(1,3),(2,2),(3,1),...]
и еще куча интересных и не очень способов

Все они хороши, быстры и работают, но только в случае вот таких одноклеточных объектов или вытянутых в высоту (isoZ) столбиков :) Меня же интересовало более общее решение для вытянутых по одной координате объектов, или вообще "заборов", которые не имеют ширины, но вытянуты в одном направлении с нужной высотой.

На скриншоте правильно отсортированные вытянутые объекты 3x1 и 1x3 с "заборами" размерами 3x0 и 0x3

И тут начинаются проблемы и начинается место где нужно принимать решение по какому пути идти:

разбивать "многоклеточные" объекты на "одноклеточные", т.е. резать вертикальными полосками и сортировать эти полоски
думать над другим вариантом сортировки, более сложным и интересным

Я выбрал второй вариант, не хотелось связываться с особой подготовкой арта, с нарезанием (даже автоматическим), особым подходом к логике. Для справки: первый способ использовался в известных играх Fallout 1 и Fallout 2, и полоски эти можно наблюдать, если распотрошить данные игры.

Второй подход не подразумевает критерия сортировки объектов, то есть нет какого-то специального вычисленного значения по которому можно их отсортировать. Кто не верит (а многие кто не делал изометрию — не верят), возьмите листочек и порисуйте объектики размерами 2x8 и, например, 2x2, если что-то получится и вы как-то исхитритесь вывести какое-то число для вычисления глубины и сортировки — добавьте в пример объектик 8x2 и попробуйте их отсортировать в разных положениях относительно друг друга.

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

На скриншоте у синего куба зависимость от красного

На скриншоте у зеленого куба зависимость от синего

Псевдокод для определения зависимости по двум осям (с осью Z аналогично):

bool IsIsoObjectsDepends(IsoObject obj_a, IsoObject obj_b) {
  var obj_a_max_size = obj_a.position + obj_a.size;
  return
    obj_b.position.x < obj_a_max_size.x &&
    obj_b.position.y < obj_a_max_size.y;
}

С помощью такого подхода строим зависимости между объектами и рекурсивно проходимся по всем объектам и их зависимостям выставляя дисплейную Z координату. Подход довольно универсальный, а главное работает. Подробнее описание этого алгоритма можно почитать, например, тут и тут. А еще этот подход используется в популярной flash-библиотеке для изометрии (as3isolib).

Всё бы хорошо, да вот алгоритмическая сложность данного подхода O(N^2), так как для построения зависимостей нужно сравнить каждый объект с каждым. Но оптимизации были отложены на более поздние версии, разве что я сделал ленивую пересортировку, что бы ничего не сортировалось, когда ничего не двигается. Об оптимизациях позже.

Цели были поставлены следующие:

сортировка объектов должна работать в редакторе (не только в игре)
должны быть другие Gizmos-Arrow (стрелки перемещения объектов)
опциональное выравнивание по тайлам при перемещениях
автоматическое применение размеров тайлов и их задание в инспекторе изометрического мира
рисование AABB объектов с изометрическими размерами
вывод изометрических координат в инспекторе объекта, при смене которых меняется положение самого объекта в игровом мире

Все цели были достигнуты, Unity действительно позволяет сильно расширять свой редактор. Добавлять новые вкладки, окна, кнопки, новые поля в инспектор объектов, при желании можно сделать даже свой кастомый инспектор для компонента нужного типа. Выводить дополнительную информации в окне редактора (в моём случаи AABB объектов), заменять стандартные стрелки перемещения объектов тоже можно. Сортировка внутри редактора была решена магическим флажком ExecuteInEditMode, который позволяет компонентам объекта выполняться в режиме редактора, то есть делать тоже самое, что и в игре.

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

На скриншоте мои gizmos для перемещения объектов в изометрическом мире

Первая версия написана, скриншоты сделаны, иконка кое-как нарисована, описание составлено. Пора. Выставляю символическую цену в 5 долларов, заливаю плагин в стор и жду результатов аппрува со стороны Unity. Над ценой долго не думал, не было цели заработать, была цель узнать есть ли вообще спрос, а если есть, то какой. Так же была цель помочь разработчикам изометрических игр, которых почему-то совсем обделили на возможности и дополнения.

Мучительные 5 дней (примерно столько же я потратил на написание первой версии, но я знал что делал, без особых поисков и дум, что дало мне бОльшую скорость по сравнению с людьми, которые только начинают копать в сторону изометрии) и пришло письмо от Unity, что плагин одобрен и можете идти любоваться им в сторе и смотреть нулевые (пока) продажи. Отметился на местном форуме, встроил Google Analytics на страницу в сторе и стал ждать с моря погоды.

Долго ждать не пришлось и пошли первые продажи, а так же отзывы на форуме и в сторе. За оставшийся январь было продано 12 копий плагина, я посчитал это присутствующим интересом к нему и продолжил.

Основные претензии были к двум вещам:

Алгоритмическая сложность сортировки — O(N^2)
Проблемы со сборщиком мусора и общей производительностью

Алгоритм

При 100 объектах и O(N^2) было 10'000 проверок, что бы только найти зависимости, а еще нужно по всем ним пройтись и дисплейный Z выставить для сортировки. Нужно было что-то решать. В конечном итоге я перепробовал огромную кучу вариантов, не мог спать мучаясь над решениями. Не буду описывать все опробованные механизмы, опишу лучше на чем остановился в данный момент.

Во-первых, естественно, сортируем только видимое. Это значит, что нужно постоянно знать кто в кадре, при появлении в кадре добавлять объект в сортировку, при уходе — забывать. Юнити не даёт нам возможность узнать Bounding Box объекта вместе с его детьми в дереве сцены, пробегать по всем детям (причем каждый раз, потому что они могут добавляться и удаляться) не вариант — медленно. События OnBecameVisible и иже с ними тоже нельзя, потому что работают только для родительского объекта. Зато есть возможность получить все Renderer компоненты из нужного объекта и его детей. Вариант этот не блещет красотой, но такого же универсального способа с приемлемой производительностью я не нашел.

List<Renderer> _tmpRenderers = new List<Renderer>();

bool IsIsoObjectVisible(IsoObject iso_object) {
  iso_object.GetComponentsInChildren<Renderer>(_tmpRenderers);
  for ( var i = 0; i < _tmpRenderers.Count; ++i ) {
    if ( _tmpRenderers[i].isVisible ) {
      return true;
    }
  }
  return false;
}

Тут есть тонкость, что используется функция GetComponentsInChildren, с помощью которой можно получить компоненты без аллокаций в нужный буффер, в отличии от той, что возвращает новый массив с компонентами

Во-вторых, нужно всё равно что-то делать с O(N^2). Я пробовал многие варианты разбития пространства, но остановился на простой двухмерной сетке в дисплейном пространстве, куда я проецирую свои изометрические объекты, в каждом такой секторе содержится список изометрических объектов, которые его пересекают. Идея простая: если проекции объектов не пересекаются, то и зависимости между объектами строить смысла нет. Далее бежим по всем видимым объектам и строим зависимости только в нужных секторах, тем самым понижая алгоритмическую сложность и увеличивая драгоценное быстродействие. Размер сектора выбираю как среднее между размерами всех объектов, результат меня устроил.

Общая производительность

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

Также там узнаёшь о боли сборщика мусора. Нужна производительность? Забудьте о всём что может выделять память, а в C# (а особенно в местном старом Mono) это может делать всё, начиная от foreach(!) заканчивая создающимися лямбдами, а уж какой-нибудь LINQ противопоказан даже в самых простых случаях. В конечном итоге из красивых синтаксических конструкций и прочего сахара C# превращается в этакий Си со смешными возможностями.

Приведу полезные ссылки по теме:
Часть1, Часть2, Часть3

Результаты

Я никогда не видел, чтобы так улучшали этот алгоритм, поэтому особенно был рад результатам. Если в первых версиях буквально на 50 двигающихся объектах игра превращалась в слайд-шоу, то сейчас на 800 объектов в кадре — всё крутится на запредельных скоростях, пересортировываясь всего за 3-6мс, что для такого количества объектов и изометрии оооочень хорошо. Плюс после инициализации почти не выделяя в кадре памяти вообще.
После прочтения отзывов и предложения назрели несколько возможностей, которые я добавил в последних релизах.

Микс 2D и 3D

Смешивание 2d и 3d в изометрических играх интересная возможность, которая позволяет минимизировать отрисовку разных вариантов движения и поворотов (например 3д модели персонажей с анимациями). Делается не сложно, но нужно встроить это всё в систему сортировки. Всего лишь нужен Bounding Box модели со всеми детьми и сдвигать модель по дисплейному Z на его ширину.

Bounds IsoObject3DBounds(IsoObject iso_object) {
  var bounds = new Bounds();
  iso_object.GetComponentsInChildren<Renderer>(_tmpRenderers);
  if ( _tmpRenderers.Count > 0 ) {
    bounds = _tmpRenderers[0].bounds;
    for ( var i = 1; i < _tmpRenderers.Count; ++i ) {
      bounds.Encapsulate(_tmpRenderers[i].bounds);
    }
  }
  return bounds;
}

Так можно вычислить Bounding Box модели со всеми её детьми

А вот так всё получается в конечном итоге

Кастомные настройки изометрии

Тут всё относительно просто, просили сделать возможность задавать угол изометрии, аспект, высоту тайлов. Помучившись немного с математикой можно получить такое:

Физика

А вот здесь интереснее. Так как изометрия симулирует 3д мир, то и физика должна быть трёхмерной, с высотой и прочим. Был придумал интересный трюк. Я дублирую все компоненты физики, такие как Rigidbody, Collider и прочее для изометрического мира. По этим описаниям и настройкам повторяю невидимый физический трёхмерный мир средствами самого движка и встроенного в него PhysX'а. Далее беру вычисленные данные симуляции и возвращаю в те дублирующие компоненты для изометрического мира. Таким же образом симулирую события столкновений и триггеров.

Гифка физической демки тулсета

После реализации всех предложений на форуме, я решил поднять цену до 40 долларов и не выглядеть как дешевый плагин с пятью строчками кода. Буду очень рад вопросам и предложениям, а так же критикой статьи, так как на Хабр пишу в первый раз, спасибо. А теперь, на закуску, собранная статистика продаж по месяцам:

Месяц	5$	40$
январь	12	0
февраль	22	0
март	17	0
апрель	9	0
май	9	0
июнь	9	0
июль	7	4
август	0	4
сентябрь	0	5