Doolhofoplosser-simulatie voor flood-fill-planning

Bediening

Kies een modus — Verkennen en dan afrennen of Alleen afrennen — en druk op Start om hem te zien oplossen, of gebruik Stap om zet voor zet te volgen. Nieuwe doolhof bouwt een verse willekeurige doolhof; Opnieuw speelt dezelfde doolhof opnieuw af. Drie snelheden, sneltoetsen en Volledig scherm houden de run beheersbaar. Vetgedrukte lijnen zijn de muren van de doolhof, de gearceerde gangen zijn overal waar de robot heeft verkend (doodlopende wegen inbegrepen), en de vetgedrukte lijn is het kortste pad dat flood fill heeft gevonden.

Theorie

Een rasterdoolhof bestaat uit cellen die door open zijden met elkaar verbonden zijn, met muren tussen de rest. Om de kortste route te vinden moet een robot de doolhof eerst kennen — daarom draait dit lab twee fasen.

Verkennen. De robot loopt de doolhof diepte-eerst met een linkerhandregel: bij elke kruising slaat hij linksaf als dat kan, anders rechtdoor, en dan rechtsaf. Bij een doodlopende weg keert hij terug naar de laatste kruising en neemt hij de volgende tak. Dat herhalen tot elke cel bezocht is, brengt de hele doolhof in kaart — inclusief alle verkeerde paden die hij moest uitsluiten.

Optimaliseren. Met de kaart compleet kent een flood fill het doel afstand nul toe en verspreidt het oplopende waarden naar buiten langs elke open zijde. Elke cel bevat nu zijn afstand tot het doel, dus het kortste pad is eenvoudig dit: ga vanaf het startpunt steeds naar een buurcel met een getal lager. De robot rent dat pad af — veel korter dan de zwerpende verkenning.

Algoritme

1. Verken de doolhof diepte-eerst met een linkerhandregel, terugkerend uit elke doodlopende weg, tot alle cellen bezocht zijn.
2. Leg elke open zijde aan beide kanten vast, zodat de afgeronde kaart elke muur kent.
3. Flood-fill vanaf het doel: label het 0 en verspreid oplopende afstanden naar buiten langs elke open zijde.
4. Lees het kortste pad van het veld af: ga vanaf het startpunt steeds naar een buurcel waarvan de afstand één lager is.
5. Ren dat pad af naar het doel.
6. Vergelijk de lengte van de verkenning met die van het kortste pad om te zien hoeveel zweren de kaart heeft bespaard.

Broncode

Splits verkennen, in kaart brengen, plannen en bewegen in afzonderlijke functies:

// 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

Die scheiding maakt dezelfde planner testbaar in dit browserlab, op een desktop en op de uiteindelijke ESP32-controller.

Aannames en hardwareverschillen

Het lab maakt het in kaart brengen overzichtelijk door het lastige deel van een echte Micromouse weg te nemen: de odometrie. De gesimuleerde robot beweegt precies één cel per stap, zonder wielslip, zonder gyro-afwijking en zonder fout bij het 90° draaien, en zijn drie afstandssensoren melden muren perfect, zonder fout-positieven. Een fysieke ESP32-build accumuleert bij elke stap fouten in richting en afstand, moet opnieuw rechtzetten tegen de muren en moet ToF-metingen filteren tegen zonlicht en spanningsval — en daarom besteden de tutorial over precieze bochten en de flood-fill-handleiding meer tijd aan beweging dan aan planning. Gebruik deze simulatie om te begrijpen waarom flood fill opnieuw plant, niet om je bewegingslaag te bewijzen.

Schakelschema

Gebruik een externe spanningsregelaar die gedimensioneerd is op de vastloopstroom van de motor. De ESP32 en de sensoren hebben een stabiele logische voeding nodig, ook wanneer de motoren omkeren.