artificial intelligence - que - ¿Cómo implemento un algoritmo de identificación de ruta A*, con costos de movimiento para cada lenguaje de programación?
que es un algoritmo (11)
Una implementación de VB6.
http://www.gandraxa.com/pathfinding_with_a_star.xml
Esto es particularmente útil porque 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.
¿Podemos hacer que las personas publiquen 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 hacer ... aunque en realidad estoy interesado en obtener una versión de esto de ActionScript 3.
¡Pero la idea es que esta "Pregunta" continuará siendo actualizada 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 (y mucho menos) diferentes idiomas. Parece que es un recurso que vale la pena, y aunque no necesariamente es para lo que este sitio fue diseñado, no hay ningún problema en probarlo y ver si resulta ser algo valioso para que stackoverflow pueda ser utilizado.
Aquí hay una implementación de C # realizada por una de las personas que construyen el lenguaje.
Un ejemplo de AS 3 ... http://www.dauntless.be/astar/
Aquí hay una implementación de C ++. Ya está bastante probado y se usa en videojuegos comerciales y en varios proyectos de inteligencia artificial.
http://code.google.com/p/a-star-algorithm-implementation/
Y hay un tutorial, que en realidad escribí primero:
No es una implementación, pero encontré http://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html como 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 pueden usarse para implementar los conjuntos abiertos y 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).
Códigos fuente y demos en diferentes lenguajes de programación:
Lista de demostraciones 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
Demostración de Pathfinding en diferentes idiomas
Disfruta :)
Aquí hay una implementación de JavaScript , junto con el código fuente y una demostración en línea que hice como un hobby / proyecto de 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.
Una implementación optimizada de Java está disponible en GraphHopper.
Implementé A * en C como una forma de aprender C, así que no puedo prometer que sea 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
El código fuente de Python y C ++ junto con el tutorial interactivo . 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).