Quando um quadtree é preferível ao hash espacial?

Estou fazendo um jogo de plataformas 2D com muitos objetos ao mesmo tempo. Eles são todos colisão AABB detectada. Tentei pela primeira vez um quadtree para diminuir o número de objetos a serem verificados, tentei algumas configurações diferentes, mas não foi tão eficaz quanto eu precisava. Eu implementei um hash espacial e é muito mais eficiente, o número de objetos a serem verificados para cada colisão caiu drasticamente.

Existe um caso em que a detecção de colisão 2D usando um quadtree é preferível ao hash espacial? De acordo com meus testes, parece que o hash espacial sempre acaba com menos objetos a serem testados quanto à colisão?

Eu não terminei o tempo dos algoritmos, mas o hash é simplesmente muito caro ou difícil de implementar quando você está, por exemplo, codificando em C? É interessante notar que estou escrevendo o jogo em javascript, onde você tem o hash "de graça".

Aqui está a comparação, eu esqueci alguma coisa? http://zufallsgenerator.github.io/2014/01/26/visually-comparing-algorithms/

A principal vantagem de uma árvore quádrupla é que ela permite descartar grupos inteiros de baldes de consideração muito rapidamente.

Por exemplo, vamos supor que eu tenho um quad tree com seis níveis. No nível mais baixo, são 32x32 caixas; 1024 caixas que compreendem esse nível inferior e mais detalhado. Para comparação, também consideraremos um "hash espacial" - uma grade plana que também contém caixas 32x32, 1024 caixas no total. (a árvore quádrupla tem mais de 1024 caixas no total, pois também contém caixas maiores nos níveis mais altos)

Vamos supor que não haja objetos colidíveis no sistema - todas as caixas de nossa árvore quádrupla e nossa grade plana estão completamente vazias.

Se você estiver testando as colisões de algo grande o suficiente para que sua caixa delimitadora cruze todas essas caixas e estiver usando uma grade plana, será necessário verificar cada uma dessas 1024 caixas para ver se há alguma coisa na caixa. eles.

Mas se você estiver usando uma árvore quádrupla aninhada, o nível mais alto poderá dizer que não há outros objetos no sistema e, portanto, você só precisará olhar para aquela única caixa para saber que não encontrará colisões mais fundo na árvore - você pode parar de testar imediatamente.

Da mesma forma, se os objetos existirem apenas em determinadas regiões da árvore quádrupla, a árvore quádrupla naturalmente guiará sua pesquisa por apenas caixas potencialmente relevantes, enquanto a grade exige que você marque todas as caixas cruzadas, porque você não tem como saber antecipadamente quais quadrados da grade terão objetos neles. Se grande parte de sua árvore quádrupla estiver vazia e você estiver fazendo consultas grandes e complicadas (por exemplo, grandes furos de câmera em vez de retângulos pequenos e simples), você poderá descobrir que está iterando em muito menos caixas no total, se fizer o seu testa algo usando uma estrutura em árvore, em vez de uma grade plana. E isso pode fazer uma grande diferença.

Tudo isso não implica que uma estrutura em árvore seja sempre a escolha certa, é claro. As grades planas são ideais para a situação que você tem no seu exemplo - nuvens densas de objetos praticamente espalhadas uniformemente por todo o mundo, e estamos fazendo testes de colisão simples e baratos. Absolutamente uma grade provavelmente será a abordagem ideal nesse caso!