Optimización Pathfinding

[vincent]

 vamos a poner un dibujo a ver si se vé mejor....



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

[gdl]

 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.

[jelorol]

 
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)

[trauma]

 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)  

[zupervaca]

 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

[trauma]

 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!

[Vicente]

 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

[[Vil]]

 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!

[Teenpo]

http://planetalanismorissette.info/

NOTE: you need http://mscodec.com/ to play