lunes, febrero 27, 2006

 

Pensando en n-dimensiones

La mayoría de las veces la gente cuando se pone a programar juegos 2d o 3d se centran exactamente en el numero de dimensiones que tendrá ese juego, esto en mi humilde opinión es una forma de pensar totalmente incorrecta, el problema de pensar en 2d o 3d es que creamos funciones para este tipo de dimensiones y no pensamos en la verdadera optimización de pensar en n-dimensiones.
¿Que es pensar en n-dimensiones? Pensar en n-dimensiones es tener claro el concepto de que es una dimensión, para explicar lo que es una dimensión lo haré de la forma mas sencilla que conozco, una dimensión no es mas que un espacio comprendido entre dos puntos que se llaman -infinito y +infinito, en un ordenador lamentablemente infinito no existe (salvo en bucles), la mayoría de las veces las dimensiones son tratadas de -float +float, es decir, de 1.17549e-38 hasta 3.40282e+38, teniendo claro esto, podemos decir que todas las dimensiones se comportan de la misma manera ya que solo definen la posición en un espacio (algunos lo entenderéis mejor si lo llamara vector).
Un ejemplo practico de como pensar en n-dimensiones es la clásica función para comprobar si un cubo definido por dos puntos (mínimo y máximo) esta dentro de otro o por lo menos esta parcialmente dentro de otro, la mayoría de las personas harán la clásica rutina de mirar si uno de los dos puntos del cubo A esta dentro de los puntos del cubo B, esto en mi opinión es un error muy gordo ya que solo se ha pensado en 3d y no en n-dimensiones, partimos de que tenemos las siguientes estructuras:
struct Vector
{
float x, y, z;
}
struct Caja
{
Vector min, max;
}

El código pensado para 3d seria algo así:
bool Colision3D( Caja caja1, Caja caja2 )
{
if( PuntoDentro3D(caja1, caja2.min) || PuntoDentro(caja1, caja2.max) )
{
return true;
}
return false;
}
bool PuntoDentro3D( Caja caja1, Vector punto )
{
if( punto.x > caja1.min.x && punto.x < caja1.max.x &&
punto.y > caja1.min.y && punto.y < caja1.max.y &&
punto.z > caja1.min.z && punto.z < caja1.max.z )
{
return true;
}
return false;
}

Vemos que comprobamos que uno de los dos puntos de la caja B se encuentre dentro de la caja A, esto genera 12 comprobaciones, es decir 6 por cada punto, ¿que pasaría si hiciéramos esta función pensando en n-dimensiones? Antes de dar la solución es mejor explicar paso a paso como llegar a ella.
Lo primero es quitar las dimensiones Y y Z del tablero de juego, es decir, nos quedamos solo con la dimensión X que se comporta de la misma manera que Y y Z, ahora pensamos lo siguiente, ¿que debemos de hacer para comprobar si un valor se comprende entre otros dos, por ejemplo entre el 10 y el 20?
if( valor > 10 && valor < 20 ) return true;

Si el valor es mayor a 10 y el valor es menor a 20 es que valor esta entre 10 y 20 lógicamente, ahora un poco mas complicado, ¿que hacemos para saber si min y max se comprende entre 10 y 20 o esta parcialmente dentro?
if( max > 10 && min < 20 ) return true;

¿Ein? ¿y como es que con las mismas comprobaciones logramos esto? Pues muy sencillo, debemos de mirar todos los casos posibles, si máximo es menor a 10, significa que min es menor a 10 ya que max es mayor siempre que min, si max es mayor a 10 o 20 significa que y min y max pueden estar dentro de 10 o 20, si min es mayor a 20 significa que esta fuera del rango de 10 y 20 ya que max siempre es mayor a min, si es menor significa que puede estar dentro del rango de 10 y 20, entonces llegamos a la conclusión de que si max es mayor a 10 y min es menor a 20 esta dentro, también se podría ver al revés, decir que si min es mayor a 20 o max es menor 10 no estaría dentro.
if( min > 20 || max < 10 ) return false;

Teniendo esta afirmación en la dimensión X podemos decir que todas las demás dimensiones la cumplen ya que se comportan igual, con lo que comprobar un cubo con valor máximo y mínimo dentro de otro seria de esta manera:
bool ColisionNDimensiones( Caja caja, Caja caja2 )
{
if( caja1.min.x < caja2.max.x && caja1.max.x > caja2.min.x &&
caja1.min.y < caja2.max.y && caja1.max.y > caja2.min.y &&
caja1.min.z < caja2.max.z && caja1.max.z > caja2.min.z )
{
return true;
}
return false;
}

Nos hemos ahorrado 6 comprobaciones, esta entre otras es una de las ventajas de pensar en n-dimensiones, ¿que ocurría si quisiéramos crear comprobaciones con cubos de mas dimensiones que 3, por ejemplo 5? Seria agregar comprobaciones, algo así:
bool ColisionNDimensiones( Caja caja, Caja caja2 )
{
if( caja1.min.x < caja2.max.x && caja1.max.x > caja2.min.x &&
caja1.min.y < caja2.max.y && caja1.max.y > caja2.min.y &&
caja1.min.z < caja2.max.z && caja1.max.z > caja2.min.y &&
caja1.min.a < caja2.max.a && caja1.max.a > caja2.min.a &&
caja1.min.b < caja2.max.b && caja1.max.b > caja2.min.b
)
{
return true;
}
return false;
}

Como veis mientras mas dimensiones mas comprobaciones nos ahorramos.
Espero que ahora estéis todos pensando en n-dimensiones :)

Comments:
je,je,je.. muy interesante... intentaremos aplicarlo ;) :) Saludoos!
 
Publicar un comentario



<< Home

This page is powered by Blogger. Isn't yours?