Поиск пути
Вычисление того, как персонажу добраться из точки А в точку Б, не упираясь в стены, — за долю кадра.
Задача состоит из двух половин. Сначала мир нужно описать как граф: сетка из свободных и заблокированных клеток, сеть вручную расставленных путевых точек или навмеш из проходимых многоугольников. Затем граф исследуется, почти всегда алгоритмом A* — его в 1968 году опубликовали Питер Харт, Нильс Нильссон и Бертрам Рафаэль для робота Shakey, — то есть Дейкстрой с эвристикой, которая тянет поиск к цели.
Остальное — оптимизация и косметика. Иерархический поиск пути делит большие карты на кластеры, векторные поля потока позволяют тысяче юнитов делить один поиск, а сглаживание пути не даёт результату идти зигзагами. Путь, который математически кратчайший, но выглядит по-роботски, всё равно считается багом.