¿Cómo implemento un algoritmo de identificación de ruta A *, con los costos de movimiento para cada lenguaje de programación?

Question

¿Podemos hacer que la gente publique código de implementaciones simples y optimizadas del algoritmo de identificación de ruta A * en todos los idiomas?

Esto es principalmente por diversión y para jugar con lo que stackoverflow es capaz de ... aunque en realidad estoy interesado en obtener una versión de ActionScript 3 de esto.

Pero la idea es que esta "Pregunta" continuará actualizándose eternamente en el futuro, ¡incluso cuando se creen diferentes lenguajes de programación!

No conozco ningún otro lugar en línea en el que pueda ver el pseudocódigo "traducido" en muchos (mucho menos cada) idioma diferente. Parece que es un recurso que vale la pena, y aunque no es necesariamente para lo que se diseñó este sitio, no hay problema en probarlo y ver si resulta ser algo valioso para que stackoverflow pueda ser utilizado.

Answer 1

Aquí hay un C# implementation hecho por una de las personas que construyen el lenguaje.

Answer 2

Implementación de VB6.

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

Esto es particularmente útil porque se puede pasar por el proceso y obtener una buena comprensión de cómo funciona el algoritmo. Esto puede ser bastante valioso al convertir el algoritmo a otro idioma.

Answer 3

Aquí hay una implementación de C++. Ya se ha probado bastante bien, y se usa en videojuegos comerciales y varios proyectos de inteligencia artificial.

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

Y hay un tutorial, que en realidad escribí primero:

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

Answer 4

Aquí es una JavaScript implementation, junto con source code y un online demo lo hice como un proyecto de manía/investigación.

Es muy simple, pero puede cambiar algunos de los parámetros (tamaño de cuadrícula, número de muros, información de depuración activada/desactivada). Le mostrará los valores f (x), g (x) y h (x) calculados para cada nodo que se inspecciona.

La implementación de la página de demostración usa jQuery.

Answer 5

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

Answer 6

Un Clojure aplicación, fuertemente basada en un ejemplo dado en PAIP.

Answer 7

No es una implementación, pero encontré que http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html es una explicación particularmente clara del algoritmo. Tiene pseudocódigo que lo hace muy fácil de implementar, junto con una revisión extendida de varias estructuras de datos que se pueden usar para implementar los conjuntos cerrados &, una discusión de diferentes heurísticas que son aplicables en diferentes situaciones, modificaciones a la heurística para obtener comportamientos específicos (por ejemplo, obtener aproximaciones de líneas rectas en sistemas que solo admiten ángulos de movimiento limitados), dificultades comunes (por ejemplo, utilizar una heurística con una escala diferente a los costos de movimiento reales) y algunas optimizaciones (por ejemplo, trabajar con regiones de costo uniforme en lugar de cuadrícula).

Answer 8

Un optimizado Java implementation está disponible en GraphHopper.

Answer 9

códigos fuente y demostraciones en diferentes lenguajes de programación:

Lista de demostración de para cada idioma:

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

implementé A * en C como una forma de aprender C, así que no puedo prometer que es hermoso, ¡pero funciona! Lo usé para resolver Project Euler # 83 y funcionó en dos casos de prueba.

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

Answer 11

Python and C++ source code junto con interactive tutorial. El código está escrito para trabajar en gráficos en general, y no es específico para grillas (como lo encontrará en muchos ejemplos de A * en la web). Utiliza montones binarios para la cola de prioridad (tanto Python como C++ tienen montones binarios en sus bibliotecas estándar). Tengo la Primera búsqueda de ancho, el Algoritmo de Dijkstra y A * en esa página. El código es razonablemente corto (más corto que la mayoría del código de muestra A * que encuentro).