Сделал свой navigation mesh для моей RTS

Те, кто в теме, знают, что pathfinding в RTS — главная головная боль для разработчиков, а иногда и для игроков.

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

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

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

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

Следить за разработкой: