implementación de pathfinding

[jfcampos]

Hola, alguien sabe de alguna implementación del algoritmo del embudo (funnel) en C++?

O algún buen algoritmo de pathfinding que no esté orientado a cuadrículas (como el A*) ?

[Vicente]

Hay un método llamado "potential fields", pero creo que normalmente se usa más para navegación una vez has conseguido un camino con otro algoritmo (A* por ejemplo).

Cuál es tu problema?

[jfcampos]

Hola.

Estoy haciendo una aventura gráfica, en 2D. De momento usaba el A*, pero las rutas que hace son muy artificiales, además de que para poder usarlo las celdas tienen que ser muy pequeñas. Vamos, que no es el idóneo para este caso.

También me hace muchos zigzags, cosa que con algoritmos como el del embudo no pasan, además de que trabaja con polígonos, lo cual me viene perfecto para el tipo de juego.

Creo que el scumm trabaja con polígonos también.

[Sante]

Antes de nada, aclarar una cosa: el A* no está "orientado a cuadrículas". Se trata de un algoritmo que busca caminos en un grafo de nodos. Esos nodos pueden ser casillas en una cuadrícula, o polígonos. Al algoritmo le da exactamente igual. En ambos casos te va a devolver la lista de casillas o polígonos que conforman el camino.

Dicho esto, no das demasiada información sobre tu problema, ni los detalles del mismo (qué tipo de movimiento buscas, o qué representación del mapa estás usando), así que intentaré cubrir todos los frentes:

- Si estás usando una cuadrícula, y tu problema es que A* devuelve paths demasiado zigzagueantes, una solución rápida es añadir un sobrecoste artificial a todos los nodos que cambien de dirección de movimiento con respecto al nodo anterior. De esta forma penalizas los cambios de dirección arbitrarios, y obtienes paths más rectos. También puedes optimizar el path una vez obtenido, eliminando nodos innecesarios (busca "string pulling"), y hacerlo más natural mediante el uso de splines.

