Visualisiere Pathfinding-Algorithmen

Name: Visualisiere Pathfinding-Algorithmen
Author: Kitmul

Visualisiere A*, Dijkstra, BFS und DFS Pathfinding-Algorithmen Schritt für Schritt auf einem interaktiven Raster.

Visualisiere Pathfinding-Algorithmen Schritt für Schritt auf einem interaktiven Raster. Zeichne Waende durch Klicken und Ziehen, generiere zufaellige Labyrinthe, dann fuehre A*, Dijkstra, BFS oder DFS aus, um dem Algorithmus in Echtzeit beim Erkunden des Rasters zuzusehen. Vergleiche besuchte Knoten, Pfadlänge und Ausführungszeit zwischen Algorithmen. Beinhaltet Pause, Geschwindigkeitskontrolle und Labyrinthgenerierung. Alles laeuft in deinem Browser ohne Serveraufrufe.

Geschwindigkeit

Start

Ziel

Wand

Besucht

Pfad

Klicke und ziehe um Waende zu zeichnen. Klicke Starten um den Algorithmus auszuführen. Nutze Labyrinth Generieren für zufaellige Hindernisse.

Deine Daten bleiben in deinem Browser

War dieses Tool hilfreich?

Dieses Tool bewerten

Anleitung

Raster einrichten

Klicke und ziehe auf dem Raster um Waende zu zeichnen. Nutze Labyrinth Generieren für automatische Hindernisplatzierung. Die gruene Zelle ist Start und die rote ist Ziel.

Algorithmus wählen

Waehle A*, Dijkstra, BFS oder DFS aus den Algorithmus-Tabs. Jeder erkundet das Raster anders und liefert unterschiedliche Ergebnisse.

Ausführen und Vergleichen

Druecke Starten um dem Algorithmus beim Erkunden zuzusehen. Vergleiche besuchte Knoten, Pfadlänge und Ausführungszeit zwischen Algorithmen.

Guide

Vollständiger Leitfaden zu Pathfinding-Algorithmen

Warum Pathfinding wichtig ist

Pathfinding-Algorithmen sind fundamental für Informatik und Ingenieurwesen. Sie treiben GPS-Navigation, Spiele-KI, Netzwerk-Routing und Robotik an. Das Verständnis wie verschiedene Algorithmen einen Graphen erkunden und die Abwaegungen zwischen Optimalitaet, Geschwindigkeit und Speicher ist essenziell.

Breitensuche vs Tiefensuche

BFS erkundet alle Nachbarn auf der aktuellen Distanz bevor es weitergeht und garantiert kuerzeste Pfade auf ungewichteten Graphen. DFS folgt einem Pfad so tief wie möglich bevor es zurückgeht. BFS nutzt mehr Speicher während DFS weniger nutzt.

Dijkstra und gewichtete Graphen

Dijkstra erweitert BFS auf gewichtete Graphen indem es immer den Knoten mit der kleinsten bekannten Distanz expandiert. Auf ungewichteten Rastern verhaelt es sich identisch zu BFS. Seine Zeitkomplexitaet ist O((V+E) log V) mit einer Prioritätswarteschlange.

A* und heuristische Suche

A* kombiniert Dijkstras garantierte Optimalitaet mit einer heuristischen Schätzung der verbleibenden Distanz. Durch Priorisierung von Knoten die naeher am Ziel erscheinen erkundet A* typischerweise weit weniger Knoten als Dijkstra bei gleichem kuerzestem Pfad.

Sources

Examples

Geloeste Beispiele

Beispiel: BFS auf offenem Raster

Gegeben: ein 10x10 Raster ohne Waende, Start bei (0,0), Ziel bei (9,9).

Schritt 1: BFS expandiert von (0,0) und besucht alle Zellen auf Distanz 1, dann Distanz 2, etc.

Schritt 2: Jeder Expansionsring deckt Zellen auf Manhattan-Distanz d vom Start ab.

Schritt 3: BFS erreicht (9,9) auf Distanz 18 (9 rechts + 9 unten).

