Симулятор робота для лабиринта: заливка по расстоянию

Управление

Выберите режим — Исследовать, затем пройти на скорости или Только быстрый проход — и нажмите «Пуск», чтобы посмотреть, как робот решает задачу, или «Шаг», чтобы выполнять по одному ходу. Новый лабиринт создаёт новый случайный лабиринт; Сброс повторяет тот же. Три скорости, сочетания клавиш и полноэкранный режим позволяют управлять запуском. Жирными линиями обозначены стены лабиринта, затенённые коридоры — все места, где побывал робот, включая тупики, а жирная линия — кратчайший путь, найденный заливкой по расстоянию.

Теория

Лабиринт на сетке состоит из клеток, соединённых открытыми рёбрами, а между остальными находятся стены. Чтобы найти кратчайший маршрут, робот сначала должен узнать лабиринт, поэтому в этой лаборатории выполняются две фазы.

Исследование. Робот обходит лабиринт в глубину по правилу левой руки: на каждом перекрёстке поворачивает налево, если может, иначе едет прямо, а затем направо. При попадании в тупик он возвращается к последнему перекрёстку и выбирает следующую ветвь. Повторение до посещения каждой клетки составляет карту всего лабиринта, включая все неверные пути, которые пришлось исключить.

Оптимизация. Когда карта готова, заливка по расстоянию назначает цели расстояние ноль и распространяет увеличивающиеся значения через каждое открытое ребро. Теперь в каждой клетке хранится расстояние до цели, поэтому кратчайший путь просто таков: из старта всегда переходить в соседнюю клетку с меньшим числом. Робот проходит этот путь на скорости — он намного короче бесцельного исследования.

Алгоритм

1. Исследуйте лабиринт в глубину по правилу левой руки, выходя из каждого тупика с возвратом, пока не будут посещены все клетки.
2. Запишите каждое открытое ребро с обеих сторон, чтобы готовая карта знала о каждой стене.
3. Выполните заливку по расстоянию от цели: обозначьте её 0 и распространяйте увеличивающиеся расстояния через каждое открытое ребро.
4. Считайте кратчайший путь с поля: из старта каждый раз переходите в соседнюю клетку, расстояние до которой на единицу меньше.
5. Пройдите этот путь к цели на скорости.
6. Сравните длину исследования с длиной кратчайшего пути, чтобы увидеть, насколько карта сократила блуждание.

Исходный код

Разделите исследование, построение карты, планирование и движение на отдельные функции:

// Phase 1 — map the whole maze, backtracking out of dead ends
exploreDepthFirst(map, robot);        // left-hand rule until every cell is visited

// Phase 2 — flood-fill the finished map and run the shortest path
map.floodFill(goal);                  // goal = 0, distances ripple outward
for (Cell c = start; c != goal; c = map.lowerNeighbor(c))
  robot.driveTo(c);                   // always step one distance lower

Такая граница позволяет проверить один и тот же планировщик в этой браузерной лаборатории, на настольном компьютере и на итоговом контроллере ESP32.

Допущения и отличия от реального оборудования

Лаборатория делает построение карты чистым, убирая сложную часть настоящего Micromouse — одометрию. Смоделированный робот перемещается ровно на одну клетку за шаг без проскальзывания колёс, смещения гироскопа и ошибки поворота на 90°, а его три датчика расстояния идеально сообщают о стенах без ложных срабатываний. Физическая конструкция на ESP32 накапливает ошибку курса и расстояния при каждом ходе, должна выравниваться по стенам и фильтровать показания ToF с учётом солнечного света и просадки питания, — поэтому руководство по точным поворотам и руководство по заливке уделяют больше времени движению, чем планированию. Используйте этот симулятор, чтобы понять, зачем заливке перепланировать, а не чтобы доказать работу слоя движения.

Схема соединений

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