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

13

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!

omgnoseat
fonte
Que língua é essa? Javascript?
Kyle C
2
Actionscript 3, mas a linguagem é bastante irrelevante. Só quero descobrir o que é a melhor maneira de lidar e estruturar este :)
omgnoseat

Respostas:

8

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.

Stephen
fonte
Isso é um awnser muito claro e compreensível, muito obrigado! Como é tratado em qual subespaço está um objeto? O subespaço é manipulado como um objeto, onde o objeto nele é salvo como matrizes e verificado entre si? Ou você apenas verifica em qual subespaço está verificando o X e Y dentro do loop principal? Parece que construir e alterar matrizes o tempo todo é bastante ineficiente. Então, quero ter certeza de que uso o método apropriado :) Também vejo um problema ocorrendo quando os objetos variam de tamanho. Eu acho que o menor subespaço deve ser tão grande quanto o maior objeto?
omgnoseat
Fico feliz em ajudar :) Um subespaço seria um objeto que mantém os 4 subespaços que ele contém. O menor subespaço é diferente, pois não contém mais subespaços, mas uma lista de seus objetos. Considerando o custo da atualização: a árvore do subespaço é criada uma vez no início do jogo. Em cada loop do loop principal, as listas de objetos nos menores subespaços são limpas e preenchidas novamente. Portanto, apenas a lista adicionar / remover é necessária. Nenhuma matriz precisa ser alterada. O menor subespaço deve ser grande o suficiente para conter vários objetos do jogo. O tamanho depende do seu jogo e pode ser ajustado mais tarde.
Stephen
Obrigado, esquecemos que também verificaremos colisões entre os objetos reais no menor subespaço, faz sentido que ele deva ser capaz de armazenar vários objetos agora. Eu comecei em um teste e está indo muito bem. O maior problema que estou tendo é detectar em qual subespaço um objeto pertence. Eu continuo repetindo os subespaços childs X e Y, esse é um método apropriado?
omgnoseat
Como você lida com objetos que se estendem para mais de um subespaço (ou seja, cuja localização está dentro ou perto de um limite)?
Mghicks 26/10/11
Simples: eu não. Os objetos podem fazer parte de vários subespaços, se estiverem no limite de cada subespaço. Portanto, um objeto pode fazer parte de até 4 subespaços. Mas essa é a minoria.
Stephen