- Si estás usando A* sobre una navmesh poligonal, además de string pulling, puedes usar un algoritmo de Funnel (http://digestingduck.blogspot.com/2010/03/simple-stupid-funnel-algorithm.html) para calcular el path óptimo una vez tienes la lista de polígonos. Leéte los comentarios si vas a usar esto, porque hay algunos puntos que es importante tener en cuenta. Por ejemplo, este algoritmo no toma en consideración el tamaño del agente, y se asume que el navmesh ya está generado dejando suficiente espacio con las paredes, algo que no tiene porqué ser así en tu caso, o que puede dar problemas si planeas tener agentes de distintos tamaños que usen la misma representación poligonal.

- En ese artículo también se enlaza con una descripción de las técnicas usadas por Valve en L4D (http://www.valvesoftware.com/publications/2009/ai_systems_of_l4d_mike_booth.pdf). Pese a lo que dice el autor, el usar técnicas reactivas para seguir el path puede ahorrarte el paso de optimización. Es posible que por las características de tu juego (por ejemplo, si es un juego de acción en la que hay otros elementos móviles o agentes que esquivar), tengas que implementar sí o sí un sistema reactivo, aunque uses un algoritmo de Funnel y calcules un path óptimo, así que teóricamente podrías ahorrarte ese paso.

En fín, que depende mucho de tu juego y de las necesidades del mismo.

[Vicente]

Añadir a la muy buena respuesta de Sante que una vez tengas el camino del A* nada te impide dar una pequeña pasada al mismo y optimizarlo para quitarte zigzags. Por ejemplo:

- coges un nodo (n).
- miras a ver si puedes llegar al nodo n+2, n+3,... en línea recta (está claro que al n+1 puedes).
- en caso de que puedas llegar a un nodo más avanzado que el n+1 (por ejemplo n+4), pues cambias el camino para ser de n a n+4 y listo.
- si no puedes pues pruebas con el siguiente nodo cotra sus sucesores y así.

Esa optimización no tarda casi nada en ejecutarse y te permite dejar los caminos mucho más bonitos. Luego ya depende claro de como te muevas, como tomes las curvas,...

[jfcampos]

Hola, gracias por vuestras respuestas.

El problema del A*, es que yo no uso nodos. Más bien uso zonas en las que se puede caminar, y zonas en las que no.  Gráficamente aquí lo vais a ver muy bien.



Eso es lo máximo que he conseguido optimizar el camino encontrado. He usado varias técnicas para optimizar, pero realmente prefiero cambiar de método, ya que como veis, se puede hacer usando polígonos y algún otro algoritmo, como por ejemplo el funnel que funciona muy bien aunque en mi opinión hace muchos cálculos. Trazar una línea y ver si se sale de cierto polígono casi en cada iteración es algo costoso.

Viendo las imágenes se os ocurre alguna solución mejor que funnel?

[Sante]

Si tienes ya funcionando un sistema basado en casillas, lo más rápido es meter alguna optimización al path (como la que dice Vicente), e incluso suavizarlo mediante splines, y vas a tener un resultado bastante satisfactorio muy rápido.

Si fuera a hacerlo desde cero, yo también usaría una malla poligonal, con algún tipo de optimización al path resultante (sea funnel o no). En tu caso el mayor coste de CPU es algo que puedes obviar, ya que sólo tienes que calcular el path en el momento en que el jugador pulsa en la pantalla, el resto del tiempo te dedicas a recorrerlo. Un proceso algo costoso, pero que se realiza muy pocas veces, no suele tener un impacto en el rendimiento global. Además, en tu caso vas a tener mallas con pocos polígonos, así que tampoco va a ser tan costoso.

[blau]

No creo que tu problema sea de calculo, la verdad, solo se va a mover un personaje.

¿Has probado a usar la polylinea como una spline? interpolando los 4 vertices mas cercanos a donde estes

[blau]

No creo que tu problema sea de calculo, la verdad, solo se va a mover un personaje.

¿Has probado a usar la polylinea como una spline? interpolando los 4 vertices mas cercanos a donde estes

UUupps, no habia refrescado el feed ;)

De todas formas si yo lo hiciera desde el principio tendria todo precalculado desde el principio para zonas pequeñas buscando el camino mas optimo y luego comprobando que me gusta. Total el área por la que te mueves no va a cambiar ni la va a bloquear nadie. ¿o si?

[jfcampos]

Puedo usar spline, pero vuelvo a tener el problema de los zigzags, que con la spline se acentúa.

Lo que he hecho realmente es descartar 1 de cada X puntos del path al hacer la spline, y queda más suave.

He hecho muchas pruebas. A veces, como es lógico, descarta un punto crítico (una esquina) y el muñeco se mete un poco en zona roja... pero para este tipo de escenario no es muy grave.

Me parece una solución un poco "chapuza"... por eso me planteo el cambiar de método.

Una de dos, o uso otro método, o implemento alguna técnica para optimizar el path que sea buena. Sin zigzags, y con el número mínimo de giros posible. Vamos, lo más natural posible, aunque no sea el más corto.

Alguna idea?

El método de optimización que propone Vicente está bien, pero tiene el problema de que terminaría con líneas de distintos ángulos, y como el personaje sólo tiene 8 direcciones animadas, va a quedar un poco moonwalk xD. No obstante, voy a probarlo. Le pondré límites y a ver qué tal queda.

[blau]

¿Has probado en al A* a no quedarte con la primera solucion?

¿Si no a esperar a que la lista de abiertos se acabe? Ahí te quedara el camino optimo. Y ese camino debe ser el que quede mejor.

A mi también me gusta empezar el a* al revés, intercambio destino con origen,  para así no tener que rehacer el camino en orden inverso. :)

Y siguiendo lo que te decia antes prueba a tener un camino principal precalculado o hecho a mano.
Por ejemplo,  las celdas por las que pase el camino pueden tener menos coste de desplazamiento así de forma natural el algoritmo A* tendera a ir por ese camino para distancias largas.

[jfcampos]

Hmmm me gusta eso último que has dicho. Caminos con menos coste predefinidos. Creo que ahí va a estar la solución.

En eso, y en un buen método para suavizar.

Lo probaré, gracias.