← Модуль 11/Pathfinding
EN
Модуль 11 · Классический контроль

Pathfinding: A* и NavMesh

Как «двигаться к игроку» превращается в поиск по графу — и почему навигация это сетка многоугольников, а не клетки.
🏠 лаба~15 мин
Суть за 20 секунд
A* ищет кратчайший путь по графу, разворачивая узлы в порядке f(n) = g(n) + h(n) — пройденная стоимость плюс эвристика оценки до цели. Если эвристика допустима (не переоценивает), A* находит оптимум, разворачивая минимум узлов. В играх ходят не по клеткам, а по NavMesh — сетке выпуклых многоугольников проходимого пространства; A* бежит по ней, а сглаживание (string-pulling) убирает зигзаги.

Механизм A*

Дейкстра разворачивает узлы по g(n) (расстоянию от старта) во все стороны. A* добавляет h(n) — оценку «сколько ещё до цели» — и тянет поиск к цели:

f(n) = g(n) + h(n) → разворачиваем узел с минимальным f

Ключевое свойство — допустимость: если h никогда не переоценивает истинную стоимость, путь оптимален. На сетке берут манхэттенское (4-связность) или евклидово/октиль (8-связность) расстояние. Чем h ближе к истине (не превышая), тем меньше узлов развернёт A* — на пределе h = истинная стоимость → идём прямо к цели.

зелёные — развёрнутые узлы; A* обходит стену и тянется к цели, не заливая всю карту

NavMesh — почему не клетки

Сетка клеток точна, но дорога: открытое поле — это тысячи узлов ни о чём. NavMesh покрывает проходимое пространство небольшим числом выпуклых многоугольников; внутри полигона можно идти по прямой. A* бежит по графу полигонов (их десятки, не тысячи), а string-pulling (алгоритм «воронки») вытягивает путь в естественную прямую вместо лесенки по центрам клеток. Поэтому в 3D-играх навигация — почти всегда NavMesh (Recast/Detour, встроенные навигаторы Unreal/Unity/Godot).

🕹 В какие игры поиграть — и что заметить

Один вопрос «как дойти до цели» — разные ответы под разные ограничения, от «вообще без поиска» до 3D-вокселей. По каждому: как сделано и во что сыграть, чтобы увидеть руками.

Pac-Man 1980 · простейший 2D, без A*

Призраки не строят путь вовсе. Каждый на перекрёстке жадно выбирает направление, минимизирующее прямую дистанцию до своей целевой клетки (Blinky целит в клетку Пакмана, Pinky — на 4 клетки впереди него, у Inky и Clyde свои правила). Один тайл лукахеда, без разворота, без памяти — O(1), потому что на железе 1980-го больше нельзя.

🎮 Сыграй: запусти Pac-Man (любой браузерный порт). Зажми призраков в угол и смотри, как на перекрёстках они расходятся в разные стороны — у каждого своя цель. Это «пасфайндинг» вообще без пути.

Тайловый A* 2D · сетка

Равномерная сетка, 4/8-связность — ровно то, что в лабе выше. Ранние RTS, рогалики, тактики: карта известна и статична → классика бьёт всё.

🎮 Сыграй: открой лабу A* и порисуй стены — это буквально оно. Или классику вроде первого Warcraft / Heroes of Might & Magic.

Minecraft 3D · воксели

A* по блокам в 3D. Соседи — «куда можно шагнуть»: ступенька вверх на 1 блок, спрыгнуть в пределах высоты, перепрыгнуть щель. Узлы оценивает NodeEvaluator со штрафами (malus): вода и лава — огромная цена/обход, огонь/забор/дверь — свои веса. Поиск ограничен бюджетом узлов (не весь мир) и троттлится по тикам — иначе 3D-A* на каждого моба убьёт сервер. Летающие/плавающие мобы — через объёмный вариант, а не «стоя на блоке».

🎮 Сыграй: в Minecraft заспавни зомби/свинью, окружи рвом с лавой или забором — смотри, как он обходит опасность и лезет по блокам-ступеням. Выкопай яму в 2–3 блока — застрянет (предел высоты прыжка / бюджет узлов). Вот 3D-пасфайндинг руками.

3D-шутеры и RPG NavMesh

В непрерывном 3D-мире воксельный A* слишком дорог. Пекут NavMesh (полигоны проходимой поверхности, Recast), A* по графу полигонов + «воронка» для гладкого пути. Почему у Minecraft иначе — его мир уже сетка блоков, там воксели естественны.

