Había mencionado hace un tiempo los quadtrees y dije que hablaría acerca de ellos y por qué son tan importantes a la hora de manejar listas de entidades. Según la wikipedia, un quadtree es una estructura de datos en forma de árbol en la que cada nodo puede tener hasta cuatro hijos. Se utilizan para particionar un espacio bidimensional subdividiéndolo recursivamente en cuatro cuadrantes o regiones. En este caso nos interesa su aplicación en indexación espacial, o dicho en lenguaje más claro, para determinar si dos puntos están cercanos entre sí.
Supongamos que tenemos un área o mapa de nuestro juego y comenzamos dividiéndolo en cuatro sectores:
A su vez, cada uno de estos sectores es subdividido otra vez:
y así sucesivamente (que para eso está la palabrita recursivo por ahí arriba), hasta que tenemos nuestro mapa dividido en regiones de tamaño X, cada una de las cuales es un nodo de nuestro árbol. Dadas tres entidades de nuestro juego, A, B y C, necesitamos notificar de cualquier cambio en alguna de ellas a sus vecinos. ¿Cómo encontrar las entidades cercanas sin recorrer toda la lista? Aquí es donde entran en escena los quadtrees. Como muestra la imagen siguiente, solo tendríamos que recorrer nuestro árbol y tomar todas las entidades que se encuentren en el mismo sector.
En el caso anterior, A y B son vecinos, están en el mismo sector, así que teóricamente deberíamos encontrarlos en el mismo nodo. Tal búsqueda debería además dejar fuera a C.
Así que, sin recorrer toda la lista de entidades, tenemos los vecinos de A.
Sin embargo, las cosas pueden complicarse, como podemos ver en este último dibujito:
No hay dudas de que este tío llamado D es tremendo inoportuno. Es vecino de B, ¡pero no está en el mismo cuadrante! Es como para mentarle a su progenitora. Resolver este problema lo dejo como ejercicio intelectual para el lector. O sea, que no tengo ni puta idea de cómo lidiar con él, a menos que cada cuadrante guarde un puntero adicional al cuadrante vecino.
Otro detalle, no sé cuánto CPU consuma la importantísima tarea de mantener el árbol organizado. Hay que recordar que cuando una entidad se desplaza, debe quedar en el nodo correcto.
Supongamos que tenemos un área o mapa de nuestro juego y comenzamos dividiéndolo en cuatro sectores:
A su vez, cada uno de estos sectores es subdividido otra vez:
y así sucesivamente (que para eso está la palabrita recursivo por ahí arriba), hasta que tenemos nuestro mapa dividido en regiones de tamaño X, cada una de las cuales es un nodo de nuestro árbol. Dadas tres entidades de nuestro juego, A, B y C, necesitamos notificar de cualquier cambio en alguna de ellas a sus vecinos. ¿Cómo encontrar las entidades cercanas sin recorrer toda la lista? Aquí es donde entran en escena los quadtrees. Como muestra la imagen siguiente, solo tendríamos que recorrer nuestro árbol y tomar todas las entidades que se encuentren en el mismo sector.
En el caso anterior, A y B son vecinos, están en el mismo sector, así que teóricamente deberíamos encontrarlos en el mismo nodo. Tal búsqueda debería además dejar fuera a C.Así que, sin recorrer toda la lista de entidades, tenemos los vecinos de A.
Sin embargo, las cosas pueden complicarse, como podemos ver en este último dibujito:
No hay dudas de que este tío llamado D es tremendo inoportuno. Es vecino de B, ¡pero no está en el mismo cuadrante! Es como para mentarle a su progenitora. Resolver este problema lo dejo como ejercicio intelectual para el lector. O sea, que no tengo ni puta idea de cómo lidiar con él, a menos que cada cuadrante guarde un puntero adicional al cuadrante vecino.Otro detalle, no sé cuánto CPU consuma la importantísima tarea de mantener el árbol organizado. Hay que recordar que cuando una entidad se desplaza, debe quedar en el nodo correcto.
Comentarios
Publicar un comentario