Проблемы имеющихся подходов к оптимизации

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

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

• Замена системы определения столкновений на QuadTree

• Подготовка игровой карты с как можно меньшим числом объектов, участвующих в расчёте столкновений. Если у вас есть какая-то зона с тайлами, для которых надо просчитывать столкновения, то лучше считать их только для тайлов на границе этой зоны, но не считать внутри. Что, однако, увеличивает вероятность «застрять в текстуре»

  

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

• Экономия на лишних вызовах updateTree – не нужно считать логику для объектов, когда это реально не требуется

• Не добавлять объекты с разными priority к одному родителю.

• Объединять большие количества PositionComponent в статические картинки, чтобы не вызывать renderTree для большого числа объектов. При этом в зависимости от ситуации для хранения пререндеренной картинки лучше подойдёт либо Image, либо Picture, либо даже их сочетание

• По аналогии – объединять объекты с одной и той же анимацией в один большой анимированный объект, что уменьшит как количество вызовов uptateTree, так и число вызовов renderTree.

Комбинирование этих методов может впечатляюще увеличить производительность. Подробно про QuadTree я писал здесь. Про остальные способы «разогнать» Flame – здесь. Но все эти методы имеют несколько критических недостатков:

1. Они работают «каждый сам за себя». В текущей реализации нет возможности переиспользовать вычисления, сделанные для одной подсистемы, в другой подсистеме.

2. Они работают только на всю карту, начиная с QuadTree, заканчивая пререндером компонентов в специальные слои. А карта может быть не просто очень большой, а, например, бесконечной и процедурно-генерируемой. Что делать, если мы никогда не знаем полный размер нашей карты? Что делать, если на протяжении игры игровое поле может расти без ограничений?

3. Объединение компонентов в пререндеренные слои приводит к формированию больших изображений. Перерисовка этих изображений – дорогая операция. Кроме того, на некоторых системах, судя по репорту на гитхабе, и рендер такого большого пререндеренного слоя может оказаться проблематичным, что вызовет падение FPS.

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

Как объединить разные алгоритмы

Давайте поделим игровое пространство на равномерную сетку, что-то вроде шахматной доски, но в каждой клетке может находиться неограниченное число объектов.

Полученные «ячейки» игрового пространства мы можем использовать сразу для множества задач:

1. Определение столкновений в "широкой фазе"

2. Оптимизация рендера (не рендерить удалённые от игрока ячейки)

3. Оптимизация игровой логики: не вызывать или вызывать реже update() и updateTree() для компонентов в очень удалённых ячейках

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

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

1. https://en.wikipedia.org/wiki/Grid_(spatial_index)

2. http://noregret.org/tutor/n/grid/

3. https://gameprogrammingpatterns.com/spatial-partition.html

Поэтому, думаю, стоит представить нашего «героя». Знакомьтесь: Spatial Partition, он же Spatial Grid, он же Spatial Index… на русском я так и не понял, как это назвать, чтобы адекватно загуглить.

Важный момент. Чтобы не погрязнуть в сложной логике и математике (нам и без этого проблем хватит), предлагаю принять за правило несколько моментов:

1. Размер ячейки должен быть больше размера любого из игровых объектов.

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

3. Ячейка не должна быть слишком большой. Она должна включать в себя столько объектов, сколько система сможет обработать быстро, без особой нагрузки.

Если не соблюдать эти правила, то мы рискуем не получить желаемого прироста производительности, или столкнуться с необходимостью дополнительных сложных вычислений, как, например, описано тут: http://noregret.org/tutor/n/grid/#3

Почему QuadTree не подходит

Конечно, можно спросить, а зачем нам какая-то отдельная сетка, не гибкая, не учитывающая плотность игровых объектов на карте, если есть уже такой классный QuadTree? Отвечу:

1. QuadTree должен знать размеры карты. А для Spatial Grid вообще не важно, есть ли у карты размер. Можно генерировать бесконечное число ячеек, начиная отсчёт от точки, в которой появляется игрок. Карта может быть ограничена определённым размером на старте игры, но в процессе увеличиваться бесконечно.

