Path-Finding en aventuras gráficas

[plugin]

                                Holap de nuevo. Estoy haciendo una pequeña aventura gráfica y me trae loco el movimiento (correcto) de los personajes. Actualmente el sistema de rutas/busqueda de caminos lo resuelvo dividiendo la zona por la que se puede andar en triángulos. Despues calculo los triangulos por los que hay que pasar para llegar al destino. Con esto ya tengo asegurado de que el personaje llega a su destino rodeando cualquier objeto. Pero ahora me viene el problema: yo se los triángulos por los que he de moverme pero ¿dentro de los triangulos por donde me muevo exactamente para que el movimiento sea real?. Es decir, ahora mismo funciona todo bien, pero el personaje al moverse parece que da como rodeos y no anda en linea recta (ya que va de triangulo en triangulo).

He estado leyendo info de path-finding (incluso un post que puso aqui Emotion) pero no consigo aclararme como adaptar eso para una aventura gráfica (ademas que esos algoritmos son algo complejos). En un juego de rol en el que el mapa está dividido en tiles es mas o menos fácil pero ¿como se hace en una aventura gráfica, en la que el escenario no es divisible en partes iguales? ¿Conoceis enlaces donde pueda encontrar más info acerca de esto?

Thanks again. Saludos
--plugin                                

[Kabila]

                                Por que no pruebas a hacerlo por cuadrados de
un tamaño medio 32x32 divides toda la pantalla en un array y marcas por donde se puede pasar y no. Luego aplicas la busqueda de caminos e iria mucho mejor. Ya que el cuadrado tiene todos los lados iguales y es mucho as facil el calculo....tambien cuando esta dentro de un cuadrado lo mueves en esa direccion hasta que sale del mismo que vuelves a pedir camino                                

[plugin]

                                Con cuadrados no me parece buena idea porque es menos preciso (a no ser que fueran paralelepipedos y tendría el mismo problema). Con triángulos me puedo ajustar a la perfección al decorado (no tienen porque ser equiláteros). Lo tengo ya casi listo, lo que hago para bordear un objeto es ir por los vértices de los triángulos que lo rodean. Funciona a la perfección, excepto en algunas ocasiones que estoy viendo como solucionarlo.

Saludos
--plugin                                

[plugin]

                                Bueno, pues me respondo a mi mismo, que ya he dado con la solución. Por si os puede valer lo he solucionado de la siguiente manera: al tener el escenario dividido en triángulos puedo utilizar un simple algoritmo de back-tracking (u otros mas complejos como el A*, aunque no hace falta) para detectar cual será la secuencia de triángulos que tengo que atravesar para llegar al destino. Pueden darse dos casos:
a) Que pueda ir desde el origen al destino en linea recta y SIEMPRE pasando por triángulos -> En ese caso el personaje lo muevo directamente sin calcular ninguna ruta.
B) El personaje no puede ir directamente -> luego se ha de seguir la secuencia de triangulos devuelta por el algoritmo. Ahora bien, el problema me venia de que no sabia por donde tirar dentro de los triangulos. Lo que he hecho al final es ir por las aristas que forman "los vertices comunes" a cada 2 triangulos adyacentes. Puede darse el caso de que 2 triangulos tengan 2 vertices comunes, en ese caso eligo el vertice que hace que la ruta sea mas corta...

Pues nada, que ya lo he resuelto, por si le puede valer a alguien. Hay que decir que el personaje se mueve con bastante coherencia; aunque claro, siempre es "mejorable"

Saludos
--plugin                                

[BeRSeRKeR]

                                ¿Qué tal calcular el baricentro de cada uno de los triángulos a recorrer y pasar por ellos?. Así que una vez que tengas los centros ya puedes crear una spline cuyos puntos de control serían dichos centros y finalmente hacer que el personaje (o lo que sea) recorriera la spline...

Es algo que se me ha venido a la cabeza nada más leer tu post pero vamos que nunca he implementado algo de esto...

Un saludo.
                               

