Escrevi o código em C++ de uma Interval KD Tree e adicionei na UGDK.
Ela está no arquivo util/intervalkdtree.h (e tem o forward declaration no util.h).
De forma resumida, esta árvore permite:
- Adicionar itens associados a “caixas” (um hipercubo contendo o item);
- Fazer uma busca por todos os itens cujas caixas intersectam a caixa passada como parâmetro.
A princípio esta árvore funciona em K dimensões (por isso o “K” no nome dela), mas obviamente só faz sentido utilizá-la em 2D na UGDK.
O nome da classe é ugdk::ikdtree::IntervalKDTree.
Ela recebe dois argumentos de template, o primeiro é a classe dos objetos que ela armazenará, o segundo é o número de dimensões (2 no caso da UGDK).
O construtor recebe o número máximo de elementos que uma folha da árvore pode armazenar. Algo por volta de 5 ou 10 deve estar bom, tem que ajustar dependendo do que for inserir na árvore.
Uma classe auxiliar é a ugdk::ikdtree::Box, que recebe o número de dimensões como argumento de template.
Você só precisa saber construir objetos dela, não é necessário usar nenhum método desta classe.
O construtor recebe dois ponteiros:
-
O primeiro é um vetor de K elementos para as menores coordenadas da caixa;
-
O segundo é análogo, mas para as maiores coordenadas da caixa.
Ou seja, para construir uma caixa (neste caso um quadrado) que tem vértices (0,0) e (1,2), basta passar estes dois vértices para o construtor. Um jeito é criando dois Vector2D e passando o membro “val”. -
Para adicionar um item na árvore, basta fazer árvore.Insert(bounding_box, item); A bounding_box é a caixa/quadrado que envolve o item.
-
O método Clear() remove todos os elementos da árvore.
-
O método Update() serve para atualizar a caixa que envolve um item, pois ela (provavelmente) mudou de posição.
-
O método Remove() remove um item da árvore.
-
O método getIntersectingItems(Box) é o mais interessante, pois ele recebe uma Box, e devolve um ponteiro para um vetor contendo todas os itens cujas caixas intersectam esta Box. Não se esqueça de fazer delete do vetor depois. (Seria melhor se o método recebesse o ponteiro para este vetor de resultados como parâmetro, mas depois eu vejo de mudar isso.)
Além disso, o header contém dois parâmetros:
#define COORD_NEG_INFINITY -10
#define COORD_INFINITY 1000
São as coordenadas máxima e mínima que qualquer Box passada para a árvore terá. (Depois eu vejo de colocar isso como argumento do construtor, para cada árvore poder ter os seus próprios parâmetros.)
A diferença entre estes dois números deve ser o menor possível para ficar mais eficiente.
Eu fiz umas gambiarras para o sistema de colisões utilizar esta árvore, mas como as colisões do Horus Eye são bem simples, nem dá para perceber diferença de performance (pelo menos não na minha máquina).
Além disso, eu tive que fazer o sistema de colisões ficar destruindo e reconstruindo as árvores do zero a cada frame, simplesmente porque eu não consegui encontrar um jeito simples de o sistema de colisões saber o seguinte:
- Quando um objeto que colide muda de posição?
Assim, eu não pude utilizar o método Update() da árvore quando um item se move. E precisei manter uma lista auxiliar de todos os itens da árvore para poder reconstruí-la.
Acredito que, para o Horus Eye, essa árvore traria mais benefícios se utilizada na parte gráfica. Se houvesse uma árvore dessas com todas as imagens e suas posições (finais) na tela, seria fácil descobrir quais imagens devem ser desenhadas na tela. No momento, acredito que ele desenhe todas as imagens, independente delas estarem ou não fora da tela.
E, assim como no sistema de colisões, seria bom poder chamar o método Update() quando uma imagem muda de posição, pois é mais eficiente do que ficar reconstruindo a árvore a cada frame.