2. QuadTree слишком дорого перестраивать. Чтобы отреагировать на изменение размеров карты, необходимо просканировать всё игровое поле, чтобы заново учесть плотность объектов на нем. А для Spatial Grid достаточно добавить новую ячейку в ту точку координат, где её ещё нет

   

3. Ячейка QuadTree имеет непредсказуемое положение, непредсказуемый размер, момент её появления или исчезновения также довольно случаен. Это затрудняет использование QuadTree каком-либо другим алгоритмом, например для пререндера групп объектов в картинку. А Spatial Grid делит пространство на равные части с известным размером и постоянным положением.

4. QuadTree – это дерево с иерархией. Текущая ячейка содержит ссылку на дочерние меньшего размера, и на родительские – большего. И в случае, если объект находится на границе нескольких ячеек, нужно собирать все объекты не только вниз, но и вверх по иерархии. Если объект находится ровно по центру карты – вообще никакой оптимизации не будет, придётся проводить сравнение со всеми объектами в игре. SpatialGrid же работает гарантированно только с ячейкой, в которой находится объект, и с 8ю окружающими его ячейками – на случай, если объект пересекает границу. Это не мало, но по крайней мере больше точно не станет.

Реализация для Flutter Flame

Для Flame я сделал отдельную библиотеку, подключить её в свой проект можно отсюда: https://github.com/ASGAlex/flame_spatial_grid

На момент публикации статьи библиотека ещё в «альфа» стадии разработки, там возможны радикальные изменения, плюс я ещё не тестировал её на совместимость с таким функционалом Flame как рейкастинг.

Что библиотека может:

1. Отрисовывать объекты, входящие только в те ячейки, которые окружают игрока

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

3. Выгружать из памяти объекты, находящиеся слишком далеко от игрока, чтобы он мог быстро к ним вернуться. В принципе, можно сохранить информацию о состоянии объектов в ячейке на диск, и вытянуть их оттуда позже, если игрок снова приблизится к выгруженной ячейке достаточно близко

   

4. На лету генерировать игровое поле и объекты на нем, в случае перехода игрока в новую, ранее не существующую ячейку. Игровое поле становится потенциально бесконечным с возможностью процедурной генерации

   

5. Для оптимизации рендеринга не генерировать огромные пререндеренные картинки на всё игровое поле, с которыми у графического адаптера могут возникнуть сложности. Можно генерировать много маленьких «пре-рендеров», размером совпадающих с размером ячейки. Это будет эффективнее, чем рендер множества отдельных объектов.

Бенчмарк

В статье про QuadTree я проводил замеры, используя карту размером 160 000 тайлов с 22 000 объектов на ней. Для Spatial Grid эти условия удастся воссоздать лишь в приближенном виде, поскольку размер карты определяется динамически и обрабатывается не вся карта сразу, а лишь её «играбельная» область в непосредственной близости от игрока.

Условия для замеров следующие:

• Замер на 22 000 объектов: активная область вокруг игрока 5 на 5 ячеек, ещё на 3 ячейки после окончания «активной зоны» идёт зона, в которой компоненты уже не отображаются, но производится расчёт логики и столкновений.

• Замер на 640 000 объектов: активная область та же, 5 на 5 ячеек, но после неё идёт ещё 10 ячеек с неотображаемыми, но обсчитываемыми компонентами.

• В обоих тестах в каждой ячейке расположено 200 компонентов с простыми спрайтами и 200 компонентов с анимацией.

• Перед запуском подсчёта пришлось осуществить «прогрев» игры, чтобы нагенерировалось нужное число компонентов. Т.к. по-умолчанию создаётся только «активная зона» 5 на 5 ячеек, а все остальные зоны появляются только вследствие ухода игрока из активных зон.

• Гонял всё на i5-8265U + 16 гигов оперативки.

Полученные результаты:

Важный момент, нагрузка в данном случае перераспределяется с процессора на видеокарту, поэтому время на update() может быть постоянно низким, при этом FPS может падать. Например, в зависимости от зума игрового поля. Или от того, отображается ли FPS на экране и отладочная сетка. Вот, сравните этот вариант:

И этот:

Почему это работает быстрее и как пользоваться

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

