Come implementare un algoritmo A * Pathfinding, con costi di movimento per ogni linguaggio di programmazione?

Question

Possiamo far sì che le persone pubblichino codice di implementazioni semplici e ottimizzate dell'algoritmo A * Pathfinding, in ogni singola lingua?

Questo è principalmente per divertimento e per giocare con ciò che stackoverflow è in grado di ... anche se in realtà sono interessato a ottenere una versione di ActionScript 3 di questo.

Ma l'idea è che questa "Domanda" continuerà ad essere aggiornata eternamente nel futuro, anche se vengono creati diversi linguaggi di programmazione!

Non conosco nessun altro posto online in cui è possibile vedere lo pseudocodice "tradotto" in molte (molto meno ogni) lingua diversa. Sembra che sia una risorsa utile, e anche se non necessariamente ciò per cui questo sito è stato progettato, non c'è nulla di male nel provarlo e vedere se si rivela essere una cosa utile che lo stackoverflow potrebbe essere utilizzato per!

Answer 1

Ecco uno C# implementation eseguito da una delle persone che costruiscono la lingua.

Answer 2

Un'implementazione VB6.

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

Ciò è particolarmente utile perché si può fare un passo attraverso il processo e ottenere una buona comprensione di come funziona l'algoritmo. Questo può essere molto utile quando si converte l'algoritmo in un'altra lingua.

Answer 3

Ecco un'implementazione in C++. Ormai è abbastanza ben collaudato e utilizzato nei videogiochi commerciali e in vari progetti di intelligenza artificiale.

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

E c'è un tutorial, che ho scritto prima:

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

Answer 4

Ecco una JavaScript implementation, insieme a source code ed un online demo ho fatto come un progetto hobby/di ricerca.

È molto semplice, ma è possibile modificare alcuni parametri (dimensione della griglia, numero di muri, informazioni di debug on/off). Ti mostrerà i valori calcolati di f (x), g (x) e h (x) per ogni nodo ispezionato.

L'implementazione della pagina demo utilizza jQuery.

Answer 5

Un AS 3 esempio ... http://www.dauntless.be/astar/

Answer 6

A Clojure implementazione, fortemente basato su un esempio dato in PAIP.

Answer 7

Non un'implementazione, ma ho trovato http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html una spiegazione particolarmente chiara dell'algoritmo. Ha uno pseudocodice che lo rende molto facile da implementare, insieme a una revisione estesa delle varie strutture dati che possono essere utilizzate per implementare gli insiemi aperti &, una discussione di diverse euristiche applicabili in situazioni diverse, modifiche all'euristica per ottenere comportamenti specifici (ad esempio ottenere approssimazioni di linee rette in sistemi che supportano solo angoli di movimento limitati), insidie ​​comuni (ad esempio utilizzando un'euristica con una scala diversa rispetto ai costi di movimento effettivi) e alcune ottimizzazioni (ad esempio, lavorare con regioni di costo uniforme piuttosto che un griglia).

Answer 8

Un ottimizzato Java implementation è disponibile in GraphHopper.

Answer 9

codici sorgente e dimostrazioni in diversi linguaggi di programmazione:

Elenco dei demo per ogni lingua:

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 different languages

Enjoy :)

Answer 10

ho implementato A * a C come un modo per imparare C, quindi non posso promettere che è bello, ma funziona! L'ho usato per risolvere Project Euler # 83 e ha funzionato su due casi di test.

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

Answer 11

Python and C++ source code con interactive tutorial. Il codice è scritto per funzionare su grafici in generale e non è specifico per le griglie (come si troverà in molti esempi di A * sul web). Usa gli heap binari per la coda di priorità (sia Python che C++ hanno un heap binario nelle loro librerie standard). Ho una ricerca per ampiezza, l'algoritmo di Dijkstra e A * su quella pagina. Il codice è ragionevolmente breve (più corto della maggior parte del codice di esempio A * che trovo).