Изначально всю навигацию в игре я строил на тайловой сетке. Наряду с общеизвестными ускорителями для A*: Weighted A*, HPA*, бинарная куча для open list — я использовал ещё одну идею для поиска по сетке (как оказалась, легко переносящуюся на NavMesh). Идея довольно проста, но почему-то упоминаний о ней я нигде не нашёл (поэтому я пока сохраню её в секрете, как коммерческую тайну), и она делает поиск очень быстрым (быстрее, чем Jump point search).

Это позволило реализовать следующую задумку: использовать тайлы очень маленького размера — гораздо меньше, чем площадь, занимаемая юнитом, и регистрировать каждого юнита как obstacle отдельно для агентов всех размеров. По сути я получил почти то, что многие хотят получить на NavMesh — использование каждого агента как dynamic obstacle. Благодаря чему, каждый юнит честно искал путь вокруг всех других юнитов.

И это, наверно, прекрасно работало бы в какой-нибудь RPG или RTT с не очень большим количеством агентов. Но в динамичной стилизованной RTS с большим количеством юнитов такая сложность и реализм не играют на руку, а скорее только вредят геймплею: при отдаче приказа игрок ожидает, что юниты исполнят его как можно быстрее, а не станут наматывать "честные" неочевидные зигзаги. Поэтому решил перейти к проверенным временем NavMesh с расталкиванием и локальным избеганием.

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

1. Не нужно выполнять всю логику каждый кадр
Большинству систем хватает 5-30 вызовов в секунду. В Final Divide почти всё, кроме движения, имеет tick (это особенно важно для RTS).

2. Пулинг объектов
Создание большого количества объектов и сборка мусора после их удаления в каждом кадре — очень дорогие операции. В Final Divide я использую централизированную коллекцию пулов для пуль, взрывов, эффектов и всего, что постоянно спавнится и деспавнится. Избавиться от лишних аллокаций можно в местах, где часто создаются массивы и иные структуры данных: лучше один раз закэшировать структуру и реюзать её.

3. Ленивые вычисления
Не нужно считать то, что может не понадобиться. Например, я часто вижу, как при pathfinding кто-то сразу сглаживает и оптимизирует весь путь до конечной точки. Но юнит может прервать движение на середине. Путь можно сглаживать по ходу движения.

4. Не использовать физику без необходимости
Простота использования физики в современных движках привела к тому, что её применяют там, где она совсем не нужна. Во многих RTS, как и в Final Divide, юниты вообще не используют физику. Чтобы "поставить" танк на землю, достаточно найти высоту террейна в 4 точках и снепнуть к ним объект. Добавляем сюда первый совет; а если юнит находится не в кадре, то тик можно ещё и увеличить. Получаем вместо постоянной физической симуляции очень легковесные вычисления.

5. Пространственная кластеризация
Действия большинства игр происходят в пространстве, которое можно разбить на сегменты. Так, обычный A* можно превратить в HPA*. Если юнит ищет ближайшую вражескую цель полным перебором — это экспоненциальная сложность; в Final Divide для каждого entity постоянно определяется, какие кластеры он занимает, а поиск целей происходит по кластерам в радиусе обзора. При перестроении NavMesh я обновляю только затронутые изменениями кластеры. Ну а если вы вдруг решили создать свой собственный физический движок, без этого не обойтись.