Trabajando en mi juego, estoy en el punto donde necesito rastrear todas las unidades del mundo para poder hacer controles de combate del vecino más cercano. Este es un juego similar a RTS, con potencialmente miles de pequeñas unidades automatizadas moviéndose.
He estado buscando en KD-Trees y Quadtrees (especialmente Point Quadtrees). Todavía estoy tratando de aprender los detalles de cómo funcionan, pero hasta ahora Point Quadtrees tiene más sentido para mí. Sin embargo, tengo la impresión de que los árboles KD son más rápidos de buscar, lo cual es importante con la cantidad de puntos que tendré en el árbol.
Por otro lado, en mi caso, voy a estar rastreando una gran cantidad de unidades que siempre están en movimiento. De cuadro a cuadro, sus posiciones siempre serán diferentes. Los quadtrees son aparentemente más rápidos para reequilibrar que KD-Trees, pero no sé si eso es aplicable cuando se reequilibra cada punto del árbol.
Me pregunto si sería mejor en este caso simplemente desechar el árbol de cada cuadro y reconstruirlo desde cero, en lugar de tratar de reequilibrar cada punto del árbol. Si un Quadtree es más rápido para reequilibrar, ¿eso también significa que es más rápido construir desde cero? Si es así, eso podría ser más importante para el rendimiento que la velocidad de búsqueda del KD-Tree, dependiendo de la carga que supone crear el árbol, pero no sé ...
Las sugerencias de Lærne son geniales, pero también sugeriría un árbol de volumen dinámico delimitador de AABB. Conceptualmente, el árbol de volumen delimitador dinámico mantiene un árbol equilibrado de nodos que pueden consultarse en cualquier momento para elementos cercanos al pasar un AABB y recuperar un par superpuesto. El árbol no se reconstruye en cada cuadro. En cambio, el AABB de cada nodo se infla ligeramente cuando se coloca en el árbol, y el árbol solo se reconstruye cuando el AABB inflado ya no contiene el AABB real del nodo. Lo uso en mi motor de física y funciona muy bien.
El código fuente de Box2D tiene una gran implementación.
https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h
Aquí hay una buena revisión de su implementación:
http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/
fuente