Jetzt befinden wir uns in der ersten Phase des Wettbewerbese, dem Erkunden vom Labyrinth. Die Maus hat 10 Minuten sich den kürzesten/schnellsten Weg zum Ziel zu finden.
Floodfill-Algorithmus
Es gibt verschiedenste Möglichkeiten ein Labyrinth zu lösen:
- Rechte Hand Regel
- Rekursives Rücksetzverfahren
- shortest-way-finder
- uvm.
Es hat sich jedoch der Floodfill-Algorithmus durchgesetzt. Der Vorteil: Da die Zielposition immer in der Mitte ist, kann dies ausgenützt werden und die Micromouse kann mit möglichst wenigen Bewegung den kürzesten Weg herausfinden. Das spart Zeit und senkt die Fehlerrate.
Funktionsweise
Zu Beginn muss das Feld initialisiert werden. Die Maus erhält ein Grundgerüst das immer gleich aussieht: Alle Außenwände sind gesetzt und die Felder werden mit ihrem Abstand zur Zielposition durchnummeriert, als wenn keine Wände vorhanden wären.
Jetzt werden folgende Schritte widerholt, bis das Ziel erreicht ist:
- Wände scannen
- Zahlenwerte der Felder aktualisieren
- Zum kleinsten Zahlenwert fahren
Wurde das Ziel erreicht, wird geprüft, ob der kürzeste Weg bereits gefunden wurde. Falls nicht, probiert die Micromouse noch andere Wege, bis einer dieser Wege wieder zum Anfang vom Labyrinth führt.
Danach ist das „scannen“ des Labyrinths abgeschlossen und die Micromouse kann mit der schnellen Durchfahrt beginnen.