--- key: lesson/npc-pathfinding type: lesson id: npc-pathfinding lang: ru title: Поиск пути и выполнение маршрута summary: >- Выбираем представление пространства и стоимость переходов, отделяя найденный путь от реального движения NPC. updatedAt: '2026-10-20' status: active url: 'https://gamemechanics.pro/ru/lessons/npc-pathfinding/' jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/ru/lesson/npc-pathfinding.json' markdownUrl: 'https://gamemechanics.pro/content/knowledge/ru/lesson/npc-pathfinding.md' aliases: - навигация - navigation - Дейкстра - Dijkstra - BFS - A* tags: - npc-ai - pathfinding - algorithms sourceIds: - source-f4e30147f2944e5d sources: - id: source-f4e30147f2944e5d title: 'Amit Patel, Red Blob Games: Introduction to the A* Algorithm' url: 'https://www.redblobgames.com/pathfinding/a-star/introduction.html' verifiedAt: null relations: - type: requires direction: outgoing label: Перед началом key: lesson/collision-basics title: Основы столкновений url: 'https://gamemechanics.pro/ru/lessons/collision-basics/' jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/ru/lesson/collision-basics.json' markdownUrl: 'https://gamemechanics.pro/content/knowledge/ru/lesson/collision-basics.md' - type: explains direction: outgoing label: Применение принципа key: mechanic/point-and-click--family-24 title: 'Карты, маршруты и лабиринты' url: >- https://gamemechanics.pro/ru/knowledge/mechanic/point-and-click--family-24/ jsonUrl: >- https://gamemechanics.pro/api/v1/knowledge/ru/mechanic/point-and-click--family-24.json markdownUrl: >- https://gamemechanics.pro/content/knowledge/ru/mechanic/point-and-click--family-24.md - type: practices direction: outgoing label: Применить на практике key: practice/maintenance-patrol title: Ремонтный патруль url: 'https://gamemechanics.pro/ru/knowledge/practice/maintenance-patrol/' jsonUrl: >- https://gamemechanics.pro/api/v1/knowledge/ru/practice/maintenance-patrol.json markdownUrl: >- https://gamemechanics.pro/content/knowledge/ru/practice/maintenance-patrol.md - type: reviews direction: outgoing label: Проверить через призму key: lens/schell-026 title: Функциональное пространство url: 'https://gamemechanics.pro/ru/knowledge/lens/schell-026/' jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/ru/lens/schell-026.json' markdownUrl: 'https://gamemechanics.pro/content/knowledge/ru/lens/schell-026.md' - type: contains direction: incoming label: Учебные маршруты key: path/npc-behavior title: Поведение NPC url: 'https://gamemechanics.pro/ru/learn/npc-behavior/' jsonUrl: 'https://gamemechanics.pro/api/v1/knowledge/ru/path/npc-behavior.json' markdownUrl: 'https://gamemechanics.pro/content/knowledge/ru/path/npc-behavior.md' placements: [] supersededBy: [] attributes: category: engineering level: intermediate minutes: 6 endsAt: null provenance: >- Авторский материал gamemechanics.pro. Учебные примеры требуют проверки в своём проекте. license: CC-BY-4.0 codeLicense: MIT attribution: gamemechanics.pro contributors --- # Поиск пути и выполнение маршрута id: npc-pathfinding type: lesson key: lesson/npc-pathfinding lang: ru status: active url: https://gamemechanics.pro/ru/lessons/npc-pathfinding/ Выбираем представление пространства и стоимость переходов, отделяя найденный путь от реального движения NPC. ## Что нужно знать Найти последовательность клеток и провести по ней персонажа без застреваний являются двумя разными задачами. Начните с модели пространства, затем проверьте обе части. ## Принцип Поиск работает с графом: узлами и допустимыми переходами между ними. В [объяснении Red Blob Games](https://www.redblobgames.com/pathfinding/a-star/introduction.html) одна и та же идея применяется к разным представлениям пространства. Клеточная сетка удобна, но не обязательна. При одинаковой стоимости переходов поиск в ширину (BFS) находит путь с наименьшим числом переходов. При неотрицательных разных стоимостях Dijkstra учитывает их сумму. A* добавляет оценку остатка пути. На четырёхсвязной сетке без диагоналей расстояние Манхэттена, умноженное на минимальную стоимость шага, подходит как нижняя оценка; нестандартные переходы вроде телепорта могут её нарушить. ## Практический пример ### Коридоры ремонтного робота В условном графе есть два маршрута от A к G. В обе стороны доступны только перечисленные рёбра: | Ребро | Стоимость | | ----- | --------: | | A–B | 1 | | B–G | 4 | | A–C | 2 | | C–D | 1 | | D–G | 1 | Маршрут A–B–G содержит два перехода и стоит 5. Маршрут A–C–D–G содержит три и стоит 4. BFS решит задачу числа переходов, но не минимальной стоимости. Dijkstra должен выбрать второй маршрут. A* с нулевой эвристикой сводится к Dijkstra и удобен как исходная проверка. Теперь разместите коридоры в игре. Учитывайте ширину робота при построении проходимости. Если дверь закрылась, старый путь может потерять смысл. Сигнал изменения навигации или обнаружение блокировки должны приводить к пересчёту либо понятному отказу по правилам проекта. ## Частые ошибки - Использовать прямое расстояние как гарантированную оценку при дешёвых телепортах. - Считать пустой путь успехом, когда цель недостижима. Старт, совпавший с целью, является отдельным случаем. - Пересчитывать путь каждый кадр без необходимости и без измерения стоимости. - Забывать, что сглаженный отрезок может срезать непроходимый угол. ## Проверка результата 1. Проверьте обе суммы вручную и сравните результат алгоритма. 2. Удалите D–G: должен остаться маршрут A–B–G стоимостью 5. Затем удалите B–G и проверьте явный результат «пути нет». 3. Проверьте совпадение старта и цели и закрытие двери во время движения. 4. Пройдите найденный маршрут реальным коллайдером, включая узкие повороты. ## Задание для ИИ-агента > Отдели поиск пути от движения робота. Верни маршрут, суммарную стоимость и статус. На указанном графе сравни BFS и Dijkstra, затем добавь обработку блокировки. Не объявляй готовую навигацию по одной нарисованной линии. Оцените функциональное пространство через призму [«Функциональное пространство»](/ru/lenses/#schell-026). ## Связанные материалы - Перед началом: [Основы столкновений](https://gamemechanics.pro/ru/lessons/collision-basics/) (key: lesson/collision-basics) - Применение принципа: [Карты, маршруты и лабиринты](https://gamemechanics.pro/ru/knowledge/mechanic/point-and-click--family-24/) (key: mechanic/point-and-click--family-24) - Применить на практике: [Ремонтный патруль](https://gamemechanics.pro/ru/knowledge/practice/maintenance-patrol/) (key: practice/maintenance-patrol) - Проверить через призму: [Функциональное пространство](https://gamemechanics.pro/ru/knowledge/lens/schell-026/) (key: lens/schell-026) - Учебные маршруты: [Поведение NPC](https://gamemechanics.pro/ru/learn/npc-behavior/) (key: path/npc-behavior) ## Источники и происхождение Авторский материал gamemechanics.pro. Учебные примеры требуют проверки в своём проекте. - [Amit Patel, Red Blob Games: Introduction to the A* Algorithm](https://www.redblobgames.com/pathfinding/a-star/introduction.html) (id: source-f4e30147f2944e5d) CC-BY-4.0 · gamemechanics.pro contributors