Ergebnis: BFS findet optimalen Pfad der Länge 19 Zellen. Besucht etwa 100 Zellen auf offenem Raster.

Beispiel: A* vs Dijkstra Effizienz

Gegeben: ein 25x40 Raster mit verstreuten Waenden, Start bei (12,5), Ziel bei (12,34).

Schritt 1: Dijkstra erkundet gleichmaessig in alle Richtungen vom Start.

Schritt 2: A* priorisiert Zellen naeher am Ziel und fokussiert die Erkundung nach rechts.

Schritt 3: Beide finden denselben optimalen Pfad, aber A* besucht 40-60% weniger Knoten.

Ergebnis: A* findet denselben kuerzesten Pfad wie Dijkstra bei deutlich weniger besuchten Knoten.

Anwendungsfälle

Anwendungsfaelle

Algorithmus-Unterschiede lernen

“Fuehre BFS und DFS auf demselben Raster aus um zu sehen, wie Breitensuche gleichmaessig in alle Richtungen erkundet während Tiefensuche tief entlang eines Pfades taucht.”

A*-Heuristiken verstehen

“Vergleiche A* mit Dijkstra auf einem offenen Raster. A* nutzt die Manhattan-Distanz-Heuristik um weniger Knoten zu besuchen und dennoch den gleichen optimalen Pfad zu finden.”

Technische Interviews vorbereiten

“Fragen zu Graphendurchlaeufen und kuerzesten Pfaden sind häufig in Coding-Interviews. Die Visualisierung baut das mentale Modell auf, das zur Implementierung noetig ist.”

Häufig gestellte Fragen

?Was ist der Unterschied zwischen A* und Dijkstra?

Beide finden kuerzeste Pfade, aber A* nutzt eine Heuristik um die Distanz zum Ziel zu schätzen und besucht weniger Knoten. Dijkstra erkundet alle Richtungen gleichmaessig.

?Findet BFS immer den kuerzesten Pfad?

Ja, auf ungewichteten Rastern findet BFS immer den kuerzesten Pfad, da es Knoten in Reihenfolge der Distanz vom Start erkundet.

?Warum besucht DFS manchmal weniger Knoten?

DFS erkundet eine Richtung tief bevor es zurückgeht. Wenn das Ziel in dieser Richtung liegt, findet es dies schnell. Aber der gefundene Pfad kann viel länger als optimal sein.

?Welche Heuristik nutzt A* hier?

Manhattan-Distanz (Summe der horizontalen und vertikalen Distanzen zum Ziel). Dies ist zulaessig für 4-Richtungs-Bewegung und garantiert optimale Pfade.

?Wie wird das Labyrinth generiert?

Durch rekursives Backtracking, ein klassischer Labyrinth-Generierungsalgorithmus der ein perfektes Labyrinth mit genau einem Pfad zwischen zwei beliebigen Zellen erstellt.

?Sind meine Daten privat?

Vollständig. Alle Algorithmen laufen in deinem Browser. Keine Daten werden an einen Server gesendet.

?Ist dieses Tool kostenlos?

Ja. Völlig kostenlos ohne Anmeldung, ohne Limits und ohne Werbung.

?Kann ich diagonale Bewegung nützen?

Die aktuelle Implementierung nutzt 4-Richtungs-Bewegung. Dies passt zur Manhattan-Distanz-Heuristik die von A* für garantiert optimale Pfade verwendet wird.

Hilf uns besser zu werden

Wie gefällt Ihnen dieses Tool?

Jedes Tool bei Kitmul wird auf Basis echter Nutzeranfragen gebaut. Ihre Bewertung und Ihre Vorschläge helfen uns, Bugs zu beheben, fehlende Funktionen hinzuzufügen und die Tools zu bauen, die Sie wirklich brauchen.

Empfohlene Bücher über Algorithmen und Graphentheorie

Erweitern Sie Ihre Fähigkeiten

Empfohlene Produkte für Algorithmus-Studium

Q1 Pro Kabellose Mechanische Tastatur, QMK/VIA Programmierbar, 75% Layout