Wegfindung (Pathfinding)

Ein Micromouse muss nicht nur fahren und stoppen – es soll das Labyrinth möglichst effizient lösen. Dafür gibt es verschiedene Algorithmen, die sich in Komplexität, Speicherbedarf und Qualität des gefundenen Weges unterscheiden.

Übersicht

Algorithmus	Schwierigkeit	Karte nötig?	Findet kürzesten Weg?	Typischer Einsatz
Wall Follower	⭐ Einfach	Nein	Nein	Erster funktionierender Prototyp
Flood Fill	⭐⭐ Mittel	Ja	Ja (bei vollständiger Karte)	Standard bei Micromouse-Wettbewerben
Tiefensuche (DFS)	⭐⭐ Mittel	Ja	Nein	Erkundung unbekannter Labyrinthe
Breitensuche (BFS)	⭐⭐ Mittel	Ja	Ja (ungewichtet)	Garantiert kürzester Weg in Schritten
A*	⭐⭐⭐ Schwer	Ja	Ja (gewichtet)	Optimale Navigation mit Heuristik

Die Algorithmen im Detail

Wall Follower – Der Wandfolger

Der einfachste Ansatz: Der Roboter folgt immer einer Wand – entweder der linken oder der rechten.

Funktionsweise:

• Ist die linke Wand frei → abbiegen und ihr folgen
• Sonst geradeaus fahren
• Ist die linke Wand und geradeaus blockiert → rechts abbiegen
• Überall blockiert → umdrehen

Vorteile:

• Sehr einfach umzusetzen
• Benötigt keinerlei Karte oder Speicher

Nachteile:

• Funktioniert nur in Labyrinthen ohne Inseln (isolierte Wandstücke)
• Findet nicht zwingend den kürzesten Weg

Hinweis

Für einen ersten lauffähigen Roboter ist der Wall Follower ein guter Startpunkt. Er lässt sich direkt in einer State Machine mit den Zuständen DRIVE, TURN_LEFT und TURN_RIGHT umsetzen.

---

Flood Fill – Die Überflutung

Flood Fill ist der Standardalgorithmus bei Micromouse-Wettbewerben. Die Idee: Jede Zelle im Labyrinth bekommt einen Wert, der angibt, wie viele Schritte sie vom Ziel entfernt ist – wie eine Flut, die vom Ziel aus das Labyrinth „überflutet”.

Funktionsweise:

1. Das Ziel erhält den Wert 0.
2. Alle Nachbarn des Ziels (ohne Wand dazwischen) erhalten den Wert 1, deren Nachbarn 2, usw.
3. Der Roboter fährt immer zur Nachbarzelle mit dem kleinsten Wert.
4. Sobald der Roboter eine neue Wand entdeckt, wird die Karte neu berechnet.

Vorteile:

• Findet den kürzesten Weg (bei vollständiger Kenntnis des Labyrinths)
• Passt sich dynamisch an neu entdeckte Wände an

Nachteile:

• Benötigt eine vollständige Karte im Speicher
• Neuberechnung kostet Zeit und Rechenleistung

---

Tiefensuche (DFS) – Depth First Search

Die Tiefensuche erkundet das Labyrinth, indem sie immer so weit wie möglich in eine Richtung vordringt, bevor sie umkehrt.

Vorteile:

• Gut geeignet um das Labyrinth vollständig zu erkunden
• Geringer Speicherbedarf

Nachteile:

• Findet nicht zwingend den kürzesten Weg
• Kann lange Umwege nehmen

---

Breitensuche (BFS) – Breadth First Search

Die Breitensuche erkundet das Labyrinth Schicht für Schicht – zuerst alle Zellen mit Abstand 1 vom Start, dann alle mit Abstand 2, usw.

Vorteile:

• Garantiert den kürzesten Weg (in Anzahl Schritte)
• Einfach zu implementieren

Nachteile:

• Hoher Speicherbedarf (alle besuchten Zellen müssen gespeichert werden)
• Langsamer als A* bei großen Labyrinthen

---

A* – A-Stern

A* ist eine Erweiterung der Breitensuche. Er verwendet eine Heuristik (z.B. die Luftlinien-Distanz zum Ziel), um gezielt in die richtige Richtung zu suchen und unnötige Wege zu überspringen.

Vorteile:

• Findet garantiert den kürzesten Weg
• Deutlich effizienter als BFS in großen Labyrinthen

Nachteile:

• Komplexer zu implementieren
• Benötigt eine gute Heuristik und vollständige Karte

---

Welcher Algorithmus passt zu mir?

Hast du noch keinen laufenden Roboter?
└─→ Wall Follower

Läuft der Roboter, aber du willst den kürzesten Weg finden?
└─→ Flood Fill (Empfehlung für Wettbewerbe)

Willst du tiefer in die Informatik einsteigen?
└─→ BFS → A*

Tipp

Fang mit dem Wall Follower an. Sobald dein Roboter zuverlässig fährt, ist der Umstieg auf Flood Fill der nächste sinnvolle Schritt.

Kontrollfragen

Teste dein Wissen

1. Welcher Algorithmus benötigt keine gespeicherte Karte des Labyrinths?

   1. Wall Follower

   2. Flood Fill

   3. A*

   Absenden

2. Welcher Algorithmus garantiert den kürzesten Weg und ist gleichzeitig der Standardalgorithmus bei Micromouse-Wettbewerben?

   1. Wall Follower

   2. Flood Fill

   3. Tiefensuche (DFS)

   Absenden

3. Was ist der Hauptnachteil des Wall Followers?

   1. Er ist zu schwer zu programmieren.

   2. Er benötigt zu viel Speicher.

   3. Er funktioniert nicht in Labyrinthen mit isolierten Wandinseln und findet nicht zwingend den kürzesten Weg.

   Absenden

4. Was unterscheidet A* von der einfachen Breitensuche (BFS)?

   1. A* benötigt keine Karte.

   2. A* nutzt eine Heuristik, um gezielt in Richtung Ziel zu suchen und ist dadurch effizienter.

   3. A* findet immer einen Weg, BFS nicht.

   Absenden