Что нужно знать
Найти последовательность клеток и провести по ней персонажа без застреваний являются двумя разными задачами. Начните с модели пространства, затем проверьте обе части.
Принцип
Поиск работает с графом: узлами и допустимыми переходами между ними. В объяснении Red Blob Games одна и та же идея применяется к разным представлениям пространства. Клеточная сетка удобна, но не обязательна.
При одинаковой стоимости переходов поиск в ширину (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 и удобен как исходная проверка.
Теперь разместите коридоры в игре. Учитывайте ширину робота при построении проходимости. Если дверь закрылась, старый путь может потерять смысл. Сигнал изменения навигации или обнаружение блокировки должны приводить к пересчёту либо понятному отказу по правилам проекта.
Частые ошибки
- Использовать прямое расстояние как гарантированную оценку при дешёвых телепортах.
- Считать пустой путь успехом, когда цель недостижима. Старт, совпавший с целью, является отдельным случаем.
- Пересчитывать путь каждый кадр без необходимости и без измерения стоимости.
- Забывать, что сглаженный отрезок может срезать непроходимый угол.
Проверка результата
- Проверьте обе суммы вручную и сравните результат алгоритма.
- Удалите D–G: должен остаться маршрут A–B–G стоимостью 5. Затем удалите B–G и проверьте явный результат «пути нет».
- Проверьте совпадение старта и цели и закрытие двери во время движения.
- Пройдите найденный маршрут реальным коллайдером, включая узкие повороты.
Задание для ИИ-агента
Отдели поиск пути от движения робота. Верни маршрут, суммарную стоимость и статус. На указанном графе сравни BFS и Dijkstra, затем добавь обработку блокировки. Не объявляй готовую навигацию по одной нарисованной линии.
Оцените функциональное пространство через призму «Функциональное пространство».