Pathfinding — AI мобов

Находим путь в сетке: от старта до цели, обходя препятствия.

🎣 Hook

Зомби умеет добраться до игрока, даже если есть стены и коридоры. Значит, он ищет путь по карте.

🧠 Concept

Термины: list, dictionary, loop, function — пишем по-английски, объясняем по-русски.

Pathfinding часто моделируется как граф:
- клетки/точки = вершины;
- переходы между ними = рёбра.

Для «минимального числа шагов» на равных рёбрах подходит BFS (поиск в ширину).

🧩 Квиз +10 XP

Какой алгоритм обычно берут для кратчайшего пути в невзвешенном графе?

A Bubble sort

B BFS

C Linear search

D Recursion only

🔧 Практика

Задание 1: укажи стартовую и целевую метки.

start = "S"
goal = "G"

Заполни пропуски в коде в своей тетради/редакторе. Ключевые ответы: S/G.

Задание 2: допиши структуру для BFS-посещения.

queue = [start]
visited = set()

Проверь себя: queue.

🧩 Квиз +10 XP

Что хранит visited в BFS?

A Только стены

B Уже посещённые вершины

C Только цель

D Случайные индексы

🏗️ Сборка: мини-проект

Нарисуй сетку 7x7 с препятствиями и найди кратчайший путь от S до G (список координат).

👹 Мини-босс +120 XP

Комбинируем текущую тему с предыдущими навыками.

A Сделать без структуры, потом чинить

B Сначала план, затем реализация и проверка

C Копировать решение без понимания

D Пропустить тесты ради скорости

💭 Reflection

Ты видишь, как задачи навигации сводятся к структурам данных и алгоритмам графов.