Imaginemos que nuestro juego tiene cientos de agentes desplazándose por el mundo virtual del mismo, y debemos comprovar si están consiguiendo colisionar con el agente que representa el jugador… ¿Cómo lo haríamos? La opción más fácil es comprovar si el bounding de cada uno de estos enemigos colisiona con el bounding del jugador… pero esto podría ser costoso, refiriéndonos al rendimiento. Una forma más óptima de hacerlo es descomponer el espacio, lo cual consiste en testear las colisiones entre objetos que se encuentren en la misma zona del espacio.
De descomposiciones del espacio existen los siguientes tipos (hay variantes… pero estos son los principales):
- Octrees
- Rejilla de vóxeles
Ambas soluciones son buenas, pero hay que tener cuidado en su uso. En este artículo veremos específicamente la rejilla de vóxeles.
Rejilla de Vóxeles
La definición pura y dura de voxel lo describe como un elemento volumétrico dentro de una rejilla imaginaria en el espacio tridimensional (la imagen de debajo es muy aclaradora en este sentido). Esto ya nos indica como vamos a relacionar esto con la detección de colisiones… nuestros objetos en el espacio 3D estarán virtualmente dentro de un voxel u otro, y sólo procederemos a testear la colisión en el caso en el que dos objetos se encuentren en el mismo voxel. ¿Parecido con el Quadtree? Bastante, la diferencia está en que aquí no hay voxels anidados…
Es mas, en la imagen previa, vemos una «montaña» de voxels, pero nosotros podríamos considerar que sólo tenemos un nivel de voxels, con lo cual en este caso la comprovación de si dos objetos se encuentran en el mismo voxel resulta trivial. Más que esa montaña de voxels, pasaríamos a tener lo siguiente:
Eso es «trampear» un poco con el concepto de Voxel, lo se, pero los programadores somos así 😛 El resultado es que los puntos rojos son los objetos que estarían en el espacio tridimensional vistos desde arriba, y el punto verde sería el agente del jugador. Si dividimos la pantalla en estos «voxels», sólo será necesario testear una colisión! Como tantas otras veces, comentar que obviamente esta solución no es exclusiva para XNA, el algoritmo nos servirá para cualquier tecnología.
Implementación en XNA
Lo que a mi me gusta es que las cosas que hago sean fáciles de debugar, de modo que si hay algún bug o problema, encontrar la solución sea rápido. Como hemos dicho vamos a trabajar con una descomposición del espacio, pues qué mejor que «pintar» esa descomposición en pantalla. Esto lo haremos trabajando con primitivas (dibujaremos las líneas de esta descomposición). Para hacer esto utilizaremos la siguiente clase Grid:
Esta clase ha sido creada a partir de una modificación de un código existente en la web del Creators Club. Con esto ya tendremos la «rejilla» pintada por pantalla. El siguiente paso interesante tambien para debugar, sería mostrar en la pantalla en qué parte de esta descomposición se encuentra el agente u objeto que representa el jugador. Esto lo haremos con el siguiente método, el «cálculo» es muy sencillo y rápido como se ve:
private Point GetNumCelda(Vector3 posicionObjeto)
{
Point numCelda;
numCelda = new Point((int)posicionObjeto.X / anchoCelda, (int)posicionObjeto.Z / anchoCelda);
return numCelda;
}
Además, pondremos un agente en la pantalla de forma que pueda moverlo el jugador, esto lo haremos con el código que venimos utilizando en los artículos previos (no volveré a escribirlo para no repetirme). El resultado de la ejecución es el siguiente:
Nota: En este ejemplo la descomposición se ha hecho en celdas muy pequeñas, en un videojuego las celdas podrían y deberían ser más grandes, en proporción con el tamaño de nuestros agentes, la cantidad de objetos cuyas colisiones queramos testear, etc.
Tengamos en cuenta, que para saber en qué celda se encuentra el agente, sólo esamos la posición de su «centro», no sus dimensiones. Esto quiere decir que nuestro objeto agente podría estar enmedio de dos celdas y por lo tanto podríamos considerar que se encuentra en dos celdas, y no en una, incluso en cuatro, si se encuentra en una esquina de una celda. Para no complicar la obtención de la información de en qué celdas estamos, lo que haremos es comprobar la colisión con la celda «centro» y todas las adyacentes, de la forma que indica el dibujo siguiente:
Un momento, se nos olvida algo… contra qué vamos a comprobar las colisiones? Necesitamos uno o varios modelos, que a ser posible se muevan por la pantalla, para hacerlo. Había pensado en el modelo siguiente:
Además del modelo en formato DirectX (.X) necesitaremos almacenar este en algun sitio, una buena forma de hacerlo es en una lista genérica, en la clase Game:
List<ExtendedModel> patos;
Después sólo tenemos que inicializarlos, con posiciones distintas y direcciones algo aleatorias, esto lo haremos en el método LoadContent() de la clase Game:
patos = new List<ExtendedModel>();
Model modeloPato = Content.Load<Model>(@»Modelspato»);
for (int a = 0; a <= 5; a++)
for (int i = 0; i <= 5; i++)
{
ExtendedModel m1 = new ExtendedModel(GraphicsDevice);
m1.position = new Vector3(anchoCelda * i – 500 * a, 30.0f, i * 200.0f – 400 * a);
m1.model = modeloPato;
m1.scale = 300.0f;
m1.altura = 40;
m1.anchura = 40;
m1.speed.X += (float)rnd.Next(10) / 10;
m1.speed.Z += (float)rnd.Next(10) / 10;
patos.Add(m1);
}
Y creo que aquí se hace necesario explicar mínimamente la clase ExtendedModel (que no es parte del Framework de XNA obviamente).
Bueno, no tiene ningún secreto, esta clase contiene principalmente un modelo de XNA del tipo Model, y lo que hace es dibujarlo por pantalla mediante el método Draw. Además le he puesto algunas propiedades como posición, velocidad, escala, etc, que me son de ayuda para hacer ejemplos rápidos de XNA, no diría que sea un modelo de codificación o diseño óptimo para un juego, así que ojo con su uso 😉
Ahora, sólo nos queda darle un poco de lógica a nuestro «juego», en el método Update() de la clase Game, pondremos el código siguiente:
// Boundingbox del agente
agente.bounding = new BoundingSphere(new Vector3(agente.position.X, agente.position.Y, agente.position.Z), agente.anchura);
// Miro donde está el agente
Point numCelda = GetNumCelda(this.agente.position);
// Lógica del pato
foreach (ExtendedModel pato in patos)
{
pato.bounding = new BoundingSphere(new Vector3(pato.position.X, pato.position.Y * 2, pato.position.Z), pato.anchura);
pato.rotation = pato.rotation + new Vector3(0.0f, 0.05f, 0.0f);
pato.position += pato.speed;
if (pato.position.Z < -600 || pato.position.Z > 600)
pato.speed.Z *= -1;
if (pato.position.X < -600 || pato.position.X > 600)
pato.speed.X *= -1;
pato.position.X = MathHelper.Clamp(pato.position.X, -600, 600);
pato.position.Z = MathHelper.Clamp(pato.position.Z, -600, 600);
// Inicialmente asumo que no hay colisión
pato.boundingColor = Color.Purple;
Point celdaPato = GetNumCelda(pato.position);
// Miro si el pato está en la misma zona del espacio que el agente
if (celdaPato == new Point(numCelda.X – 1, numCelda.Y – 1)
|| celdaPato == new Point(numCelda.X, numCelda.Y – 1)
|| celdaPato == new Point(numCelda.X + 1, numCelda.Y – 1)
|| celdaPato == new Point(numCelda.X – 1, numCelda.Y)
|| celdaPato == new Point(numCelda.X, numCelda.Y)
|| celdaPato == new Point(numCelda.X + 1, numCelda.Y)
|| celdaPato == new Point(numCelda.X – 1, numCelda.Y + 1)
|| celdaPato == new Point(numCelda.X, numCelda.Y + 1)
|| celdaPato == new Point(numCelda.X + 1, numCelda.Y + 1))
{
// Lo está? pues perfecto, comprovamos la colisión
if (pato.bounding.Intersects(agente.bounding))
pato.boundingColor = Color.Red; // En este caso, simplemente hacemos que el boundingSphere del pato se pinte en rojo
}
Una de las cosas que me preocupa en esta implementación es ese If, bastante «gordo», y que además se ejecuta un montón de veces por segundo. Para que esta implementación le salga «rentable» a nuestro procesador, el «mundo 3D» cuyas colisiones queremos comprobar tiene que ser bastante grande y contener bastantes elementos a comprobar.
Os dejo con el resultado de la ejecución, y como siempre, el código.
[View:http://www.youtube.com/watch?v=n4Fx7ozxpWQ:550:0]
Llevar el ejemplo «más allá»
Lo interesante sería ahora dibujar otra grid verticalmente, y tener en cuenta la dimensión Y a la hora de calcular las celdas adyacentes, esto sería implementando el concepto descomposición del espacio voxels más «real».
