it-swarm-eu.dev

Wie implementiere ich einen A * -Pfadfindungsalgorithmus mit Bewegungskosten für jede Programmiersprache?

Können wir Menschen dazu bringen, Code von einfachen, optimierten Implementierungen des A * -Pfadfindungsalgorithmus in jeder einzelnen Sprache zu veröffentlichen?

Dies dient hauptsächlich zum Spaß und zum Spielen mit dem, was Stackoverflow selbst kann ... obwohl ich eigentlich daran interessiert bin, eine ActionScript 3-Version davon zu bekommen.

Die Idee ist jedoch, dass diese "Frage" auch in Zukunft für immer aktualisiert wird, selbst wenn verschiedene Programmiersprachen erstellt werden!

Ich kenne keinen anderen Ort im Internet, an dem Pseudocode in viele (noch viel weniger) verschiedene Sprachen "übersetzt" werden kann. Es scheint, als wäre es eine lohnende Ressource, und obwohl es nicht unbedingt das ist, wofür diese Site entwickelt wurde, schadet es nicht, sie auszuprobieren und zu prüfen, ob es sich als eine lohnende Sache herausstellt, für die stackoverflow verwendet werden könnte!

29
IQpierce

Hier ist eine JavaScript-Implementierung , zusammen mit Quellcode und einer Online-Demo Ich habe als Hobby-/Forschungsprojekt gearbeitet. 

Es ist sehr einfach, aber Sie können einige Parameter ändern (Rastergröße, Anzahl der Wände, Debugging-Informationen ein/aus). Es zeigt Ihnen die berechneten Werte für f (x), g (x) und h(x) für jeden geprüften Knoten.

Die Implementierung der Demo-Seite verwendet jQuery.

11
Brian Grinstead

Hier ist eine C++ - Implementierung. Es ist mittlerweile ziemlich gut getestet und wird in kommerziellen Videospielen und verschiedenen KI-Projekten verwendet.

http://code.google.com/p/a-star-algorithm-implementation/

Und es gibt ein Tutorial, das ich zuerst geschrieben habe:

http://www.heyes-jones.com/astar.html

9
justinhj

Hier ist eine C # -Implementierung von einem der Leute, die die Sprache erstellen.

5
Joel Coehoorn

Quellcodes und Demos in verschiedenen Programmiersprachen:

Demo-Liste für jede Sprache:

C++: 1
Java: 3
Processing: 1
Actionscript 3 (Flash): 4
Flex (Flash): 1
Javascript: 6
C#: 1
Ruby: 1
Prolog: 1
Unity: 1
Lua: 1

Pathfinding Demo in verschiedenen Sprachen

Genießen :)

3
Sir

Python und C++ - Quellcode zusammen mit interaktives Lernprogramm . Der Code wurde so geschrieben, dass er allgemein für Diagramme verwendet werden kann, und ist nicht spezifisch für Raster (wie Sie in vielen Beispielen für A * im Web finden). Es verwendet binäre Heaps für die Prioritätswarteschlange (sowohl Python als auch C++ haben binäre Heaps in ihren Standardbibliotheken). Ich habe die Breitensuche, den Algorithmus von Dijkstra und A * auf dieser Seite. Der Code ist ziemlich kurz (kürzer als die meisten A * -Beispielcodes, die ich finde).

1
amitp

Ein AS 3-Beispiel ... http://www.dauntless.be/astar/

1
Chris

Keine Implementierung, aber ich fand http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html eine besonders klare Erklärung des Algorithmus. Hat einen Pseudocode, der die Implementierung sehr einfach macht, zusammen mit einer erweiterten Überprüfung verschiedener Datenstrukturen, die zum Implementieren der offenen und geschlossenen Mengen verwendet werden können, einer Diskussion verschiedener Heuristiken, die in verschiedenen Situationen anwendbar sind, Modifikationen an Heuristiken, um bestimmte Verhaltensweisen zu erhalten (z. B. Annäherung von geraden Linien in Systemen, die nur begrenzte Bewegungswinkel unterstützen), häufige Fallstricke (z. B. Verwenden einer Heuristik mit einer anderen Skala als die tatsächlichen Bewegungskosten) und einige Optimierungen (z. B. Arbeiten mit Regionen mit einheitlichen Kosten anstelle von a Gitter).

1
Jules

A Clojure Implementierung, stark basierend auf einem Beispiel in PAIP .

1
Jeff Foster

Eine VB6-Implementierung.

http://www.gandraxa.com/pathfinding_with_a_star.xml

Dies ist besonders nützlich, da Sie den Prozess schrittweise durcharbeiten und ein gutes Verständnis für die Funktionsweise des Algorithmus erhalten können. Dies kann sehr nützlich sein, wenn der Algorithmus in eine andere Sprache konvertiert wird.

0
G Mastros

Ich habe A * in C implementiert, um C zu lernen. Ich kann nicht versprechen, dass es schön ist, aber es funktioniert! Ich verwendete es, um Project Euler # 83 zu lösen, und es funktionierte bei zwei Testfällen.

https://github.com/PeterMitrano/A-star-Pathfinding/blob/master/problem_83.c

0
Peter Mitrano

Eine optimierte Java-Implementierung ist in GraphHopper verfügbar.

0
Karussell