Программист, разработчик игр
0,0
рейтинг
27 октября 2015 в 19:52

Разработка → Изометрический плагин для Unity3D из песочницы



Сказ о том, как написать плагин для 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
Матвей Черевко @MATov
карма
11,0
рейтинг 0,0
Программист, разработчик игр
Реклама помогает поддерживать и развивать наши сервисы

Подробнее
Спецпроект

Самое читаемое Разработка

Комментарии (27)

  • +1
    Спасибо за описание алгоритма, может пригодится. У меня вопрос безотносительно вашего плагина и Unity3d, но про изометрию.

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

    Но хочется иметь специализированный паковщик для изометрических тайлов:
    • В случае с простыми одноуровневыми тайлами их можно упаковать плотнее срезая уголки (почти в 2 раза)
    • Повторялка краев чтобы избежать мерцания (по периметру ромба)
    • В игре использовать правильную геометрию — ромбик. Снижается fillrate в 2 раза, а также можно отключить альфа-блендинг.


    Как-то не хочется для ландшафта использовать квады с альфа блендингом, рисуя в 2 раза больше пикселей чем на самом деле надо. Но судя по отсутствию инструментария все так и делают?
    • 0
      Для общего случая уменьшения филлрейта (за счет использования прозрачных областей) в Юнити есть, так называемая, плотная упаковка текстур в атласы (tight packer policy). Потом это всё рисовать нужно не как два треугольника, естественно, а с жутко триангулированным мешем. Так плотно как в специфическом случаи тайлов не жмёт, но хоть что-то.
      Спасибо за наводку, запишу на подумать, как о возможной фиче в этот плагин.
  • 0
    Предложенная вами сортировка вытянутых убийственно проста и одновременно с тем убийственно медленная. Можете затестить сколько сравнений она у вас сделает имея в кадре 300 объектов, например.

    Гораздо более шустрое решение ИМХО можно получить сохраняя промежуточные данные между кадрами и меняя сортировку элементов только тогда, когда один из них меняет положение. Так можно ещё одного эффекта добиться, иногда полезного — можно сделать пересортировку минимальным количеством перестановок. Для этого вам нужно хранить кроме положения каждого элемента по каждой из двух координат и размеров ещё два List<List> вдоль каждой из координат. В первый вы записываете все элементы, которые в этой целочисленной координате начинаются вдоль данной оси, а во второй все элементы, которые в этой координате заканчиваются.

    Имея такую структуру данных вы в первый раз отсортируете элементы очень быстро, а при перемещении одного из элементов сможете делать изменение в минимальное количество перестановок. В изометрической игре, как правило, реально подвижных элементов не больше 10%.
    • 0
      Гораздо более шустрое решение ИМХО можно получить сохраняя промежуточные данные между кадрами и меняя сортировку элементов только тогда, когда один из них меняет положение.

      Да, всё так и сделано, забыл про это написать. Сортируется всё не каждый кадр, а только тогда, когда это нужно:
      • когда кто-то видимый сдвинулся
      • когда кто-то стал видимым

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

      Пытался сделать несколько таких вариантов, пока хорошего и удобного не получилось, но продолжаю поиски в фоновом режиме.
      • 0
        >> Пытался сделать несколько таких вариантов, пока хорошего и удобного не получилось, но продолжаю поиски в фоновом режиме.
        Для Юнити не так критично если вы не используете DestroyInstantly и рейтрейсинг после изменений в дереве. Потому что она всё равно дерево отображения перестраивает один раз за кадр. А вот для Флэши, которая перестроение всего дерева делала после каждого SwitchDepth это было огого как критично.

        Моё решение было такое — благодаря этим вот массивам, которые я описал выше легко искать ближайший элемент, который ниже, и ближайший элемент, который выше. Я вставляя новый элемент искал место в существующей сортировке, если обнаруживался конфликт, когда первый элемент который выше вставляемого оказывался ниже последнего элемента который ниже, я брал одну из этих элементов, например верхний и двигал по сортировке до максимально допустимого для него положения. После этого повторял и если всё ещё конфликт брал нижний и сдвигал его вниз. Обычно в одно-три движения конфликт разрешается.
  • +1
    Забудьте о всём что может выделять память, а в C# (а особенно в местном старом Mono) это может делать всё, начиная от foreach(!) заканчивая создающимися лямбдами, а уж какой-нибудь LINQ противопоказан даже в самых простых случаях.

    Случайно не этот LINQ?
    Для чего-то типа поиска пути просто юзать что-то типа такого?
    Где умные дяди сделали за меня кучу оптимизаций?
    • 0
      Сам сильно зауважал дядей писавших Linq с их оптимизациями когда попытался дополнить его своими функциями, делающими то же самое, что и последовательность из нескольких коробочных команд. К сожалению забыть о нём придётся по более банальной причине — некоторые его функции не работают на iOS. А учитывая соотношение доходов от iOS и Android в юнитёвых проектах это смертный приговор.
      • 0
        Не вводите людей в заблуждение.
        "LINQ for iOS" — Вот этот плагин заменяет библиотеку LINQ на работающую в iOS. Все отлично работает, проверено на личном опыте.
        • 0
          Или бесплатный но менее оптимизированный UniLinq или ещё много что. Но это не System.Linq
          Я не говорил, что System.Linq нельзя заменить. Я говорил только что его нельзя взять и использовать.
          • 0
            Скажем так — его можно использовать. А если дойдет до iOS, то просто и незаметно подключить другую LINQ-либу.
        • 0
          Судя по данной теме о нём, он работает только на mono, на il2cpp опять же не работает.
          Но и да, мой посыл был не в том, что работает, а что нет, а в производительности которую он может выдать. Удобно, круто, изящно, но не про скорость. Ибо аллокации на каждом шагу, а за это потом догоняет GC и даже без них цена использования выше, чем написать по старинке всё руками и развернуть все эти красивые конструкции.
          • 0
            У нас проект с этой либой. Все работает, естественно и в il2cpp (потому что другого под iOS сейчас нет)
            • 0
              Значит вы не используете то, что не работает. В теме, ссылку на которую я дал выше, автор сам об этом говорит.

              Правка:
              Но опять же не в том проблема. Проблема в цене, а цена высока.
              • 0
                Цена высока? $40?? Это цена 1 рабочего дня джуниор программиста с з/п 50 тыс.руб.
                • 0
                  Цена не в деньгах имелась в виду.
                  • 0
                    А я не про деньги?

                    Цена в деньгах — это цена 1 рабочего дня плохого программиста.
                    • 0
                      Я вот знаю, что кроме меньшей оптимизации UniLinq отличается ещё только одним: Если вы измените перебираемую коллекцию, он не выдаст экспешена сразу, так что возможны инконсистэнс или выход индекса за размеры массива, если вы ошибётесь, но больше никаких отличий мы не видели.

                      А чем отличается библиотека за $40? Я не знаю. И вы не знаете, я уверен. Поэтому если ничего не будет мне специальным образом мешать я буду использовать UniLinq. Не потому, что сорок баксов, а потому что чтобы чего не того.
                    • 0
                      Причем тут деньги вообще?! Остановитесь )
                      • 0
                        Тогда могу лишь повторить. У нас есть проект, где было использована куча несложных LINQ. При переходе на iOS просто подцепили «LINQ for iOS» и все заработало (в т.ч. в 64 битах, на последних девайсах и т.п.)

                        Да, никакие совсем уж хитрые конструкции не использовали. Но для наших целей — оно подошло на 100%, по этому и советую. Основываясь исключительно на собственном опыте.
                        • 0
                          Оно будет работать (половина функций в случае «LINQ for iOS»), вопрос Как и в цене за использование, а цена — это куча аллокаций на ровном месте, просаженный перфоманс, опять же на ровном месте, если вам это позволительно, то пожалуйста, используйте, просто будьте осторожны. Одно неверное движение и может случиться плохое, а потом эти страшные сны с участием GC, часы профайлинга, переписывания кусков кода и прочее.
          • 0
            Ну как бы не обязательно строгий запрет. Можно делать Linq-ом что-то что на нём будет понятнее и выполняется не больше раза в кадр и с небольшим количеством элементов. Конечно карту линковским перебором обежите — убъёте пол производительности. Иногда можно спроттипировать с линком и потом при причёсывании кода Linq оттуда элеминировать.
            • 0
              При написании частей чувствительных к производительности нужно вообще забыть не только про LINQ, но и про foreach, а бегать по карте обычным индексированным for'ом. На кол-ве объектов в несколько тыс. выигрыш производительности уже существенен.
  • 0
    Ы. Когда я последний раз брался за 3Д, а было это овер10 лет назад, для перехода от перспективной проекции к изометрической достаточно было заменить одну константу при инициализации окна.
    Че ж так все изменилось не в лучшую сторону то?
    • +1
      :) В том-то и дело, что это не 3д, это спрайты, не 3д модели, которые прикидываются оными. В общем большой частный случай 2D, который пытается казаться трехмерным.
  • +1
    3D движок рендерит 2D спрайты, пытающиеся казаться трёхмерными =)
    Простите за нубский вопрос, но в чём преимущество в использовании двухмерных спрайтов, имитирующих 3D, перед использованием 3D моделей? Например, спрайты в вашем примере очень похожи на lo-poly модельки. Неужели использование низкополигональных моделей дороже (в плане производительности и/или производства)?
    • 0
      Вопросов тут много и нужно смотреть глубже. В производство арта вообще, модели никогда не будут такие, какие их можно отрисовать. Скажу больше, что многие нынче делают сначала модель, потом её рендерят и далее обрисовывают уже рендер этот, чтобы получить изометрический спрайт. А примеры мои похожи на модели, что бы тестировать было проще и нагляднее.
    • +1
      У вас может быть совершенно гениальный 2D художник в распоряжении. Никакое 3D ни за какие деньги этого не заменяет. Вот это, например, наш за один день нарисовал:
      image

Только зарегистрированные пользователи могут оставлять комментарии. Войдите, пожалуйста.