Optimización Pathfinding

[trauma]

 Hola gente! Hace tiempo que no paso por aquí. A ver si me podeis ayudar con esto. Estoy haciendo una aventura gráfica que se maneja con el ratón. Al pulsar en un sitio el personaje se desplaza. Para esto estoy utilizando el algoritmo ameba, pendiente de pasar a sonar, por cierto (visitar http://portalxuri.dyndns.org/blitzbasico/index.php si quereis ver como son estos algoritmos). El tema es que a veces para ir de una zona a otra, no hay obstáculos, pero el personaje hace un quiebro igual, debido al cálculo a través de una "tabla". Como me estoy liando, os paso una muestra gráfica.



Este sería el cálculo normal del algoritmo, bien, pues lo que pregunto es si apartir de ese cálculo se podría recalcular algo como esto:



La linea verde representa la segunda ruta que quiero hacer. Sabe alguien si esto es posible?

Bye!!
(saludos a drizzit#,  :D)

[KaMuY]

 No se si te servirá, pero podrías probar hacer un camino en línea recta, recorrer los puntos y si existe colisión calcular  el siguiente punto sin colisión y entonces aplicar el Pathfinding entre los dos. Si lo haces así el personaje ira con el camino mas natural hasta encontrar el obstáculo... volteara el obstaculo de forma inteligente, pero puede que en laberintos raros seguir lo mas intuitivo provoque caminos raros. Pero si en tu caso no hay muchos obstáculos creo que te quedara bien :)

Harás algo como ir siempre en línea recta y bordear siguiendo la pared si el camino esta cortado.

[trauma]

 Gracias por contestar, Kamuy. Es buena idea, pero me surje una duda... Al trazar la linea del punto inicial al final, como hago pa saber si pasa por un nodo u otro cuando esta no coincida exactamente encima de uno? Vamos a lo mio, que son los graficos :P



Si te he entendido bien, deberia chekear los nodos rojos,  no? pero como hago pa saber esos nodos rojos cuales son? Las mates no son lo mio  (nooo)
bye!

[Vicente]

 Hola!

cuanto tiempo trauma ;)

Para optimizar la ruta tienes dos alternativas: la rápida y la lenta :P

La rápida:

- tienes dos nodos n1 y n2 que son el primer y el segundo nodo de tu lista solución. Miras si desde el nodo n1 puedes ir al destino de n2 (sería n3). Si se puede, asignas n2 a n3 y vuelves a repetir.
- si no se puede ir de n1 a n3 directamente, cambias n1 y n2 por n2 y n3 y vuelves a probar.
- repites esto hasta que llegues al final.

La lenta:

- en vez de comprobar n1 solo con n3, compruebas contra todos los nodos del grafo.
- una vez has probado con todos avanzas n1 lo máximo que hayas conseguido optimizar el camino y pruebas desde allí con todos otra vez.

Espero haberme explicado más o menos ;) Un saludo!

Vicente

[zupervaca]

 yo lo que me pregunto es por que en la primera imagen el camino correcto que indicas es por encima del cilindro, yo mas bien veo mas corto por debajo de el, pero bueno solo estoy viendo una imagen

saludos

[ethernet]

 Lo que no sé es la función distancia que usas tú porque aplicando la distancia euclidea de toda la vida el camino que debe tomar no es el que te toma ni por aparición divina.
De todas maneras no veo tan grave el problema del quiebro, sinceramente ese tipo de cosas las dejaría para una fase más avanzada del proyecto, esa optimización no implica para nada cambio de código (si todo está modelado con cierta cabeza). Lo importanto es que funcione y no colisione.

saludos

[sés]

Lo que no sé es la función distancia que usas tú porque aplicando la distancia euclidea de toda la vida el camino que debe tomar no es el que te toma ni por aparición divina.

Bueno, yo ahí veo unas montañitas. El personaje evita subirse por ellas, no lo veo tan raro. Lo que veo más raro es lo que quiere que haga (subirse por ella).

[ethernet]

 El no ha comentado nada acerca de si usa pesos para la búsqueda de caminos. He intentado entrar a la web que comenta pero la sección de descargas (que es donde están los tutoriales) no me tira (el servidor parece que no estar adecuadamente escalado) para ver si usa la altura del HM como peso para el algoritmo. Si es así es lógico técnicamente.

De todas formas una montañita nunca ha sido ningún obstaculo para un personaje de un videojuego XD

saludos

[trauma]

 Hola! Que de respuestas! A ver, primero gracias a Vin por su solución que es muy interesante, y será la que vaya a usar pero... cuando tenga que comprobar si hay algún obstáculo entre dos nodos, por ejemplo, entre el nodo amarillo y azul de mi última imagen, tendré que mirar los puntos rojos que puse no? Bien, pues no sé como averiguo esos puntos adyacentes a la linea cuando no es recta o diagonal perfecta, no sé si me explico. Necesito saber la fórmula para sacarlos y así comprobar si hay obstáculo o no.

