Colisão baseada em quad-trees / grid - colocando a lógica em ação

Primeiro de tudo, eu só tenho escrito minha própria lógica de jogo por um tempo, então peço desculpas se isso pode parecer simples.

Eu tenho lido muito sobre árvores quad e detecção de colisão baseada em grade. Eu entendo a lógica - basicamente não verifique se há colisão, a menos que os objetos estejam perto basicamente. Mas nunca é mencionado como o realmente executa isso.

Eu tenho alguns métodos possíveis na minha cabeça, mas não sei qual é o melhor

Teste geral de colisão - sem otimização

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

armazenar vizinhos (método 1) Mas e se quisermos otimizar as colisões para verificar apenas os objetos que estão próximos. Ainda executamos todos os objetos ou criamos uma matriz com objetos próximos para verificar?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

repetir todos os objetos, mas verificar apenas os vizinhos quanto à colisão (método 3) A outra possibilidade é que ainda percorremos tudo, mas verificamos se os objetos estão próximos antes de testar a colisão.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Armazenar objetos em dados de bloco (método 3) O uso de um sistema baseado em bloco permite outra opção; Armazene os objetos que estão em um bloco específico nos próprios dados do bloco. Verifique para ver em qual bloco o objeto está, os blocos ao redor contêm objetos com os quais podem colidir:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Eu sempre tento olhar o mundo real como um exemplo. Se eu quisesse comparar itens da mesma cor, pareceria ilógico verificar todos os itens, mesmo que não correspondam à cor (método 2, verifique cada item). Provavelmente eu coletaria os itens da mesma cor (objetos próximos) e os verificaria (método 1), em vez de verificar tudo.

Esta não é uma comparação adequada, pois os itens na verificação de colisão estão em constante movimento, de modo que o pedido se confunde. Isso está me confundindo.

Seria mais eficiente verificar cada item, removendo assim a tensão de continuar gerando uma matriz de vizinhos.

Ou é mais eficiente encontrar vizinhos e não ter que percorrer tantos objetos para verificar a colisão?

Continue alterando os dados em cada bloco também parece muito intensivo, então não tenho certeza se é uma boa idéia.

Eu estive pensando em um jogo de defesa de torre em que a torre precisa detectar objetos se os objetos estiverem ao alcance antes de atirar nela. E parece tolo verificar todos os itens, enquanto em alguns momentos não haverá objetos próximos.

Peço desculpas pelo longo post, sempre tendo problemas para me explicar!

Você precisa reduzir a contagem de verificações de colisão reais. Sim, óbvio, eu sei. Então, vamos elaborar sobre isso:

Seu primeiro algoritmo de verificação de colisão sem nenhuma otimização: quantas verificações ele fará em uma execução? Se n for a contagem de objetos, será em torno de n * (n-1) verificações. Para muitos objetos (> 100), isso será terrivelmente lento.

O método de verificação do vizinho não será muito mais rápido. Se seus objetos não são estáticos e se movimentam muito, você precisará criar uma lista desses vizinhos para cada objeto sempre no loop do jogo. Na verdade, isso é pior que o primeiro algoritmo, já que você está executando n * (n-1) para criar a lista de vizinhos e, em seguida, verifique cada objeto se ele colidir com um de seus vizinhos.

Você precisa particionar o espaço do jogo. Digamos que o seu espaço de jogo tenha 400x400 pixels de largura. Você pode particionar isso em quatro subespaços, cada tamanho de 200x200 e verificar cada objeto em qual dos subespaços ele pertence (um objeto pode estar em mais de um subespaço). Então, você só precisará verificar se os objetos em cada subespaço colidem com outros objetos no mesmo subespaço.

Portanto, o custo de tempo de execução será: n para criar a lista de 4 subespaços + (n / 4) * ((n-1) / 4), que é muito melhor que o custo de tempo de execução anterior. Isso pode ser reduzido ainda mais, diminuindo os subespaços (por exemplo, 50x50).

Portanto, nosso algoritmo agora se parece com isso:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Isso é um pouco semelhante à sua ideia de dados de bloco. Mas os subespaços não precisam ter o mesmo tamanho dos blocos.

Podemos fazer um último passo para otimizar ainda mais isso usando um quadtree. Seja k a contagem de subespaços. Para criar as listas de objetos dos espaços, estamos fazendo verificações k * n, levando a muitas verificações se o seu mundo de jogo ficar grande.

Para reduzir esse custo, usamos um quadtree. Um quadtree é outra maneira de particionar nosso espaço de jogo. Em vez de dividir nosso espaço de 400 x 400 em 64 subespaços de 50 x 50 e verificar cada objeto em qual dos 64 subespaços atualmente, o espaço do jogo é dividido em 4 subespaços com metade do tamanho do espaço do jogo (200 x 200), que por sua vez são divididos em subespaços menores (100x100), que por sua vez são divididos novamente em subespaços 50x50. Este é o nosso quadtree.

Agora, se queremos saber em qual subespaço 50x50 um objeto pertence, verificamos em qual dos subespaços 200x200 ele pertence. Em seguida, vamos um nível mais fundo em nosso quadtree e comparamos os 4 subespaços 100x100 que estão dentro do subespaço 200x200 que acabamos de encontrar. Isso é repetido até sabermos em qual subespaço 50x50 o objeto pertence. Então, quantas verificações agora eram necessárias? 4 para cada nível do quadtree (lembre-se de que um objeto pode estar na borda de dois subespaços). Portanto, precisamos de verificações 4 * 3 para atribuir um objeto ao subespaço 50x50 correto. Muito melhor que 64 cheques.

Portanto, nosso algoritmo quadtree precisa de verificações de 4 * 3 * n para criar as listas de subespaços e, em seguida, algo como verificações de k * (n / k) para verificar as colisões de cada objeto.