🎮 Посмотри: в Godot/Unity-демо навигации (или в игре с дев-консолью) включи debug-отрисовку navmesh — увидишь полигоны проходимости поверх уровня и путь-«воронку».

RTS на масштабе тысячи юнитов

A* на юнита не тянет сотни. Supreme Commander, StarCraft II — flow fields (одно поле от цели → направление в каждой клетке, все идут по нему) + локальное расталкивание (boids / ORCA). Один поиск на цель вместо поиска на юнита.

🎮 Сыграй: в StarCraft II / любой RTS выдели 50+ юнитов и гони через узкий мост — увидишь, как они текут одним потоком и толкаются, а не считают маршрут поодиночке.

Хардкор: почему A* оптимален — и при чём тут согласованностьможно пропустить

Допустимость: h(n) ≤ h*(n) — эвристика никогда не переоценивает истинную стоимость до цели. Утверждение: A* (tree-search) с допустимой h возвращает оптимальный путь.

Набросок доказательства

Пусть A* вот-вот вернёт цель G₂ с g(G₂) > C* (субоптимум, C* — оптимальная стоимость). В момент завершения на фронтире есть узел n на оптимальном пути, для которого

f(n) = g(n) + h(n) ≤ g(n) + h*(n) = C*

(первое — допустимость, второе — n лежит на оптимальном пути). Но A* выбрал G₂ с f(G₂) = g(G₂) > C* ≥ f(n) — значит, обязан был раскрыть n раньше G₂. Противоречие. ∎

Допустимость vs согласованность

Согласованность (монотонность): h(n) ≤ c(n,n′) + h(n′) для каждого ребра. Согласованность ⇒ допустимость, и ⇒ f не убывает вдоль пути ⇒ когда A* раскрывает узел, его g уже оптимально ⇒ graph-search с closed-множеством не нуждается в переоткрытии. Лишь допустимая, но не согласованная h может потребовать переоткрытия закрытых узлов, иначе оптимальность теряется. Поэтому целятся в согласованную h (манхэттен на 4-связности, octile/евклид на 8-связности — согласованы).

Почему точная эвристика провабельно дешевле

A* раскрывает все узлы с f(n) < C* и ни одного с f(n) > C*. Если h₂ ≥ h₁ всюду (обе согласованы), h₂ доминирует: {f₂ < C*} ⊆ {f₁ < C*} → раскрывает не больше узлов. На пределе h = h* раскрываются только узлы оптимального пути.

Weighted A* — обмен оптимальности на скорость

С f = g + w·h (w ≥ 1) поиск жаднее и быстрее, но субоптимален ограниченно: стоимость ≤ w·C*. Спектр одной ручкой: w=0 → Дейкстра (только g), w→∞ → greedy best-first (только h), w=1 → A*.

Хардкор · инженерия: pathfinding в проде на масштабеможно пропустить
  • Тайм-слайсинг: бюджетируешь N поисков на кадр и размазываешь очередь по кадрам — иначе спайк, когда 50 юнитов разом запросили путь.
  • Иерархия (HPA*): грубый граф регионов + локальный поиск внутри — на больших картах дешевле плоского A* на порядки.
  • Локальное избегание ≠ глобальный путь: A* строит маршрут, но «не врезаться в соседей» — отдельный слой (ORCA/boids/steering). Путает их каждый второй джун.
  • NavMesh печётся на билде (Recast); рантайм только запрашивает; динамические препятствия → частичный re-bake/локальный обход.
  • Кэш путей для типовых маршрутов; полный пересчёт каждый кадр — антипаттерн.
Аналогия
Дейкстра — наводнение: вода растекается одинаково во все стороны, пока не дойдёт до цели. A* — вода с уклоном к цели: эвристика наклоняет поверхность, и поток идёт прямее, заливая меньше территории. NavMesh — карта районов вместо карты каждого тротуара: внутри района идёшь напрямик, маршрут строишь по районам.
Почему это важно
Pathfinding — самый «незаметный» AI: игрок замечает его, только когда он ломается (NPC застрял в углу). Понимание допустимости эвристики и того, почему NavMesh дешевле сетки, отличает «работает» от «работает на 200 юнитах в RTS на 60 FPS».
🔁 За пределами игр — куда это переносится
A* — это информированный поиск (branch-and-bound с эвристикой), а flow field — «один расчёт на многих» (амортизация). Оба переносятся широко:

Оптимизация / поиск: A* всюду в планировании, маршрутизации, компиляторах (register allocation = поиск по графу); эвристика = нижняя оценка в branch-and-bound.

ML / AI: beam search в декодировании LLM — тот же информированный поиск по дереву; MCTS (AlphaGo) = поиск + выученная эвристика-value; «когда A* бьёт RL» = «когда классика бьёт ML». Flow field = батчинг: один solve от цели для всех агентов ≈ один forward-pass на батч вместо на пример — основа эффективного инференса.

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

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

🏠 Лаба — A* вживую
Интерактивная лаба без кода: рисуй стены, двигай старт/цель, переключай Dijkstra / A* / Greedy / Weighted — и смотри на счётчик развёрнутых узлов. То самое доминирование эвристики, но глазами. Открыть лабу →
Лучший момент: сравни число узлов у Dijkstra и A* при одном пути — A* кратно экономнее. Кто хочет в коде — A* vs Q-learning описан в labs/lab-11b-astar-vs-rl/.
🔧 Запусти и поковыряй — на домашнем компе
Во что поиграть — выше (🕹). Здесь — для тех, кто хочет залезть в движок:
🔧 Поковырять (debug) ~40 мин, Godot
Открой Godot, демо NavigationServer / Navigation2D. Поставь агента, цель, препятствия, включи отладочную отрисовку navmesh и путей. Подвигай препятствие в рантайме — увидишь пересчёт пути. Сломай: убери связность меша — агент встанет.
🧪 Потестить (глазами QA) ~15 мин
Ищи классические баги навигации: застревание в углах, «дрожание» на границе препятствия, срезание сквозь тонкие стены, толпа, запирающая себя в дверном проёме. Типовой QA-чеклист по AI-навигации.
Чеклист: увидел flow-field-поведение толпы; включил debug navmesh в Godot; нашёл хотя бы один баг навигации.
Связи
основа
FSM и Behavior Trees — действие «двигаться к цели» из дерева поведения дёргает A* под капотом.
контраст
Классика vs ML — A* vs RL на навигации: известная карта → A* выигрывает всухую.
Вопросы пытливого ума
На 8-связной сетке манхэттенская эвристика всё ещё допустима?
Нет. По диагонали реальная стоимость хода ≈1.41 (или 1 при chebyshev-движении), а манхэттен считает её за 2 — он переоценивает → недопустим → A* может вернуть не кратчайший путь. На 8-связности берут octile-расстояние (или евклидово) — они допустимы и согласованы. Классическая ловушка «работает, но иногда срезает неоптимально».
A*, Дейкстра и greedy best-first — это правда один алгоритм?
Да, точки на шкале f = g + w·h: w=0 → Дейкстра (только пройденная стоимость, оптимум, но «заливает» карту), w→∞ → greedy (только эвристика, быстрый, неоптимальный), w=1 → A*. Меняя вес, скользишь между «надёжно-медленно» и «быстро-приблизительно» (см. хардкор про weighted A*).
JPS (Jump Point Search) — почему на сетке можно «прыгать» через узлы?
На равномерной сетке масса путей симметричны (та же стоимость, иной порядок ходов). JPS убивает симметрию: вместо разворота каждого соседа «прыгает» вдоль направления до точки с вынужденным поворотом (forced neighbor). Результат идентичен A*, но узлов в open-листе на порядок меньше. Только для uniform-cost grid — на NavMesh неприменим.
Flow field для 500 юнитов — это всё ещё A*?
Нет, это инверсия задачи: решаешь один single-source шортест-пас от общей цели ко всем клеткам (Дейкстра/BFS, или эйкональное уравнение для гладких полей) → поле направлений, по которому идут все юниты за O(1) каждый. A* на юнит = O(юниты × поиск); flow field = O(поиск) + O(юниты). Поэтому RTS с тысячами юнитов ходят по полю, а не по A* на каждого.
Почему RL почти не используют для навигации в шипнутых играх?
A* даёт оптимум сразу, детерминирован, отлаживаем за O(E log V); RL надо обучать, он недетерминирован и ломается на новых картах. Платить обучением там, где есть точный полиномиальный алгоритм, незачем. RL осмыслен, лишь когда модели/карты нет — непрерывное управление с динамикой, частичная наблюдаемость.
Что почитать