Основной объект оптимизации - это "пассивные объекты", которые редко изменяют свой размер и местоположение, имеют тип столкновения CollisionType.passive. Благодаря этому, мы можем:

1. Проверить эти объекты на пересечения и сформировать bounding box вокруг большого числа пересекающихся объектов одного типа. Это вычисление не нужно делать на каждом update(), достаточно выполнить его когда добавляются/удаляются объекты или меняется их местоположение, что происходит крайне редко, вероятнее всего - лишь в момент загрузки игры. На широкой фазе расчета столкновений это позволит не проверять столкновения с каждым объектом индивидуально, а сперва проверить, сталкиваемся ли мы с "bounding box", и только если да - начать проверять весь список объектов. Именно таким образом в демо-приложении расчёт столкновений с 400 объектами в ячейке в основном сводится к проверке на столкновения всего с двумя GroupHitbox.

2. Пре-рендерить эти объекты в "слой", сохранить получившееся изображение как SpriteComponent или SpriteAnimationComponent и... вместо рендера 400 отдельных компонентов рендерить всего два, экономя на многократном расчёте необходимых трансформаций множества маленьких спрайтов. Но, правда, это существенно больше расходует память.

В целом, правила использования библиотеки в текущем её виде можно свести к нескольким шагам:

1. Игру расширяем примесью HasSpatialGridFramework

2. В onLoad игры вызываем await initializeSpatialGrid. Если у вас в игре карта генерируется процедурно - используйте параметр cellBuilder . Если есть нарисованные в Tiled карты - используйте параметр maps , и для каждой из карт нужно будет отнаследовать новый класс от TiledMapLoader. Об этом классе подробнее расскажу ниже.

3. Все компоненты игры обязательно расширяем примесью HasGridSupport, иначе ничего не будет работать. При этом "дочерние" компоненты могут быть и без этого расширения, но тогда в расчёте столкновений они не будут участвовать.

4. При создании новых компонентов желательно сразу указывать их текущую ячейку, иначе системе придётся самостоятельно её высчитывать, а это довольно долго. Но если вы в процессе игры создаёте новый компонент - как правило это происходит где-то рядом с каким-то существующим компонентом, или же прямо "на нём" - соответственно, и сделать вызов типа newComponent.currentCell = oldComponent.currentCell нет никаких проблем.

Вот и всё, это необходимый минимум!

Касательно TiledMapLoader. В этом классе мы указываем:

• Какую карту грузить

• В какой позиции игрового поля рендерить

• Какую функцию вызывать в зависимости от типа тайла - по сути, дублирование функционала, который был сделан в моём предыдущем решении на эту тему, flame_tiled_utils.

• Функция, которую вызывать, если тайл не относится ни к одному из типов, для которых задан специфический обработчик. Удобно, если у вас есть некий "бэкграунд" карты, с которым пользователь не взаимодействует. Можно сразу скомпилировать его в плоскую картинку или добавить в анимационный слой. Обратите внимание на addToLayer, эта функция не только компилирует компоненты в слой-картинку, но и оптимизируют столкновения, автоматически создавая bounding box.

  Future<void> onBackgroundBuilder(CellBuilderContext context) async {
    final component =
        await TileComponent.fromProvider(context.tileDataProvider);
    component.currentCell = context.cell;
    component.position = context.position;
    component.size = context.size;
    if (component.sprite != null) {
      addToLayer(
          component: component,
          layerName: 'static',
          animated: false,
          priority: -1);
    } else if (component.animation != null) {
      addToLayer(
          component: component,
          layerName: 'animated',
          animated: true,
          priority: -1);
    }
  }

• defaultBuilder - функция, которая будет вызвана для каждого тайла. Пока не знаю use-кейс для неё, но кажется, что может пригодиться.

• cellBuilder - функция, которую нужно переопределить, чтобы процедурно генерировать компоненты в каждой новой ячейке. Метод isCellOutsideOfMap поможет не нагенерировать лишних объектов, если ячейка и так расположена на территории карты.

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

  Future<void> onBuildBrick(CellBuilderContext context) async {
    final spriteBrick = getPreloadedTileData('tileset', 'Brick')?.sprite;
    final brick = Brick(
        position: context.position, sprite: spriteBrick, context: context);
    brick.currentCell = context.cell;
    addToLayer(
        component: brick, animated: false, layerName: 'Brick', priority: 2);
  }

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

