Shortest Path Algorithmus in JavaScript

Als ich in der grauen Vorzeit Informatik studiert habe gab es im Grundstudium ein paar Algorithmen, auf denen jeder Professor bis zum Erbrechen rum geritten ist. Neben dem Suchen von Elementen und den damit verbundenen Bäumen hatten es scheinbar insbesondere die Shortest Path Algorithmen den Professoren angetan. Algorithmen deswegen, weil es logischerweise nicht den einen sinnvollen Algorithmus gibt, sondern eine ganze Auswahl an Lösungen die je nach Anwendung zum Einsatz kommen.

Lösung eines Shortest Path Algorithmus
Der Algorithmus von Dijkstra löst das Problem der kürzesten Pfade für einen gegebenen Startknoten

Der Trick am Shortest Path ist, das sich seine Komplexität fast beliebig steigern lässt, so zum Beispiel dadurch das die Durchquerung eines Feldes auf der Karte unterschiedlich viel kostet (Wasser, Berge, etc.). Ein Shortest Path steuert in der Regel jeden Gegner in einem Computerspiel und gehört zu einer gescheiten KI. Früher, als wir noch den C64 hatten, klappte das nicht so gut, da hat sich ein Skelett schon mal verlaufen. Heutzutage kann man sich drauf verlassen das der kürzeste Weg immer und zu jeder Zeit gefunden wird.

Inzwischen gibt es eine Umsetzung in JavaScript mit dem Namen Pathfinding.js, die direkt mehrere Shortest Path Algorithmen umsetzt und visualisiert. Eine feine Sache und vor allem die Visualisierung macht die Unterschiede zwischen den einzelnen Algorithmen schnell klar. Hätte mir beim Studium echt prima geholfen! ;) Wer sich immer noch wundert wieso man so etwas braucht: setzt mal Pac Man als HTML5-Game ohne Shortest Path Algorithmus um. Die Gegner rennen orientierungslos durch die Gegend und treffen einen eher durch Zufall. Bei einem Shortest Path ist ihre aktuelle Position der Ausgangspunkt, die Position des Spielers der Zielpunkt und der Algorithmus liefert den kürzesten Weg dorthin.

Viel Spaß mit Pathfinding.js – es macht echt Spaß da kleine Level zu bauen und sich einfach nur die Visualisierung anzuschauen! ;)

Ähnliche Beiträge

Skalierbare JavaScript Application Architektur Ich habe gerade bei Nettuts ein interessantes Video gefunden, das ich euch nicht vorenthalten möchte. In rund einer Stunde erklärt Nicholas Zakas eine...
d3.js – Visualisierung von Daten mit Javascr... Seit dem ganzen Hype um das Canvas-Element in HTML5 ist es scheinbar zu einem Volkssport geworden, Libraries für Javascript zu entwickeln, die entwede...
$.Callbacks() in jQuery 1.7 Ab und an scheint doch nochmal etwas neues und sinnvolles in jQuery zu kommen, in der Version 1.7 sind es wohl unter anderem die $.Callbacks(). Im Pri...
Die Installation von CoffeeScript CoffeeScript ist eine feine Sache, um schneller einfacher lesbareres JavaScript zu erstellen. Es ist eine Meta-Sprache die JavaScript entschärft und -...

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.