Ir al contenido principal

Quadtrees

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.

Comentarios

Entradas populares de este blog

Un poco de nostalgia: juegos retro

El Laberinto del Saber es un juego desarrollaod en Cuba a finales de los 80 o algo así, para MS-DOS. Aquí pueden verlo en acción:

Desde hace un buen tiempo que quiero hacer un remake moderno orientado principalmente a plataformas móviles, al principio lo intenté con SDL 2, pero luego decidí usar un motor decente. Entre Godot y Unity3d me decanté por el último, para no invertir tiempo en aprender una herramienta que no me serviría para hacer más juegos.
Sin embargo, el proyecto ya acumula unos seis meses de atraso por diversas razones, y ni siquiera tengo una imagen para mostrar. Así queni hablar de fecha de lanzamiento.

Unity 5.4 está aquí

Y no trae la herramienta de edición de cinemáticas, como esperaba. Al menos, no se hace referencia a ella en las notas de lanzamiento.
Justamente acabo de lograr descargar la 5.3.5, la cual ha sido bastante decepcionante. El MonoDevelop que incluye ha dejado de sugerir el autocompletado para los miembros de algunas clases (me queda por definir cuándo lo hace y cuándo no) y además el precalculado de la iluminación global me suelta una docena de advertencias, aparte de que me ha obligado a recalcular las luces dos veces. Y eso toma bastante tiempo.
Aún no sé si podré echarle el guante a la 5.4, y tampoco es que tenga mucho interés. Aunque supongo que peor no va a ponerse, y quizás hasta se arreglen las cosas.
Por suerte, no estoy programando mucho. Las últimas páginas de la cuarta novela me tienen  bastante ocupado, y también le estoy echando un vistazo a la historia del juego. Sin embargo, eso no será para siempre, en algún momento de esta semana tengo que seguir puliendo el sistema …

Leyendo a Sapkowsky

Este es uno de mis escritores favoritos y es lamentable que haya tan poco de él en español. Aunque hay que reconocer que Andrzej Sapkowsky no ha sido tan prolífico.
A Sapkowsky le basta con su saga de Geralt de Rivia para ser una figura de renombre en la literatura fantástica. La fama de los juegos basados en el personaje del brujo Geralt, me parece, no le han acarreado una fama enorme, porque muchos olvidan (o simplemente no se interesan en averiguar) que el Wiedźmin no fue creado por CD Projekt RED.Por suerte, como les decía, entre los lectores ya Sapkowsky era un referente aún antes de que salieran los juegos.
Tenía entendido que estaba trabajando otra serie de libros, basados en las Guerras Husitas, así que hace poco decidí buscar si ya estaban disponibles en español. Y resulta, que además de los dos libros de dicha saga, me encontré Víbora, un tercero completamente distinto, ambientado en Afganistán durante la invasión soviética.
No obstante, no es de eso que quiero hablarles, sin…