Visualisiere Pathfinding-Algorithmen

Name: Visualisiere Pathfinding-Algorithmen
Author: Kitmul

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

Visualisiere Pathfinding-Algorithmen Schritt fuer 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, Pfadlaenge und Ausfuehrungszeit 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 auszufuehren. Nutze Labyrinth Generieren fuer 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 fuer automatische Hindernisplatzierung. Die gruene Zelle ist Start und die rote ist Ziel.

Algorithmus waehlen

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

Ausfuehren und Vergleichen

Druecke Starten um dem Algorithmus beim Erkunden zuzusehen. Vergleiche besuchte Knoten, Pfadlaenge und Ausfuehrungszeit zwischen Algorithmen.

Guide

Vollstaendiger Leitfaden zu Pathfinding-Algorithmen

Warum Pathfinding wichtig ist

Pathfinding-Algorithmen sind fundamental fuer Informatik und Ingenieurwesen. Sie treiben GPS-Navigation, Spiele-KI, Netzwerk-Routing und Robotik an. Das Verstaendnis 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 moeglich bevor es zurueckgeht. BFS nutzt mehr Speicher waehrend 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 Prioritaetswarteschlange.

A* und heuristische Suche

A* kombiniert Dijkstras garantierte Optimalitaet mit einer heuristischen Schaetzung 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 Laenge 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 waehrend 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 haeufig in Coding-Interviews. Die Visualisierung baut das mentale Modell auf, das zur Implementierung noetig ist.”

Haeufig 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 schaetzen 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 zurueckgeht. Wenn das Ziel in dieser Richtung liegt, findet es dies schnell. Aber der gefundene Pfad kann viel laenger als optimal sein.

?Welche Heuristik nutzt A* hier?

Manhattan-Distanz (Summe der horizontalen und vertikalen Distanzen zum Ziel). Dies ist zulaessig fuer 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?

Vollstaendig. Alle Algorithmen laufen in deinem Browser. Keine Daten werden an einen Server gesendet.

?Ist dieses Tool kostenlos?

Ja. Voellig kostenlos ohne Anmeldung, ohne Limits und ohne Werbung.

?Kann ich diagonale Bewegung nutzen?

Die aktuelle Implementierung nutzt 4-Richtungs-Bewegung. Dies passt zur Manhattan-Distanz-Heuristik die von A* fuer 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 Buecher ueber Algorithmen und Graphentheorie

Erweitern Sie Ihre Fähigkeiten

Empfohlene Produkte fuer Algorithmus-Studium

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