Поиск пути в видеоиграх: как AI находит маршруты
апр, 23 2026
Представьте: вы отдаете приказ отряду солдат в стратегии или наблюдаете, как монстр в хорроре методично обходит мебель, чтобы загнать вас в угол. Кажется, что персонаж «видит» комнату и понимает, где стоят стены, но на самом деле внутри движка происходит жесткий математический расчет. Компьютер не понимает, что такое «дверь» или «стена» в визуальном смысле - для него мир состоит из чисел, весов и узлов графа.
Чтобы персонаж не уперся лбом в текстуру и не начал ходить кругами, разработчики используют специальный процесс, который называется Поиск пути или Pathfinding. Это способ определить оптимальный маршрут из точки А в точку Б с учетом всех препятствий и стоимости перемещения. Без этого геймплея просто не существовало бы: ни в RPG, ни в шутерах, ни в спортивных симуляторах.
| Алгоритм | Принцип работы | Гарантия кратчайшего пути | Скорость/Ресурсы |
|---|---|---|---|
| BFS (Поиск в ширину) | Равномерное расширение во все стороны | Да (по количеству шагов) | Медленно на больших картах |
| Дейкстра | Учитывает стоимость поверхности | Да (абсолютная оптимальность) | Ресурсозатратный |
| A* (A-star) | Использует эвристику (направление к цели) | Да (при правильной эвристике) | Высокая эффективность |
| Волновой поиск | Заполнение массива чисел «волнами» | Да | Быстро для маленьких сеток |
Как игра «видит» пространство
Первый шаг любого алгоритма - превратить красивую картинку в понятную для машины модель. Вы не можете просто сказать AI: «иди туда». Сначала создается Навигационная сетка (NavMesh) или граф. Это упрощенная карта, где мир разбит на проходимые зоны (узлы) и связи между ними. В стратегиях реального времени (RTS) чаще всего используют тайлы - маленькие квадраты или шестиугольники. Если клетка помечена как «стена», AI ее игнорирует. Если как «болото», то присваивает ей высокую стоимость перемещения. Таким образом, поиск пути превращается в задачу поиска самого дешевого маршрута в графе.Простой старт: Поиск в ширину и Волновой поиск
Если вам нужно найти кратчайший путь в лабиринте, где все шаги стоят одинаково, подойдет Поиск в ширину (BFS). Работает он как монстр со щупальцами: из стартовой точки он одновременно тянет «отростки» во все доступные стороны. Сначала он проверяет все клетки, до которых можно дойти за один шаг, потом за два, и так далее. Как только одно из щупальцев коснулось цели, путь найден. Похожим образом работает Волновой поиск. Представьте, что вы бросили камень в воду: от центра расходятся круги. В программировании это выглядит как заполнение массива чисел: в стартовой клетке стоит 0, в соседних - 1, в следующих - 2. Когда «волна» достигает цели, алгоритм просто идет назад по убывающим числам, пока не вернется к началу.Когда важна цена: Алгоритм Дейкстры
BFS хорош, если все дороги равны. Но в жизни и играх это не так. Представьте, что персонажу нужно добраться до замка. Перед ним два пути: короткий, но через глубокий снег (где он двигается медленно), и длинный, но по укатанной дороге. BFS выберет снег, потому что там меньше клеток. Алгоритм Дейкстры же посчитает «вес» каждой клетки. Он поймет, что потратить больше времени на обход по дороге выгоднее, чем мучиться в снегу. Это база для всех сложных систем навигации, где ландшафт влияет на скорость.
Король навигации: Алгоритм A* (A-star)
Самый популярный инструмент в индустрии - это Алгоритм A*. Почему он лучше Дейкстры? Потому что он «умнее». Дейкстра ищет во все стороны, как слепой, пока не наткнется на цель. A* же использует эвристику - он примерно знает, где находится цель, и в первую очередь проверяет те узлы, которые ведут в сторону финиша. Математически это выглядит так: стоимость пути равна сумме расстояния от старта (g) и предполагаемого расстояния до цели (h). Если AI видит, что какой-то поворот уводит его в противоположную сторону от игрока, он просто перестанет тратить ресурсы на изучение этой ветки. Именно эта оптимизация позволяет сотням юнитов в больших мирах двигаться одновременно, не «вешая» процессор.Сложные случаи: платформеры и открытые миры
Не всё так просто, когда в игру добавляются прыжки или огромные расстояния. В платформерах обычный граф не работает, ведь персонаж может прыгнуть через пропасть или запрыгнуть на платформу. Здесь используются специализированные техники, которые анализируют траектории прыжков и создают связи между узлами, которые визуально не соединены, но достижимы физически. Для огромных карт (вроде тех, что в RPG с открытым миром) используют иерархический поиск. Карту делят на большие сектора. Сначала AI находит путь между секторами (например: «из леса в деревню, затем в замок»), а уже внутри каждого сектора прорабатывает детальный маршрут. Это в десятки раз снижает нагрузку на память.
Проблемы и «тупняки» AI
Вы наверняка видели, как NPC в старых играх застревали в углах или бегали кругами. Это происходит по нескольким причинам:- Динамические препятствия: если игрок поставил стену из ящиков, старый маршрут становится невалидным, и AI должен пересчитать его на лету.
- Столкновения: когда десять орков пытаются пройти в одну узкую дверь, они начинают толкать друг друга, создавая «пробку».
- Ошибки навигационной сетки: если в NavMesh есть маленькая дырка или «островок», персонаж может решить, что цель недостижима, и просто остановится.
Почему персонажи в играх иногда ходят по прямой сквозь препятствия?
Это происходит, когда в игре отключен или неправильно настроен поиск пути. Персонаж просто двигается по вектору в сторону цели, не проверяя проходимость узлов графа. Либо же навигационная сетка (NavMesh) была создана с ошибками, и AI «думает», что стена - это проходимая зона.
В чем главная разница между Дейкстрой и A*?
Дейкстра исследует все возможные направления вокруг себя, пока не найдет цель, что гарантирует идеальный путь, но тратит много ресурсов. A* добавляет к этому расчету направление к цели (эвристику), что позволяет игнорировать заведомо ненужные направления и находить путь гораздо быстрее.
Можно ли использовать поиск в глубину (DFS) для навигации?
Теоретически можно, но на практике - нет. Поиск в глубину идет в одном направлении до самого конца, прежде чем вернуться назад. Это значит, что он может найти какой-нибудь безумно длинный и запутанный путь к цели, даже если та стоит в соседней клетке.
Что такое NavMesh?
NavMesh (Navigation Mesh) - это упрощенная геометрия уровня, состоящая из выпуклых многоугольников. Она определяет все области, где персонаж может физически находиться и передвигаться. Алгоритмы поиска пути работают именно по этой сетке, а не по сложным 3D-моделям стен и пола.
Как поиск пути работает в огромных открытых мирах?
Используется иерархический подход. Мир делится на крупные регионы. AI сначала строит «грубый» маршрут из региона в регион, а затем детализирует его в конкретном месте, где находится персонаж. Это позволяет не хранить в оперативной памяти весь граф огромного мира.