![](https://habrastorage.org/files/032/000/6f4/0320006f472344e782f536c293e3099d.png)
Сказ о том, как написать плагин для Unity Asset Store, поломать голову над решением известных проблем изометрии в играх, да еще и немного денег на кофе с этого поиметь, а так же понять на сколько Unity имеет расширяемый редактор. Картинки, реализации, графики и мысли под катом.
Завязка
Дело было вечером, делать было нечего. Новый год не предвещал ничего особенного в программерской жизни (в отличии от личной, но это уже совсем другая история). Созрела идея тряхнуть сединой и написать хоть что-то личное и своё, да еще и нацеленное хоть на какую-нибудь коммерческую выгоду (чтобы грело душу, что разработки твои хоть кому-нибудь нужны, кроме работодателя). Всё это совпало с тем, что давно хотелось пощупать возможности расширения редактора Unity и оценить его площадку для продажи своих расширений движка.
Выделил день для изучения ассет-стора: модели, скрипты, интеграции с различными сервисами, с первого взгляда казалось, что всё уже написано, интегрировано, да ещё и в различных вариантах, различного качества исполнения и проработки, с разными ценами и поддержкой. Сразу сузил свой круг поиска:
- только код (так как программист)
- только 2D (так как чертовски люблю 2D + его вменяемая поддержка "из коробки" в Unity только-только появилась)
И тут вспомнилось мне сколько кактусов я съел и сколько мышей умерло, когда делали мы изометрическую игру, сколько времени было убито на поиск хороших решений и сколько копий сломано в попытках эту саму изометрию отсортировать и отрисовать. Унимая дрожь в руках, искал по разным ключевым и не очень словам и не видел ничего, кроме кучи арта в изометрии. Что ж, решено, будет плагин для изометрии.
Постановка целей
Первое что необходимо было сделать — коротко описать какие проблемы будет решать этот плагин и чем же он будет помогать в нелегком труде разработчика изометрической игры. Проблемы изометрии:
- сортировка объектов по удалённости для правильной их отрисовки
- расширение редактора для создания, расположения и передвижения изометрических объектов в редакторе
Основные задачи на первую версию были поставлены, срок я себе отвел 2-3 дня для первой черновой версии. Затягивать было нельзя, энтузиазм — штука хрупкая и если не видеть чего-то готового в первые дни, легко загубить его. Да и новогодние праздники не такие длинные как может показаться, а хотелось бы успеть выкатить первую версию именно в них.
Сортировка
Коротко изометрия — это попытка 2D спрайтам прикинуться и выглядеть 3D моделями, что выливается в различного рода проблемы. Основная проблема в том, что спрайты должны быть отсортированы в порядке их отрисовки, для избежания неверного взаимного перекрытия.
![](https://habrastorage.org/files/60f/22b/db9/60f22bdb9ed3434888232416258f4b37.png)
На скриншоте сначала рисуется зеленый спрайт (2,1), потом сверху него синий (1,1)
![](https://habrastorage.org/files/9ba/a39/c6c/9baa39c6cd3b4584a57bbf1be169c050.png)
На скриншоте показана неверная сортировка, когда сначала рисуется синий
Сортировка, в данном простом случае, не составит труда и существуют различные варианты, например:
- сортировать по экранной позиции Y, которая = (isoX + isoY) * 0.5 + isoZ
- рисовать от самой дальней изометрической ячейки слева-направо, сверху-вниз [(3,3),(2,3),(3,2),(1,3),(2,2),(3,1),...]
- и еще куча интересных и не очень способов
Все они хороши, быстры и работают, но только в случае вот таких одноклеточных объектов или вытянутых в высоту (isoZ) столбиков :) Меня же интересовало более общее решение для вытянутых по одной координате объектов, или вообще "заборов", которые не имеют ширины, но вытянуты в одном направлении с нужной высотой.
![](https://habrastorage.org/files/396/376/23d/39637623d1c147478ef0223501a0d240.png)
На скриншоте правильно отсортированные вытянутые объекты 3x1 и 1x3 с "заборами" размерами 3x0 и 0x3
И тут начинаются проблемы и начинается место где нужно принимать решение по какому пути идти:
- разбивать "многоклеточные" объекты на "одноклеточные", т.е. резать вертикальными полосками и сортировать эти полоски
- думать над другим вариантом сортировки, более сложным и интересным
Я выбрал второй вариант, не хотелось связываться с особой подготовкой арта, с нарезанием (даже автоматическим), особым подходом к логике. Для справки: первый способ использовался в известных играх Fallout 1 и Fallout 2, и полоски эти можно наблюдать, если распотрошить данные игры.
Второй подход не подразумевает критерия сортировки объектов, то есть нет какого-то специального вычисленного значения по которому можно их отсортировать. Кто не верит (а многие кто не делал изометрию — не верят), возьмите листочек и порисуйте объектики размерами 2x8 и, например, 2x2, если что-то получится и вы как-то исхитритесь вывести какое-то число для вычисления глубины и сортировки — добавьте в пример объектик 8x2 и попробуйте их отсортировать в разных положениях относительно друг друга.
Ладно, числа нет, но мы можем вычислить отношения между ними (грубо говоря кто-кого перекрывает), а это, в свою очередь, использовать в топологической сортировке. Зависимости объектов можно вычислить используя проекции изометрических координат на изометрические оси.
![](https://habrastorage.org/files/db0/1cd/835/db01cd8359494b35aaee399e197c972e.png)
На скриншоте у синего куба зависимость от красного
![](https://habrastorage.org/files/eb3/af1/0d0/eb3af10d0cf04c6ba48a481a0b039f3c.png)
На скриншоте у зеленого куба зависимость от синего
Псевдокод для определения зависимости по двум осям (с осью 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, который позволяет компонентам объекта выполняться в режиме редактора, то есть делать тоже самое, что и в игре.
Всё это было сделано, конечно, не без проблем и всяческих уловок, но не было проблемы над которой я бился больше пары часов (гугл, форумы и комьюнити помогали решать возникшие вопросы не описанные в документации).
![](https://habrastorage.org/files/df6/ae0/2ae/df6ae02aec294ca28d9a6ffcf1b81382.png)
На скриншоте мои 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 модели со всеми её детьми![](https://habrastorage.org/files/837/b52/c02/837b52c025b6485c95ede6c77a5b4ed3.gif)
А вот так всё получается в конечном итоге
Кастомные настройки изометрии
Тут всё относительно просто, просили сделать возможность задавать угол изометрии, аспект, высоту тайлов. Помучившись немного с математикой можно получить такое:
![](https://habrastorage.org/files/02b/f56/35e/02bf5635e5df46778915d43caf2bd846.gif)
Физика
А вот здесь интереснее. Так как изометрия симулирует 3д мир, то и физика должна быть трёхмерной, с высотой и прочим. Был придумал интересный трюк. Я дублирую все компоненты физики, такие как Rigidbody, Collider и прочее для изометрического мира. По этим описаниям и настройкам повторяю невидимый физический трёхмерный мир средствами самого движка и встроенного в него PhysX'а. Далее беру вычисленные данные симуляции и возвращаю в те дублирующие компоненты для изометрического мира. Таким же образом симулирую события столкновений и триггеров.
![](https://habrastorage.org/files/56c/c0b/199/56cc0b19987043bbb94baa257879b224.gif)
Гифка физической демки тулсета
Развязка и итоги
После реализации всех предложений на форуме, я решил поднять цену до 40 долларов и не выглядеть как дешевый плагин с пятью строчками кода. Буду очень рад вопросам и предложениям, а так же критикой статьи, так как на Хабр пишу в первый раз, спасибо. А теперь, на закуску, собранная статистика продаж по месяцам:
Месяц | 5$ | 40$ |
---|---|---|
январь | 12 | 0 |
февраль | 22 | 0 |
март | 17 | 0 |
апрель | 9 | 0 |
май | 9 | 0 |
июнь | 9 | 0 |
июль | 7 | 4 |
август | 0 | 4 |
сентябрь | 0 | 5 |
Комментарии (19)
kraidiky
28.10.2015 00:13Предложенная вами сортировка вытянутых убийственно проста и одновременно с тем убийственно медленная. Можете затестить сколько сравнений она у вас сделает имея в кадре 300 объектов, например.
Гораздо более шустрое решение ИМХО можно получить сохраняя промежуточные данные между кадрами и меняя сортировку элементов только тогда, когда один из них меняет положение. Так можно ещё одного эффекта добиться, иногда полезного — можно сделать пересортировку минимальным количеством перестановок. Для этого вам нужно хранить кроме положения каждого элемента по каждой из двух координат и размеров ещё два List<List> вдоль каждой из координат. В первый вы записываете все элементы, которые в этой целочисленной координате начинаются вдоль данной оси, а во второй все элементы, которые в этой координате заканчиваются.
Имея такую структуру данных вы в первый раз отсортируете элементы очень быстро, а при перемещении одного из элементов сможете делать изменение в минимальное количество перестановок. В изометрической игре, как правило, реально подвижных элементов не больше 10%.MATov
28.10.2015 10:15Гораздо более шустрое решение ИМХО можно получить сохраняя промежуточные данные между кадрами и меняя сортировку элементов только тогда, когда один из них меняет положение.
Да, всё так и сделано, забыл про это написать. Сортируется всё не каждый кадр, а только тогда, когда это нужно:
- когда кто-то видимый сдвинулся
- когда кто-то стал видимым
Так можно ещё одного эффекта добиться, иногда полезного — можно сделать пересортировку минимальным количеством перестановок.
Пытался сделать несколько таких вариантов, пока хорошего и удобного не получилось, но продолжаю поиски в фоновом режиме.kraidiky
28.10.2015 12:11>> Пытался сделать несколько таких вариантов, пока хорошего и удобного не получилось, но продолжаю поиски в фоновом режиме.
Для Юнити не так критично если вы не используете DestroyInstantly и рейтрейсинг после изменений в дереве. Потому что она всё равно дерево отображения перестраивает один раз за кадр. А вот для Флэши, которая перестроение всего дерева делала после каждого SwitchDepth это было огого как критично.
Моё решение было такое — благодаря этим вот массивам, которые я описал выше легко искать ближайший элемент, который ниже, и ближайший элемент, который выше. Я вставляя новый элемент искал место в существующей сортировке, если обнаруживался конфликт, когда первый элемент который выше вставляемого оказывался ниже последнего элемента который ниже, я брал одну из этих элементов, например верхний и двигал по сортировке до максимально допустимого для него положения. После этого повторял и если всё ещё конфликт брал нижний и сдвигал его вниз. Обычно в одно-три движения конфликт разрешается.
BIanF
28.10.2015 06:10+1Забудьте о всём что может выделять память, а в C# (а особенно в местном старом Mono) это может делать всё, начиная от foreach(!) заканчивая создающимися лямбдами, а уж какой-нибудь LINQ противопоказан даже в самых простых случаях.
Случайно не этот LINQ?
Для чего-то типа поиска пути просто юзать что-то типа такого?
Где умные дяди сделали за меня кучу оптимизаций?kraidiky
28.10.2015 09:24Сам сильно зауважал дядей писавших Linq с их оптимизациями когда попытался дополнить его своими функциями, делающими то же самое, что и последовательность из нескольких коробочных команд. К сожалению забыть о нём придётся по более банальной причине — некоторые его функции не работают на iOS. А учитывая соотношение доходов от iOS и Android в юнитёвых проектах это смертный приговор.
soulburner
29.10.2015 22:35Не вводите людей в заблуждение.
"LINQ for iOS" — Вот этот плагин заменяет библиотеку LINQ на работающую в iOS. Все отлично работает, проверено на личном опыте.kraidiky
29.10.2015 22:59Или бесплатный но менее оптимизированный UniLinq или ещё много что. Но это не System.Linq
Я не говорил, что System.Linq нельзя заменить. Я говорил только что его нельзя взять и использовать.soulburner
29.10.2015 23:14Скажем так — его можно использовать. А если дойдет до iOS, то просто и незаметно подключить другую LINQ-либу.
MATov
29.10.2015 23:12Судя по данной теме о нём, он работает только на mono, на il2cpp опять же не работает.
Но и да, мой посыл был не в том, что работает, а что нет, а в производительности которую он может выдать. Удобно, круто, изящно, но не про скорость. Ибо аллокации на каждом шагу, а за это потом догоняет GC и даже без них цена использования выше, чем написать по старинке всё руками и развернуть все эти красивые конструкции.soulburner
29.10.2015 23:15У нас проект с этой либой. Все работает, естественно и в il2cpp (потому что другого под iOS сейчас нет)
MATov
29.10.2015 23:17Значит вы не используете то, что не работает. В теме, ссылку на которую я дал выше, автор сам об этом говорит.
Правка:
Но опять же не в том проблема. Проблема в цене, а цена высока.
kraidiky
29.10.2015 23:23Ну как бы не обязательно строгий запрет. Можно делать Linq-ом что-то что на нём будет понятнее и выполняется не больше раза в кадр и с небольшим количеством элементов. Конечно карту линковским перебором обежите — убъёте пол производительности. Иногда можно спроттипировать с линком и потом при причёсывании кода Linq оттуда элеминировать.
vanxant
28.10.2015 13:33Ы. Когда я последний раз брался за 3Д, а было это овер10 лет назад, для перехода от перспективной проекции к изометрической достаточно было заменить одну константу при инициализации окна.
Че ж так все изменилось не в лучшую сторону то?MATov
28.10.2015 13:47+1:) В том-то и дело, что это не 3д, это спрайты, не 3д модели, которые прикидываются оными. В общем большой частный случай 2D, который пытается казаться трехмерным.
inborn_killer
29.10.2015 13:34+13D движок рендерит 2D спрайты, пытающиеся казаться трёхмерными =)
Простите за нубский вопрос, но в чём преимущество в использовании двухмерных спрайтов, имитирующих 3D, перед использованием 3D моделей? Например, спрайты в вашем примере очень похожи на lo-poly модельки. Неужели использование низкополигональных моделей дороже (в плане производительности и/или производства)?MATov
29.10.2015 13:48Вопросов тут много и нужно смотреть глубже. В производство арта вообще, модели никогда не будут такие, какие их можно отрисовать. Скажу больше, что многие нынче делают сначала модель, потом её рендерят и далее обрисовывают уже рендер этот, чтобы получить изометрический спрайт. А примеры мои похожи на модели, что бы тестировать было проще и нагляднее.
kraidiky
29.10.2015 14:01+1У вас может быть совершенно гениальный 2D художник в распоряжении. Никакое 3D ни за какие деньги этого не заменяет. Вот это, например, наш за один день нарисовал:
Vavius
Спасибо за описание алгоритма, может пригодится. У меня вопрос безотносительно вашего плагина и Unity3d, но про изометрию.
Допустим мы хотим положить наши 2д тайлы в атлас. В случае с простыми прямоугольными тайлами (как в марио) есть множество инструментов для упаковки атласов с возможностью повторения граничных пикселей — более-менее стандартный способ избежать мерцания на стыках, возникающего из-за интерполяции текстур.
Но хочется иметь специализированный паковщик для изометрических тайлов:
Как-то не хочется для ландшафта использовать квады с альфа блендингом, рисуя в 2 раза больше пикселей чем на самом деле надо. Но судя по отсутствию инструментария все так и делают?
MATov
Для общего случая уменьшения филлрейта (за счет использования прозрачных областей) в Юнити есть, так называемая, плотная упаковка текстур в атласы (tight packer policy). Потом это всё рисовать нужно не как два треугольника, естественно, а с жутко триангулированным мешем. Так плотно как в специфическом случаи тайлов не жмёт, но хоть что-то.
Спасибо за наводку, запишу на подумать, как о возможной фиче в этот плагин.