Problemas geometricos

[DVM]

                                Hola a todos!!

He estado informandome sobre pathfinding, y en la mayoria de los documentos, se utiliza el metodo de un bitmap con dos colores (pisable, no pisable). Pero observando algunos juegos (sobre todo aventuras graficas), he visto que utilizan cuadrilateros. La forma en que los utilizan es la siguiente, definen los cuadrilateros por sus cuatro puntos y todo lo que este en los cuadrilateros es pisable. Por ejemplo:

(0,0)---------------Pantalla-----------------------
|                 a4
|                /
|              //
|            / /     b4
|       b4|/--/-------/c4
|        /|  /       /    
|      /  | /       /     /c3
| a1 /    |/   B   /  C  /
|  /   A  /b1    /c1  /
|  _____/      /    /
|  a2   a3     /    /c2
|             /b2

He dibujado 3 cuadrilateros A (a1,a2,a3,a4), B (b1,b2,b3,b4), C (c1,c2,c3,c4) (espero que se vean bien). Bien, pues los puntos pisables, son aquellos que están dentro de cualquier cuadrilatero. Aqui es donde me surgen las dudas:

- Si yo selecciono un punto de la pantalla de coordenadas (x,y) con el raton, ¿como puedo saber si ese punto esta en un cuadrilatero o no?. Si fueran rectangulos, o cuadrados, es muy sencillo, pero con cuadrilateros, no consigo solucionar el problema.

- Si un un punto (x,y) no esta dentro de un cuadrilatero, ¿como se localiza el cuadrilatero mas cercano?.

- En cuanto a aplicar el pathfinding, cuando utilizas un bitmap bicolor, ya tienes todos los puntos para realizar el pathfindig, pero con cuadrilateros, ¿Tendrias que comprobar si cada punto esta o no en uno de los cuadrilateros?. Si esto fuera asi, el costo del pathfinding sería muy alto, a no ser que la funcion para comprobar si un punto esta en un cuadrilatero fuera de costo minimo.

Existe otro sistema similar, pero en vez de utilizar cuadrilateros, utiliza triangulos. Y me surgen las mismas dudas.

Espero que podais ayudarme. Y muchas gracias de antemano.

[ Este Mensaje fue editado por: DVM el 2002-08-29 19:20 ]

[ Este Mensaje fue editado por: DVM el 2002-08-29 19:21 ]                                

[DVM]

                                Hola a todos de nuevo.
¿Nadie puede echarme una mano?, no necesito codigo, ni nada de eso, solo un poco de orientacion. Por favor, si sabeis algo relacionado con la duda, o teneis alguna idea os agradeceria muchisimo que me contestarais.                                

[synchrnzr]

                                No consigo descifrar tus preguntas. O las entiendo muy mal. Y eso que el ASCII art ha quedado de pelotas al pasarlo a HTML... :ojo:

Haré lo que pueda basándome en lo que creo que he entendido:

"- Si yo selecciono un punto de la pantalla de coordenadas (x,y) con el raton, ¿como puedo saber si ese punto esta en un cuadrilatero o no?. Si fueran rectangulos, o cuadrados, es muy sencillo, pero con cuadrilateros, no consigo solucionar el problema."

Supongo que te refieres a un cuadrilátero irregular con ángulos y lados distintos. El coste de saber si el punto está dentro puede ser bastante alto: no creo que un algoritmo de pathfinding vaya por ahí.

"- Si un un punto (x,y) no esta dentro de un cuadrilatero, ¿como se localiza el cuadrilatero mas cercano?"

Eso puede ser la leche ya... XDDD

"- En cuanto a aplicar el pathfinding, cuando utilizas un bitmap bicolor, ya tienes todos los puntos para realizar el pathfindig, pero con cuadrilateros, ¿Tendrias que comprobar si cada punto esta o no en uno de los cuadrilateros?. Si esto fuera asi, el costo del pathfinding sería muy alto, a no ser que la funcion para comprobar si un punto esta en un cuadrilatero fuera de costo minimo."

Eso creo que lo veo más claro. No, sólo tienes que comprobar si el punto (x,y) es de un color u otro. Si es del color del path, está dentro, si no, no...

"Existe otro sistema similar, pero en vez de utilizar cuadrilateros, utiliza triangulos. Y me surgen las mismas dudas."

Y te costará lo mismo que con cuadriláteros. Será mejor que mires bien cómo funcionan estos algoritmos que mencionas pq dudo que, si utilizan cuadriláteros y triángulos, necesiten calcular eso que preguntas.

Vaya, lo mio es el sonido, o sea que a lo mejor me equivoco de cabo a rabo (que nadie me pegue) pero yo lo he intentado... XDDD

Sync :guay:
                               

[NeLo]

                               

Y eso que el ASCII art ha quedado de pelotas al pasarlo a HTML... :ojo:

xDDDDDDDDDDDDDDDDDDDDDDDD
                               

[Frodrig]

                                Hola,

Tambien puedes investigar como funcionan otros motores de juegos para aventuras graficas, yo lo haria si tuviera que construir un sistema similar para asi aprender y sacar mis propias conclusiones.

Tienes el KKAG (http://kkag.sourceforge.net/), que es un proyecto español y creo que su autor escribe por estos lares y el AGAST, que es bastante majo tambien (http://agast.dyndns.org/agast/home.html).

Saludos.                                

[Malandrin]

                                Hola, te explico como funciona más o menos el sistema que conozco. El mapa se divide en sectores de cualquier número de lados (es obligatorio que los sectores sean convexos, para que dados dos puntos dentro del sector, se pueda ir de uno a otro sin salirse del propio sector), aunque tambien se puede dividir en cuadrados, rectangulos o lo que sea, pero los sectores dan mucha más versatilidad a la hora de crear el mapa. Para cada sector se le especifican unas caracteristicas, si es transitable o no, si es de sombra, etc, etc... Cada sector del mapa tiene información de los sectores adyacentes, luego para ir de un punto a otro simplemente se hace un pathfinding entre ambos puntos, desde el punto inicial se calcula el punto a la arista que une el sector origen con el adyacente, una vez en este sector se va al punto de la arista que comparte con el siguiente sector, y asin sucesivamente hasta llegar al final. Y más o menos esto es asin... un saludo.                                

[DVM]

                                Hola de nuevo!
Malandrin, ese es el metodo q mas o menos intuia, y creo que ya se un metodo para conocer si un punto está dentro de un cuadrilatero. Tambien imaginaba, que los cuadrilateros (o regiones) estarían almacenados de alguna forma para poder aplicar un pathfind a nivel de cuadrilatero. Un problema al que no encuentro una solucion muy adecuada es, controlar los puntos de paso de un cuadrilatero a otro. He pensado en definir yo mismo esos puntos de paso, pero lo ideal sería conocer la región de corte de un cuadrilatero con otro, o algo parecido ¿Sabes algo de esto?