---
id: npc-pathfinding
lang: ru
title: Поиск пути и выполнение маршрута
description: >-
  Выбираем представление пространства и стоимость переходов, отделяя найденный
  путь от реального движения NPC.
category: engineering
level: intermediate
minutes: 6
updatedAt: '2026-10-20'
tags:
  - npc-ai
  - pathfinding
  - algorithms
sources:
  - title: 'Amit Patel, Red Blob Games: Introduction to the A* Algorithm'
    url: 'https://www.redblobgames.com/pathfinding/a-star/introduction.html'
url: 'https://gamemechanics.pro/ru/lessons/npc-pathfinding/'
markdownUrl: 'https://gamemechanics.pro/content/ru/npc-pathfinding.md'
license: CC-BY-4.0
codeLicense: MIT
attribution: gamemechanics.pro contributors
---

## Что нужно знать

Найти последовательность клеток и провести по ней персонажа без застреваний являются двумя разными задачами. Начните с модели пространства, затем проверьте обе части.

## Принцип

Поиск работает с графом: узлами и допустимыми переходами между ними. В [объяснении Red Blob Games](https://www.redblobgames.com/pathfinding/a-star/introduction.html) одна и та же идея применяется к разным представлениям пространства. Клеточная сетка удобна, но не обязательна.

При одинаковой стоимости переходов поиск в ширину (BFS) находит путь с наименьшим числом переходов. При неотрицательных разных стоимостях Dijkstra учитывает их сумму. A* добавляет оценку остатка пути. На четырёхсвязной сетке без диагоналей расстояние Манхэттена, умноженное на минимальную стоимость шага, подходит как нижняя оценка; нестандартные переходы вроде телепорта могут её нарушить.

<span id="пример-коридоры-ремонтного-робота"></span>

## Практический пример

### Коридоры ремонтного робота

В условном графе есть два маршрута от 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).