Interaktive Demo
Tiefensuche
Die Tiefensuche (DFS) macht immer bei der Zelle weiter, die sie zuletzt erreicht hat. Sie läuft so weit wie möglich in eine Richtung und kehrt erst in Sackgassen um, als würde man ein Labyrinth erkunden und immer den nächsten unbekannten Gang nehmen.
Zeichne Wände oder Schlamm ins Gitter und ziehe Start und Ziel. Ist eine Suche fertig, wird nach jeder Änderung sofort neu gesucht. Probiere ein Labyrinth: Die Tiefensuche löst es, macht in offenen Bereichen aber lange Umwege. Die Reihenfolge der Richtungen (oben, rechts, unten, links) entscheidet, wohin sie zuerst geht.
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
Nein
Nimmt den ersten Weg, auf den sie stößt, oft einen langen Umweg.
Gewichtete Zellen
Nein
Ignoriert die Kosten vollständig.
Heuristik
Nein
Blind: Nur die Reihenfolge der Richtungen entscheidet, wohin sie geht.
Beliebiger Winkel
Nein
Bewegt sich von Zelle zu Zelle, gerade oder diagonal.
Alle Wegfindungsalgorithmen im Vergleich
| Algorithmus | Optimal | Gewichtete Zellen | Heuristik | Beliebiger Winkel |
|---|---|---|---|---|
| Breitensuche | Ohne Schlamm und Diagonalen | Nein | Nein | Nein |
| Tiefensuche diese Seite | 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. Ein Stapel
- Lege den Start auf einen Stapel.
- Nimm die neueste Zelle vom Stapel und überspringe sie, wenn sie schon besucht ist.
- Markiere sie als besucht und lege alle unbesuchten Nachbarn auf den Stapel, die bevorzugte Richtung zuletzt.
- Wiederhole das, bis das Ziel vom Stapel kommt.
2. Tief statt breit
In Bäumen und tiefen Suchen muss sich die Tiefensuche nur den Ast merken, auf dem sie gerade ist, deshalb braucht sie wenig Speicher. Auf einem Gitter bringt das nichts: Sie besucht trotzdem viele Zellen, und der gefundene Weg ist einfach der, den sie zufällig genommen hat.
3. Wo sie verwendet wird
Die Tiefensuche ist die Grundlage von Labyrinthgeneratoren (Recursive Backtracker), topologischer Sortierung, der Suche nach zusammenhängenden Teilen eines Graphen und der Suche in Spielbäumen. Als Wegfinder ist sie eine schlechte Wahl, und gerade deshalb ein guter Vergleich.