В двух словах всё выглядит так. Подробности можно посмотреть в рабочем примере: https://github.com/ASGAlex/flame_spatial_grid/blob/main/examples/lib/game.dart

API нормально опишу уже на гитхабе, когда архитектура окончательно устаканится.

Проблемы и ограничения метода

При всех позитивных моментах, у данного подхода есть свои сложности:

1. Нагрузка на видеопамять. Статичные компоненты компилируются в слои (с анимацией или без), которые хранятся и рендерятся в виде готовой картинки, и слабые системы могут с этим не справиться. Мне уже жаловались на такую проблему в рамках другой библиотеки: https://github.com/ASGAlex/flame_tiled_utils/issues/2

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

3. Необходимость в целом заниматься менеджментом ресурсов: не только подчищать неиспользуемые картинки, но и в целом удалять «протухшие» компоненты, воссоздавать их заново, выгружать и загружать обратно карты…

4. Определиться с размерами игровых компонентов и, соответственно, размером игровой сетки. От этого параметра напрямую зависит эффективность использования ресурсов.

5. «Телепортация» игрового персонажа в произвольную точку карты теперь становится ресурсоёмкой процедурой, т.к. мало просто переместить компонент по новым координатам, нужно ещё и определить соответствующую этим координатам ячейку, создать новые ячейки при необходимости, наполнить их данными, выключить неиспользуемые ячейки и очистить ресурсы…. Всё это в Flutter идёт строго в одном потоке, так что крайне вероятны лаги.

6. Алгоритм позволяет работать только с большим числом статичных объектов, то есть когда подавляющее их большинство – это предметы игрового окружения. Если на поле бахнуть тыщ пять активных NPC – я даже не вижу смысла проверять, система гарантированно загнётся.

В целом, любая проблема решаема, вопрос в том, что в текущем своём состоянии flame_spatial_grid хорошего рабочего решения на все случаи не предлагает. Но, скорее всего, и решение этих проблем не добавит простоты в использование библиотеки, а наоборот, заставит разработчика дополнительно думать и принимать решения по новым и новым вопросам….

Итоги

В прошлый раз мы увеличили скорость определения столкновений в 32 раза. В этот раз мы сделали работу со столкновениями ещё примерно в 2 раза быстрее. А также в принципе позволили системе обрабатывать в 30 раз больше объектов, чем раньше (при падении производительности в 5 раз, но сохранении на приемлемом уровне). Прежде всего, в этот момент хочется отдельно передать привет людям, которые искренне верят, что все проблемы решаются тем, «быстрый» язык программирования ты используешь, или «медленный» ????

Пока что это решение ещё нужно обрабатывать напильником, ещё много где. И даже если не обрабатывать – впереди ещё написание документации. В любом случае, фундамент для написания какого-нибудь Fallout с бесконечной игровой картой у нас уже есть.

Если кому-то уже нужно/интересно попробовать такую штуку в своём проекте – выкачивайте из гита, смотрите рабочий пример в папке examples. Если вам интересно просто посмотреть – заходите на https://asgalex.github.io/flame_spatial_grid (да, оно и в браузере работает!), только с десктопа, мобилка не потянет.  WASD – перемещение, пробел – выстрел, M – включение / выключение отладочной сетки, LShift – переключение режима огня, чтобы разрушать или только кирпичи, или и кирпичи и воду. Зум колёсиком мыши, при тыке в любую часть экрана – телепорт персонажа в указанную точку.  

Если вы где-то использовали у себя библиотеку flame_tiled_utils, то есть смысл переключиться с неё на вот это новое решение - подходы используются те же, но более грамотно. Ну и , к тому же, развивать старую библиотеку уже не планирую, это был промежуточный вариант.

И, надеюсь, в 2023 году вам вообще не понадобятся никакие сторонние библиотеки, потому что получится законтрибьютить сделанные доработки непосредственно в Flame, как это произошло с QuadTree ????????