Кратчайший путь
Рисуйте стены и смотрите, как алгоритмы находят путь.
Алгоритм
СтартФинишСтенаИсследованоКратчайший путь
Начните, когда будете готовы · исследовано 0 клетокКак это работает +
Выберите инструмент и нажимайте или ведите указатель для размещения стен, старта и финиша. Правки карты и смена алгоритма сбрасывают поиск, сохраняя карту.
Можно идти вверх, вниз, влево и вправо, стоимость шага — 1. BFS ищет по слоям. Дейкстра использует накопленную стоимость и здесь ведёт себя сходно. A* добавляет манхэттенское расстояние, выбирая перспективные направления.
Все три находят путь с наименьшим числом шагов, если он существует, но исследованные клетки и маршруты могут отличаться. Случайные стены могут перекрыть все пути. Жёлтым показан итоговый маршрут. Скорость анимации не измеряет быстродействие. Карта обрабатывается в браузере.