Teoría de colisiones 2D: QuadTree

En el artículo anterior repasamos los conceptos básicos de las colisiones 2D, ahora vamos a entrar en materia y vamos a ver como optimizar los cálculos en el mundo de nuestro juego.

Uno de los principales problemas del sistema de colisiones es que en cada interacción tenemos que comprobar si cada objeto está colisionando con el resto de objetos de nuestro juego. Por ejemplo si tenemos 100 objetos en nuestro juegos nos daría 100 x 100 = 10000 comprobaciones de colisión en en cada bucle de nuestro juego, lo que es una barbaridad para 100 objetos. Vamos a ver como podemos optimizar esto.

Imagina que tenemos un escenario como el siguiente, donde los puntos azules son objetos de nuestro mundo.

Digamos que los objetos se mueven a una velocidad de unos 10px por segundo. Quizás necesitemos entonces comparar si los objetos de la esquina superior izquierda colisionan entre ellos, pero es totalmente innecesario comprobar si están ambos colisionando con el objeto de la esquina inferior derecha, entonces ¿Cómo lo hacemos para descartar las colisiones que obviamente sabemos que no se van a prouducir? La solución es el clásico divide y vencerás.

Quadtrees

Los Quadtrees son un tipo de estructura de datos en el que cada nodo tiene a su vez cuatro nodos hijos, sería algo similar a un árbol binario, pero en vez de dos ramas con cuatro ramas.

Esto se puede usar para separar nuestro escenario en cuatro áreas iguales recursivamente, vamos a ver el Quadtree de la siguiente manera.

Ahora tendríamos un nodo padre que representa el escenario completo y cuatro nodos hijo que lo subdividen en cuatro partes iguales. Ahora lo que debemos hacer es decirle a nuestro objeto algo como: comprueba sólo las colisiones con los objetos que están en tu cuadrante.

Con esto ya tendríamos nuestros dos objetos superiores en un único cuadrante y evitaríamos comprobar colisiones con el objeto de la esquina inferior derecha.

Añadiendo profundidad

Ahora imaginemos que añadimos unos cuantos objetos más a nuestro mundo, tal que nos queda así.

Está claro que el cuadrante superior izquierdo empieza a tener demasiados objetos y se empiezan a hacer demasiado costoso comprobar todas las colisiones que suceden en él. Así que la solución es subdividir a su vez este cuadrante en otro nodo Quadtree.

De esta manera volvemos a tener un número pequeño de nodos en cada cuadrante que se hace mucho más manejable.

¿A partir de cuantos objetos subdivido un cuadrante?

Esta pregunta dependerá del tamaño del mapa y de los objetos, pero sería recomendable no tener mas de 10 objetos por cuadrante que yo son 10 x 10 = 100 comprobaciones. Lo mismo con el número de subdivisiones, sería bueno establecer un número máximo en el que un Quadtree se pueda subdividir en otro Quadtree, como antes todo dependerá del tamaño del mapa de nuestro juego, pero a partir de 5 niveles ya puede empezar a ser excesivo.

Caso especial

Vamos a fijarnos en el objeto marcado en rojo de nuestra representación:

Estos objetos que quedan sobre las líneas no los metemos en ninguno de los cuadrantes hijos sino que lo dejamos en el cuadrante padre. Por tanto cada cuadrante deberá comprobar si sus objetos colisionan con los objetos de sus nodos hijos. Si un Quadtree que no sea un nodo hoja contiene un objeto podemos decir que dicho objeto se encuentra en una de las líneas que lo subdivide.

Esto es todo con esta pequeña implementación conseguiremos ahorrarnos un montón de cálculos y comprobaciones y haremos nuestro juego más fluido. Os dejo un vídeo con un ejemplo implementado en SFML.

Vídeo | Implentación de Quadtrees en SFML