Как я уже писал ранее, на FPS в Flame в основном влияют операции, производимые на CPU. Если в вашей игре достаточно много взаимодействующих объектов, то одной из самых дорогих операций будет определение столкновений. Настолько дорогой, что на экране performance-метрики она закроет собой любые другие неоптимизированные участки.

Сами авторы Flame отлично осознают, что их алгоритм – не идеальный, а просто «дающий достаточную производительность». Достаточна она, видимо, для случаев, когда у вас всего объектов 10, не более. Если же у вас что-то более сложное – тогда приятного чтения!

Проблемы алгоритма Flame

Алгоритм определения столкновений состоит из двух фаз:

1. Предварительная, или "Broadphase": алгоритм определения столкновений низкой точности, но работающий на большом количестве объектов. Вычищает из выборки объекты, которые точно НЕ пересекаются.

2. Непосредственное определение столкновений: детальное и дорогостоящее определение для пар оставшихся объектов, сталкиваются они или нет. Именно во время этой фазы вызываются пользовательские callback-функции onCollision.

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

Но можно ещё быстрее ????

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

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

Кажется, проблема решается просто: в onCollision добавляем проверку по типу объекта, игнорируем столкновения, если объекты оказываются определённого типа. Беда в том, что этим мы не облегчаем процесс, а только утяжеляем алгоритм дополнительными проверками, ведь onCollision вызывается уже после того, как проходит Broadphase и после того, как ресурсы на дорогостоящую проверку столкновений уже потрачены.

В идеале, такие проверки должны быть вынесены в Broadphase. Также в идеале их результат должен кэшироваться, чтобы не нагружать этот алгоритм, поскольку изменение типа объекта во время игры маловероятно (в крайнем случае, если уж надо превратить воду в стену, для этого правильнее было бы удалить объект с типа «вода» и добавить на его место объект с типом «стена»).

Реализация такой механики возможна, но для этого нужно переопределить StandardCollisionDetection.

