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.
(http://www.telecable.es/personales/jolusfer/ruta1.jpg)
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:
(http://www.telecable.es/personales/jolusfer/ruta2.jpg)
La linea verde representa la segunda ruta que quiero hacer. Sabe alguien si esto es posible?
Bye!!
(saludos a drizzit#, :D)
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.
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
(http://www.telecable.es/personales/jolusfer/ruta3.jpg)
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!
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
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
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
Cita de: "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.
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).
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
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!!
CitarBien, 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!
Cita de: "trauma"a ver ese fistPC cuando lo terminamos, ;) jejeje
Esos sprites que faltan... y los fondos...
...y la IA ^.^
CitarY 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 <_<
CitarEsos sprites que faltan... y los fondos...
Ejem... esto... :rolleyes: Algún día aparecerán! :lol:
Taluego!!
Perdón, confundí a Vicente con Vicent....
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
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!!
vamos a poner un dibujo a ver si se vé mejor....
(http://www.salleurl.edu/~vgarcia/recta.jpg)
como espero que puedas ver (soy un desastre dibujando :) ) un puto estará cerca de tu recta (lo que está en azul) si su distancia a la recta es menor que la mitad de la hipotenusa de uno de los cuadrados que tengas (en caso de que todos los quadrados sean iguales).
Espero que te sirva.
Saludos
Trauma, la solución a ese problema es muy conocida. Es lo que se llama navegación por waypoints y, en particular, por esquinas. El truco está en no utilizar todos los nodos que tienes (que son un montón), sino en poner los nodos que necesitas y únicamente estos.
¿Cuáles son los nodos que necesitas?
El nodo de comienzo
El nodo de final
Las esquinas
Para los arcos, dos nodos estarán unidos por un arco si los nodos tienen visibilidad entre ellos. Para la visibilidad te conviene usar un algoritmo a lo Bresenham o Wu (si hay webos de implementarlo).
En las imágenes que posteas y con este método el número de nodos puede ser de unos veinte. Teniendo en cuenta que los algoritmos de búsqueda de caminos son O(2^n) es mejor que ese n sea pequeñito (es decir, pocos nodos). Además, existen métodos que reducen la complejidad aún más clasificando los tipos de esqunas.
En realidad lo que haces, Vil, es un chequeo de colisiones de tu camino con los obstáculos del entorno, pero como quien usa el camino es un personaje con dimensiones, puedes aprovecharte de ello para optimizar un poco los chequeos de colisiones usando el "bounding box" o sucedáneos del personaje. Traducido:
Si sabes a priori el radio "r" del personaje o lo que sea que se mueve...¿no se podría hacer la búsqueda cada "r" en lugar de cada 0.1 u otra cantidad más o menos arbitraria?
Por radio me refiero a la distancia entre el centro de movimiento del personaje y el punto más alejado del mismo del modelo (por ejemplo, la punta de los dedos de la mano)
Ok Vicent! Ahora entiendo todo, esta claro que yo sólo funciono con gráficos :P Esa sería una forma muy precisa de hacerlo.
Tb he mirado el algoritmo de Bresenham
http://www.tscc.de/tc_line.html y tiene muy buena pinta, pq al final mira la cuadrícula por donde pasa una linea, ya sea pa dibujarla o para chequearla, que es lo que quiero yo :D
Bueno, tengo ya un montón de opciones para aplicar, gracias a todos. Iré probando a ver que tal.
Bye!! (ole)
yo aplicaria la que dice gdl ya que es la mas usada, ademas si usas algun exportador para max puedes hacer que los splines que quieras sean los caminos
saludos
Hola otra vez, he encontrado una pequeña modificación del algoritmo Bresenham que detecta todas las cuadrículas por donde pasa, no sólo las óptimas, para chequear obstaculos
http://lifc.univ-fcomte.fr/~dedu/projects/bresenham/Taluego!
Hola!
te me has adelantado con el Bresenham! ;) Yo lo he visto este año para pintar una recta compuesta de pixels, y mira que me parece curioso que pega bastante bien para aplicarlo en este caso. Pues nada, a ver que tal ese jueguecito y cuando te vuelvo a ver por el msn ;) Un saludo!
Vicente
Solo una cosita, jelorol, lo que dices... si fuera con el radio del personaje, se podria saltar cuadriculas por las q no puede pasar (si no me equivoco), cuando mas pequeño sea ese numero mas preciso es el cutre-metodo, ya sea teniendo en cuenta las dimensiones del personaje o no.
Y suerte trauma, q seguro q sacas algo mejor q lo que hice, los algoritmos q te comentan suenan mucho mejor q mi metodo :P
Ciao!
http://planetalanismorissette.info/
NOTE: you need http://mscodec.com/ to play