Interaktive Demo
Breitensuche
Die Breitensuche (BFS) erkundet ein Gitter wie eine Welle: erst alle Zellen einen Schritt entfernt, dann zwei Schritte, dann drei. Erreicht sie das Ziel zum ersten Mal, hat sie einen Weg mit den wenigsten Schritten gefunden.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Male etwas Schlamm zwischen Start und Ziel: Die Breitensuche läuft mitten hindurch, denn jeder Schritt zählt gleich.
Ablauf
- Erweitert
- –
- Front (max.)
- –
- Wegkosten
- –
Drücke Abspielen oder Nächster Schritt, um die Suche zu starten.
Raster
Optionen
Legende
- Start (ziehen zum Verschieben)
- Ziel (ziehen zum Verschieben)
- Wand
- Schlamm
- Front (Open List)
- Besucht (Closed List)
- Gerade erweitert
- Weg
Eigenschaften
Optimal
Mit Bedingung
Wenigste Schritte, das ist nur ohne Schlamm und Diagonalen der günstigste Weg.
Gewichtete Zellen
Nein
Jeder Schritt zählt gleich, Schlamm wird wie freies Gelände durchquert.
Heuristik
Nein
Weiß nicht, wo das Ziel liegt, und breitet sich gleichmäßig in alle Richtungen aus.
Beliebiger Winkel
Nein
Bewegt sich von Zelle zu Zelle, gerade oder diagonal.
Alle Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche diese Seite | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche | Nein | Nein | Nein | Nein |
| Dijkstra-Algorithmus | Ja | Ja | Nein | Nein |
| Bidirektionale Suche | Ja | Ja | Nein | Nein |
| Gierige Bestensuche | Nein | Nein | Ja | Nein |
| A*-Suche | Mit Gewicht 1 und zulässiger Heuristik | Ja | Ja | Nein |
| Jump Point Search | Ohne Schlamm | Nein | Ja | Nein |
| Theta* | Nein | Abkürzungen nur über freies Gelände | Ja | Ja |
1. Eine Warteschlange
- Lege den Start in eine Warteschlange.
- Nimm die älteste Zelle heraus und sieh dir ihre Nachbarn an.
- Jeder noch nicht gesehene Nachbar merkt sich, woher er kam, und stellt sich hinten an.
- Wiederhole das, bis das Ziel herausgenommen wird. Die Vorgänger rückwärts ergeben den Weg.
2. Wenigste Schritte
Weil die Warteschlange zuerst herausgibt, was zuerst kam, verlassen die Zellen sie in der Reihenfolge ihrer Schrittzahl. Deshalb ist die Breitensuche optimal, wenn jeder Schritt gleich viel kostet. Mit Schlamm oder diagonalen Schritten (√2) sind die wenigsten Schritte nicht der günstigste Weg.
3. Wo sie verwendet wird
Die Breitensuche ist einfach und braucht keine Schätzung der Entfernung. Sie findet kürzeste Wege in ungewichteten Graphen, etwa die wenigsten Züge in einem Puzzle, Freunde von Freunden in einem Netzwerk oder die Fläche der Füllfunktion in einem Malprogramm.