Вторая проблема: алгоритм Broadphase в Flame оставляет слишком много пар объектов для детальной проверки. В итоге на карте с большим количеством «препятствий» на детальную проверку столкновений может выпасть по несколько десятков пар объектов, что значительно нагружает систему.  Кроме того алгоритм «Sweep and prune» (https://ru.wikipedia.org/wiki/Sweep_and_prune) , который использует Flame, на каждом запуске производит перебор всех объектов на карте, что само по себе дорого, когда их много. Хорошо бы как-то ограничить выборку этих объектов.

В принципе, сами авторы осознают проблему, и прямо в документации оставили «подсказку»:

Алгоритм Quad Tree

Основная идея Quad Tree алгоритма заключается в том, что мы делим карту на сектора. Далее для каждого объекта определяем сектор, в котором он находится, и проводим проверку на столкновения только с объектами внутри этого сектора. Это позволяет не работать со всем множеством игровых объектов, а только с теми, которые находятся в непосредственной близости от активных объектов.

Вторая изюминка алгоритма в том, что карта делится не статически. При достижении некоего критического числа объектов в одном «квадранте», которое уже слишком дорого обрабатывать вместе, этот квадрант делится на 4 квадранта меньшего размера, и объекты распределяются между этими дочерними квадрантами. Таким образом, ваша карта будет проанализирована алгоритмом и автоматически поделена на много мелких зон, где высока концентрация объектов, и на более крупные зоны, где этих объектов не так много.

Для наглядности, на этом рисунке можно посмотреть «дебаг» того, как система разбила на квадранты игровую карту:

В сети есть много реализаций данного алгоритма. Есть и версия на Flutter с впечатляющей демкой: quadtree_dart.

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

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

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

3. Как следствие первого пункта, авторы большинства алгоритмов, чтобы определить, к какому квадранту относится объект, начинают заново вычислять квадрант по координатам. Для примера, автор одного из алгоритмов писал, что «не видит в этом проблемы и какого-либо влияния на производительность». Скорее всего, на C++ действительно код гораздо производительнее, чем на dart. А возможно, у него в тесте просто не было большого числа статических объектов.

Из меня такой себе математик-алгоритмист. Так что подходящее решение я злостно списывал, и рабочий результат уже оптимизировал под реалии языка и задачи. Первый раз списал не очень удачную имплементацию на Java, удостоверился, что работает быстрее, чем Sweep and prune, но всё равно удалил.

Второй раз портировал с C++ реализацию, описанную здесь: https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374 и уже с устранением вышеуказанных недостатков.

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

Свои наработки я обернул в библиотеку flame_quad_tree.

Это решение работает быстрее других алгоритмов, потому что:

1. Не перестраивает квадранты каждый раз. Карта первоначально делится на квадранты, после чего в неё только добавляются новые.

2. Связь между объектом и его квадрантом хранится в переменной Map<ShapeHitbox, Node>. Это затрудняет понимание кода, забивает память, замедляет запись о движении объектов, но зато для любого объекта мы можем максимально быстро получить его квадрант.

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

В использовании библиотека практически идентична тому, как это делается в «ванильном» Flame:

1. Добавляем примесь HasQuadTreeCollisionDetection к классу нашей игры

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

3. Все компоненты игры, которым нужно участвовать в просчёте столкновений, должны иметь примеси CollisionCallbacks, как в ванильном Flame, и CollisionQuadTreeController.

Примеры кода можно посмотреть в README.

Проблемы реализации.

Мне кажется, что-то можно было бы ещё улучшить, но, возможно, на самом деле нельзя. Поделюсь здесь, может что подскажете.

1. Рекурсивный сбор объектов. Проблема в том, что некоторые объекты могут быть разрезаны «квадрантами» на пополам. Для примера, на скриншоте выделены такие объекты:
   

   

   Таким образом, они не могут быть четко определены в какой-то определённый квадрант, и остаются висеть в родительском. А это вынуждает при получении списка потенциально сталкивающихся объектов перебирать элементы как вверх по дереву, так и вниз: https://github.com/ASGAlex/flame_quad_tree/blob/main/lib/src/quad_tree.dart#L272
   После того, как игра максимально заоптимизированна, оказывается, что самая тяжелая процедура, которая осталась – это вот этот перебор списков и наполнение списка данными.
   На практике, при работе со статичной тайловой картой, можно следить за её размером так, чтобы при делении на квадранты граница проходила четко по границе между тайлами. Ну, это нужно вручную считать размер карты и проверять, что она правильно «делится пополам». После чего дорисовывать недостающие тайлы, чтобы всё делилось правильно. Лишняя ручная работа, к тому же надо придумывать, какой игровой контент запихать в тайлы, которые тебе не нужны…
   В теории надо все-таки научить алгоритм учитывать размер тайла на карте, и делить кару пополам, учитывая эти данные. Это по крайней мере уменьшит нагрузку при работе со статичными тайлами. Но из-за наличия динамических объектов всё равно придётся проверять дерево в обе стороны. А так не хочется!

2. Работа с динамическими списками занимает много времени на выделение памяти. Опять же, это становится видно только когда вы максимально всё заоптимизировали. В теории, можно было бы сделать так, чтобы списки были ограниченной длинны «с запасом», и место в памяти выделялось бы единожды, заранее. Но тогда возня с «пустыми ячейками» после удаления объекта становится главным багообразующим фактором. Я не уверен, даст ли это в итоге прямо ощутимый прирост производительности, если таки заморочиться и сделать, но в теории должно работать быстрее.

"Бонусные" методы оптимизации

Перед тем как перейти к бенчмаркам, необходимо сказать, что эффект от смены алгоритма будет замечен только если:

1. У вас реально огромная карта

2. И на этой карте очень много объектов

Но беда в том, что Flame не умеет быстро рендерить огромные карты, о чем я писал в предыдущей статье. Решение, описанное там (только касательно рендера карты и класса TiledComponent), я завернул в библиотеку tiled_utils, его обязательно нужно использовать, чтобы изменение алгоритма рендеринга карты стало вообще заметным.

Проблемы будут у Flame и с большим количеством компонентов на огромной карте. Рендер компонента – ещё более дорогостоящая процедура, чем рендер тайла карты, а если объектов тысячи… В моей прошлой статье описан подход к решению и этой проблемы, его также нужно применить, иначе с любым алгоритмом определения столкновений вы получите только 1 FPS.

Чтобы не отвлекать внимание от главного - работы с столкновениями - я не стал тащить в демо-приложение свои запутанные классы, а применил штатное решение от Flame, хоть и не настолько гибкое. В принципе тоже можете взять себе на вооружение, вполне рабочий метод: https://github.com/ASGAlex/flame_quad_tree/blob/main/example/lib/static_layer.dart  

Бенчмарк

Пример кода в репозитории позволяет не только посмотреть, как пользоваться библиотекой, но и провести сравнение скорости работы с Sweep-and-Prune от Flame.

По умолчанию, конечно, в примере выкручены все оптимизации на максимум. Но есть возможность вместо TestGameQuadTree использовать TestGameStandard в main.dart. Запустив приложение в таком режиме, мы увидим довольно печальную картину по производительности несмотря на то, что уже оптимизировали и рендер карты, и рендер слоя компонентов:

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

Теперь давайте вернем обратно TestGameQuadTree, но у класса Brick уберем примесь UpdateOnce. Что получим при запуске:

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

На графике видно, что теперь, когда просчёт столкновений нам ничего не стоит, время тратится на вызов updateTree компонентов игры. Как я и писал в предыдущей своей статье, избыточных компонентов надо избегать, а Brick – как раз избыточный компонент, поскольку он не содержит никакой игровой логики и даже рендерится только один раз за всю игру – в PreRenderedLayer. Чтобы избавить систему от лишних вычислений, вернём примесь UpdateOnce на место. После третьего запуска приложения получим:

Победа? Однозначно.

Вот более «точечный» бенчмарк. Как видим, Quad Tree работает не только быстрее, но и эффективнее.

Должен заметить, что перенос проверки на типы пересекающихся объектов на этап broadphase не менее важен, чем сам алгоритм. В примере кода, по которому мы меряем производительность, не смоделирована такая ситуация, но, если бы у нас было множество активных объектов разных типов, и не все типы должны были бы взаимодействовать между собой – алгоритм Flame зашился бы ещё больше, а flame_quad_tree – нет, поскольку позволяет выполнить эту проверку на максимально ранней стадии, до тяжелых вычислений.

Итоги

Итак, сегодня мы ускорили расчёт столкновений в Flame примерно в 80000 / 2500 = 32 раза, сделав играбельной карту в 160 000 тайлов и 22 000 объектов на ней. Можно ли ещё что-то сделать с Flame, чтобы выжать из него ещё чуточку больше?

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

Как попробую – расскажу, что получится ????