[plugin]

                                Buenas. Efectivamente, lo que comentas de calcular el baricentro e ir de uno a otro fue mi idea original, pero el problema es que el personaje parecía que estaba "borracho", vamos que da muchas vueltas. Lo de la spline sería buena idea quizás si fuera un vehículo; siendo un personaje lo que tiene que moverse es más fácil hacer que se mueva en líneas rectas, aunque hay que optimizar éstas. Os he hecho una imagencita para que veais el resultado (no soy muy buen dibujante como vereis):



Lo que se ve en medio (aunque no lo parezca) es un árbol que se supone hay que esquivar. El algoritmo lo que devuelve es la serie de triángulos a pasar para alcanzar el objetivo (en este ejemplos son todos, es que no he pintado la ruta completa). La línea en amarillo lo que hace es ir de baricentro en baricentro como bien dice BerSerKer. Pero como lo he hecho es más óptimo, caminando por las aristas. Como ves, el camino en azul es mucho más corto y hace menos zig-zags que el otro.

Todavía tengo que optimizarlo un poco porque con rutas más complejas a veces no elije el camino que yo (como humano y ser más inteligente que el ordenador, creo...) eligiría.

Pues eso. Saludos a todos
--plugin

P.D. ¿Porque no se me ve la imagen? Bueno,... este es el enlace: http://www.geocities.com/mugenss/imgs/path.gif

[ Este Mensaje fue editado por: plugin el 2002-04-22 00:12 ]                                

[BeRSeRKeR]

                                Jeje, viendo la imagen la cosa queda bastante clara :sonriendo:

Un saludo
                               

[metaxas]

                                En el Game Programming Gems I hay un artículo en el que te explican un algoritmo de pathfinding basado en mallas de navegación, no sé si lo conoces, pero es exactamente lo mismo que has hecho tú, aunque no sé cómo lo habrás implementado.
La solución que se proponía al final del artículo para suavizar el movimiento era un algoritmo basado en el line-of-view entre dos puntos: coges un punto del camino y lanzas una linea recta hacia el siguiente punto, mientras esa linea no atraviese ningún obstáculo vas cogiendo el siguiente punto del camino y haces lo mismo, hasta que la linea intersecte un objeto, en ese caso coges como siguiente punto el anterior en el que no había habido intersección y repites el proceso con este punto como nuevo punto de origen, hasta que llegues al destino. De esta forma consigues un camino hacia el destino mucho más recto. Luego con esos puntos puedes moverte entre ellos por lineas rectas o, si quieres un movimiento más suave, como te decía Berserker con los puntos te construyes un spline por el que mover al personaje.                                

[plugin]

                                Pues si... Eso que comentas me vale.. Como dije, el algoritmo funciona muy bien, aunque todo es mejorable y este trukillo podría valer para hacer el camino con menos zig-zags (mas recto como bien dices). Pues nada, al final parece que va a quedar un algoritmo muy curioso....

Gracias
--plugin                                

[Loover]

                                Por favor, ¿puedes volver a colocar esa imagen?                                

[plugin]

                                Aqui esta. A ver si se ve ahora. Es tela de cutre, pero valía para ilustrar el ejemplo:



Saludos
--plugin                                

[samsaga2]

                                Lo que hacen mucho las aventuras gráficas es hacer los caminos posibles a mano. Asi si quieres ir de un punto a otro solo tienes que seguir el camino que se ha preprogramado.                                

[plugin]

                                Yap. Pero de la manera que yo lo hago puedes conseguir que el personaje se mueva por CUALQUIER parte de la escena, lo que hace que gane en calidad la aventura. Es más divertido permitir al usuario moverse por donde quiera, además sería un jaleo editar los caminos posibles; como contrapartida el método que yo utilizo, dependiendo de la complejidad de la ruta, puede ocasionar movimientos extraños o poco lógicos en el personaje (aunque la verdad, actualmente esta bastante optimizado y sólo hace cosas raras en contadas ocasiones).

Saludos
--plugin