¿Qué algoritmos de búsqueda de ruta hay? [cerrado]

Me gustaría leer sobre algoritmos de búsqueda de ruta. ¿Hay un manual disponible o algún material o tutoriales en Internet que sería un buen comienzo para mí?

Si está buscando investigar y aprender sobre la búsqueda de caminos en general, definitivamente sugeriría que aprenda más de un algoritmo. Querrá comprender los conceptos generales, pero podrá aplicarlos a lo que sea que esté trabajando. La mayoría de los desarrolladores de juegos que necesitan hacer una búsqueda seria terminan escribiendo sus propios algoritmos personalizados, aunque altamente basados ​​en soluciones conocidas, cada juego es diferente y tendrá requisitos diferentes.

Comenzaría leyendo sobre algunos de los métodos más conocidos como A *, el algoritmo de Dijkstra, las búsquedas de profundidad y amplitud primero. Hay mucha buena información en Internet sobre cada uno de estos. ( http://en.wikipedia.org/wiki/Pathfinding )

Mientras los lee, tome nota de cuáles son las ventajas y desventajas de cada enfoque, así como el tipo de datos con los que puede operar el algoritmo. ¿Se puede aplicar a caminos tridimensionales? ¿Se puede modificar para tener en cuenta nuestra IA humana que quiere evitar las minas terrestres en el mapa?

Cuando se trata de encontrar caminos, A * es prácticamente el boleto dorado que todos usan. Definitivamente deberías saber cómo funciona. ( http://en.wikipedia.org/wiki/A*_search_algorithm )

Aquí hay un buen ejemplo de A *, ya que se aplica a un juego de estrategia en tiempo real, que debe tener en cuenta entidades de diferente tamaño: http://aigamedev.com/open/tutorials/clearance-based-pathfinding/

¡Buena suerte!

Los algoritmos de Pathfinding son básicamente algoritmos de resolución de problemas de búsqueda de gráficos.

http://en.wikipedia.org/wiki/Pathfinding#Algorithms

El más conocido es el algoritmo de Djikstra: http://en.wikipedia.org/wiki/Dijkstra's_algorithm

y su variante A * algoritmo de búsqueda: http://en.wikipedia.org/wiki/A*

Este es un gran recurso inicial que analiza todos los aspectos de la búsqueda de rutas en un enfoque muy fácil de digerir.

Notas de Amit sobre la búsqueda de caminos

... Pathfinding aborda el problema de encontrar un buen camino desde el punto de partida hasta la meta: evitar obstáculos, evitar enemigos y minimizar los costos (combustible, tiempo, distancia, equipo, dinero, etc.). El movimiento aborda el problema de tomar un camino y moverse a lo largo de él. Es posible gastar sus esfuerzos en solo uno de estos. En un extremo, un pathfinder sofisticado junto con un algoritmo de movimiento trivial ...

Pathfinding es un problema bastante resuelto ... como se menciona en casi todas las respuestas aquí, alguna variación en A * será lo que use.

El mayor desafío para mí es cómo quieres representar tu camino . Uso de una cuadrícula, nodos de ruta, mallas de navegación, cuadrículas jerárquicas u otras estructuras complejas, etc.

No tengo ninguna referencia específica en mente, pero explorar AIGameDev te dará todo tipo de ideas sobre lo que hay ahí fuera.

Solo recuerde que cada representación tiene sus pros y sus contras; no se trata de encontrar el "mejor", se trata de encontrar el que mejor se adapte a tu juego .

Hay una buena lista en Wikipedia: Pathfinding

Que yo sepa, A * y D * son muy populares.

Hay varios algoritmos de búsqueda de rutas por ahí.

Uno de los más populares es probablemente A * ( A-Star ). Es un algoritmo muy útil si tiene una función heurística que puede proporcionarle costos estimados para alcanzar un objetivo (por ejemplo, la distancia de la línea de visión al objetivo). A * es muy útil para encontrar la ruta más corta desde el inicio hasta el final.

Aparte de eso, también está el algoritmo de Dijkstra, que es muy útil para encontrar el elemento más cercano de varios elementos. P.ej. si quieres averiguar qué potencia (o similar) está más cerca de tu personaje de juego.

Existen varios otros algoritmos, pero supongo que A * es, con mucho, el más popular. Mat Buckland tiene un excelente capítulo sobre Path-Finding en su libro IA de Juego de programación por ejemplo . Le recomiendo que obtenga una copia. De lo contrario, encontrará mucha información en línea al buscar "Una búsqueda de estrellas".

Aquí hay un tutorial sobre el uso del algoritmo de Dijkstra para encontrar rutas.

Aquí hay un buen ejemplo de A * en un juego con un código psuedo: http://www.anotherearlymorning.com/2009/02/pathfinding-with-a-star/

Esto no es una gran introducción, pero discutimos los algoritmos gráficos ampliamente en nuestra clase de algoritmos el otoño pasado 2009. Usamos este libro,

Introducción a los algoritmos, tercera edición de Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein

http://mitpress.mit.edu/algorithms/

y también ha acompañado conferencias de youtube de una clase de MIT.

http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-046j-introduction-to-algorithms-sma-5503-fall-2005/video-lectures/

Los capítulos 17, 18 y 19 tratan de los caminos más cortos.

Consulte [Algoritmos de búsqueda de gráficos y árboles] en Wikipedia 1 . Son prácticamente solo una variación de la búsqueda en el espacio de estado, solo tienes que pasar por todo esto y encontrar dónde difieren.

También está Collaborative Diffusion , que es uno de los algoritmos mencionados anteriormente que se hace de manera interesante.

Este se ve interesante:

http://www.codeproject.com/Articles/455 ¿ Me pregunto si es mejor que A *?