Lab · потрогать руками

A* вживую

Лаба без кода: рисуй стены, двигай старт и цель, переключай режим — и смотри, сколько узлов разворачивает алгоритм и какой путь выходит. Здесь видно глазами всё, что в уроке доказано формулами.

🏠 эксперимент~10 мин

Как пользоваться

Рисуй стены — тяни мышью/пальцем по сетке. Двигай зелёный старт и красную цель — тяни их. Жми Запустить и смотри на счётчик «развёрнуто узлов». Переключи Dijkstra → A* — узлов станет в разы меньше при том же оптимальном пути. Greedy — быстро, но путь кривой. Weighted A* — крути вес и смотри размен «меньше узлов ↔ длиннее путь».

старт цель стена фронтир (open) развёрнуто (closed) путь

режим диагонали

Что заметить: поставь стену-«стену с дыркой» между стартом и целью. 1) Dijkstra заливает почти всё поле; A* тянется к цели и разворачивает кратно меньше узлов — тот же оптимальный путь (это и есть доминирование информированной эвристики). 2) Greedy — мало узлов, но путь не кратчайший. 3) Weighted A*: w↑ → узлов меньше, путь длиннее, но не более чем в w раз (ограниченная субоптимальность).

🏠 Что дальше

Вернись в урок, раздел «🎮 Поиграй / поковыряй» — где запустить настоящую навигацию: Godot-демо NavMesh, RTS с тысячами юнитов (flow fields), и поломать pathfinding застреванием в углу.

Связи

из урока

Pathfinding A*/NavMesh — теория: f=g+h, допустимость, weighted A*, доминирование эвристики.

пересечение

Классика vs ML — известная карта → A* бьёт RL всухую: ровно то, что ты видишь на счётчике узлов.

Что заметить по итогу (чеклист наблюдений)

Сравнил счётчик узлов: A* ≪ Dijkstra при том же пути.
Увидел, что Greedy быстрый, но путь не оптимален.
Покрутил w в Weighted A*: узлов меньше, путь длиннее.
Нарисовал «ловушку» (П-образную стену) и увидел, как алгоритм её обходит.