Para Zupervaca, Ethernet y Sés (a ver ese fistPC cuando lo terminamos, ;)  jejeje),  El algoritmo que usé es el ameba, que es, digamos, el primer paso, la base, hacía un algoritmo mas potente.  Su creador (Elthan) me ha explicado lo primero que debería hacer, que es poner pesos, ya que en este ejemplo las diagonales tienen la misma distancia que las horizontales y verticales, por eso hace esas cosas raras. Como de pathfinding no tengo mucha idea pues prefiero empezar así para enterarme bien de todo. Pero el problema me parece que no lo resuelven del todo los pesos, puesto que en un terreno liso y sin obstáculos, siempre usaría lineas horizontales, verticales y de 45º. Ahora estoy poniendo los pesos y luego intentaré aplicar la solución de Vin. A ver si me podeís echar un cable con los dichosos puntos rojos. El asunto sería dados dos puntos cualesquiera en una rejilla, sacar las coordenadas de los puntos adyacentes.

Este tema no lo dejo para una fase más avanzada pq tengo todo el mapa y código preparao para hacer estas pruebas y quiero dejarlo cerrado y olvidarme para meterme con otra cosa. Es decir, no tengo prisa por avanzar, lo que quiero es ir tema por tema, hacerlo bien y atacar otro problema. BUeno, voy con los pesos.

Bye!!  

[vincent]

 

Bien, pues no sé como averiguo esos puntos adyacentes a la linea cuando no es recta o diagonal perfecta, no sé si me explico. Necesito saber la fórmula para sacarlos y así comprobar si hay obstáculo o no.

Y si haces que la distancia del punto a la recta sea menor a un cierto epsilon siendo epsilon la raiz quadrada de la hipotenusa del cuadrado partida por dos?

Es una solución cutre pero supongo que te iria bien...

Saludos!

[sés]

a ver ese fistPC cuando lo terminamos, ;)  jejeje

Esos sprites que faltan... y los fondos...


...y la IA ^.^

[trauma]

 

Y si haces que la distancia del punto a la recta sea menor a un cierto epsilon siendo epsilon la raiz quadrada de la hipotenusa del cuadrado partida por dos?

Esto... Vin, estás tan metido en estos rollos que te olvidas que mis mates son muy básicas  :lol:
Si lo puedes explicar un poco más, no sé, como de andar por casa, te lo agradecería  :D
Se que me presentaron a epsilon, pero ahora no me acuerdo de quien es <_<

Esos sprites que faltan... y los fondos...

Ejem... esto...  :rolleyes:  Algún día aparecerán!  :lol:

Taluego!!  

[trauma]

 Perdón, confundí a Vicente con Vicent....

[[Vil]]

 Yo tengo hecho exactamente eso que dices para una aventura gráfica en 3D. Me encontre con el mismo problema y como siempre no se me ocurrio buscar opciones de otras personas y se me ocurrio lo siguiente (q si no recuerdo mal es lo q te han explicado antes).
Imaginemos en tu espacio 3D los nodos se separan por 1 unidad. Tu quieres ir de tu nodo 1 (n1) al nodo 10 (n10) (por ejemplo), y no quieres giros bruscos de 45 o 90 grados.

Lo que yo hago es: miro si puedo ir de n1 a n3 sin chocarme (hasta n2 es evidente), si puedo llegar a n3 sin problemas, pruebo desde n1 a n4, si puedo, pruebo con n5... etc. (que es lo que te han comentado en la primera respuesta si no me equivoco)

Esto me funciona muy muy bien, ahora... el problema puede q sea en saber "si puedo ir de un nodo a otro sin chocarme"

Aqui aparecen las cutrerias que me monto normalmente pa sacar adelante estas cosas (siempre me ha costado mucho encontrar soluciones optimizadas, y no se hasta q punto esta es buena):

Te colocas en la posicion inicial (n1) y voy avanzando 0.1 unidades en dirección al nodo siguiente (por ejemplo el n3) y a cada avance miras en q posicion estás, y si se puede "estar alli". Para eso, pues simplemente miras en que posicion estas (con sus decimales, por ejemplo 4,32 y 2,67), a eso le sacas un int() y miras en tu matriz si esas coordenadas tienen un -1 (o lo q sea muro para ti). Ya ni recuerdo porque puse 0.1, pero asi me va bien, y para las busquedas q hace una aventura gráfica no necesito optimizar nada mas.
Supongo que lo mejor sería conocer cual es la función para "dibujar una linea"... y de eso saben mucho mas los compañeros de stratos q yo...

Ademas le meti que cada vez que avanza 0,1 unidades, no solo mira si puede estar alli, sino q mira en un radio de N unidades, q sería el radio del personaje, asi no pasa pegaito a una esquina transpasandola.

Luego lo complique un poquito mas... pero paso de liarme/te más.

Un saludo

[trauma]

 Ole Vil! Eso ya me vale de mucho, sobre todo pq como lo has probado tú ya se que funciona  :lol: Mmm, la función de la linea tb me puede valer, voy a buscarla por los foros, que seguro que hay algo. Gracias!

Bye!!