No meu jogo, estou no ponto em que preciso rastrear todas as unidades do mundo para poder fazer verificações de vizinhos mais próximos em combate. Este é um jogo semelhante ao RTS, com potencialmente milhares de pequenas unidades automatizadas em movimento.
Eu estive olhando para KD-Trees e Quadtrees (especialmente Point Quadtrees). Ainda estou tentando aprender os detalhes de como eles funcionam, mas até agora os Point Quadtrees estão fazendo mais sentido para mim. No entanto, estou tendo a impressão de que as árvores KD são mais rápidas de pesquisar, o que é importante com o número de pontos que terei na árvore.
Por outro lado, no meu caso, vou rastrear um grande número de unidades que estão sempre em movimento. De quadro a quadro, suas posições sempre serão diferentes. Aparentemente, os quadtrees são mais rápidos em reequilibrar que as KD-Trees, mas não sei se isso é aplicável quando você está reequilibrando todos os pontos da árvore.
Gostaria de saber se seria melhor, neste caso, apenas desfazer a árvore em cada quadro e reconstruí-lo do zero, em vez de tentar reequilibrar todos os pontos da árvore? Se um Quadtree é mais rápido para reequilibrar, isso também significa que é mais rápido construir do zero? Nesse caso, isso pode ser mais importante para o desempenho do que a velocidade de pesquisa do KD-Tree, dependendo de quanto custa criar a árvore, mas eu não sei ...
As sugestões de Lærne são ótimas, mas eu também sugeriria uma árvore de volume delimitador dinâmico de AABBs. Conceitualmente, a árvore de volume delimitador dinâmico mantém uma árvore de nós equilibrada que pode ser consultada a qualquer momento para elementos próximos, passando em um AABB e recuperando um par sobreposto. A árvore não é reconstruída a cada quadro. Em vez disso, o AABB de cada nó é levemente inflado quando colocado na árvore, e a árvore é reconstruída apenas quando o AABB real do nó não está mais contido no AABB inflado. Eu o uso no meu mecanismo de física e funciona muito bem.
O código fonte do Box2D possui uma ótima implementação.
https://github.com/erincatto/Box2D/blob/master/Box2D/Box2D/Collision/b2DynamicTree.h
Aqui está uma boa revisão de sua implementação:
http://www.randygaul.net/2013/08/06/dynamic-aabb-tree/
fonte