Existe uma maneira de aumentar a eficiência da verificação de colisão de um sistema de n objetos?

Estou fazendo um jogo que consiste em muitos objetos na tela, um dos quais é o jogador. Eu preciso saber quais objetos estão colidindo a cada iteração.

Eu fiz algo parecido com isto:

for (o in objects)
{
   o.stuff();
   for (other in objects)
      if (collision(o, other))
          doStuff();

   bla.draw();
}

Isso tem O (n ^ 2), o que me disseram que é ruim. Como faço isso com mais eficiência, é possível? Estou fazendo isso em Javascript, e geralmente será menor que 30, será um problema se isso permanecer o mesmo?

Com apenas 30 objetos no máximo, você não precisa de muita otimização, a não ser verificar os mesmos dois pares um do outro mais de uma vez por quadro. Que o exemplo de código abaixo abordará. Mas se você estiver interessado em diferentes otimizações que um mecanismo de física usaria, continue lendo o restante deste post.

O que você precisará é de uma implementação de particionamento espacial , como Octree (para jogos em 3D) ou Quadtree (para jogos em 2D). Elas dividem o mundo em subseções e, em seguida, cada subseção é particionada ainda mais na mesma mansão, até que se subdividam em um tamanho mínimo. Isso permite que você verifique rapidamente quais outros objetos estão na mesma região do mundo que outro, o que limita a quantidade de colisões que você deve verificar.

Além do particionamento espacial, eu recomendaria a criação de um AABB ( caixa delimitadora alinhada ao eixo ) para cada um dos seus objetos de física. Isso permite que você verifique o AABB de um objeto em relação a outro, o que é muito mais rápido do que uma verificação detalhada por poli entre objetos.

Isso pode ser mais um passo para objetos físicos complicados ou grandes, nos quais é possível subdividir a malha física, dando a cada subforma o seu próprio AABB que você só pode verificar se os AABBs de dois objetos estiverem sobrepostos.

A maioria dos mecanismos de física desativará a simulação de física ativa nos corpos físicos assim que eles pararem. Quando um corpo físico é desativado, ele só precisa verificar a colisão contra seu AABB em cada quadro, e se algo colidir com o AABB, ele será reativado e fará uma verificação de colisão mais granular. Isso mantém os tempos de simulação baixos.

Além disso, muitos mecanismos de física usam 'ilhas de simulação', onde é agrupado um grupo de corpos físicos próximos. Se tudo na ilha de simulação estiver em repouso, a própria ilha de simulação será desativada. O benefício da ilha de simulação é que todos os corpos dentro dela podem parar de verificar colisões quando a ilha estiver inativa, e a única verificação em cada quadro é para ver se algo entrou na AABB da ilha. Somente quando algo entrar na AABB da ilha, cada um dos corpos dentro da ilha precisará verificar colisões. A ilha de simulação também se reativa se algum corpo dentro dela começar a se mover novamente por conta própria. Se um corpo se afastar o suficiente do centro do grupo, ele é removido da ilha.

No final, você fica com algo assim (em pseudo-código):

// Go through each leaf node in the octree. This could be more efficient
// by keeping a list of leaf nodes with objects in it.
for ( node in octreeLeafNodes )
{
    // We only need to check for collision if more than one object
    // or island is in the bounds of this octree node.
    if ( node.numAABBsInBounds > 1)
    {
        for ( int i = 0; i < AABBNodes.size(); ++i )
        {
           // Using i+1 here allows us to skip duplicate checks between AABBS
           // e.g (If there are 5 bodies, and i = 0, we only check i against
           //      indexes 1,2,3,4. Once i = 1, we only check i against indexes
           //      2,3,4)
           for ( int j = i + 1; j < AABBNodes.size(); ++j )
           {
               if ( AABBOverlaps( AABBNodes[i], AABBNodes[j] ) )
               {
                   // If the AABB we checked against was a simulation island
                   // then we now check against the nodes in the simulation island

                   // Once you find overlaps between two actual object AABBs
                   // you can now check sub-nodes with each object, if you went
                   // that far in optimizing physics meshes.
               {
           }
        }
    }
}

Eu também recomendaria não ter tantos loops em loops como este, o exemplo acima foi apenas para você ter a ideia, dividi-lo em várias funções que oferecem a mesma funcionalidade de algo como o que é mostrado acima.

Além disso, certifique-se de não alterar o contêiner AABBNodes enquanto o percorre, pois isso pode significar falhas nas verificações de colisão. Isso pode parecer senso comum, mas você ficaria surpreso com a facilidade de reagir a colisões, causando mudanças que você não anteciparia. Por exemplo, se uma colisão fizer com que um dos objetos em colisão mude de posição o suficiente para removê-los do AABB do nó Octree que você estava verificando, isso poderá alterar esse contêiner. Para resolver isso, recomendo manter uma lista de todos os eventos de colisão que ocorrem durante as verificações e, depois que todas as verificações estiverem concluídas, execute a lista e envie quaisquer eventos de colisão.

Seu exemplo testa cada par de objetos várias vezes.

Vamos dar um exemplo muito simples com uma matriz contendo 0,1,2,3

Com seu código, você obtém o seguinte:

• No loop 0, você testa contra 1, 2 e 3
• No loop 1, você testa 0, 2 e 3 ===> (0-1 já testado)
• No loop 2 você testa contra 0, 1 e 3 ===> (0-2 / 1-2 já testado)
• No loop 3, você testará 0, 1 e 2 ===> (0-3 / 1-3 / 2-3 já testado)

Agora vamos ver o seguinte código:

for(i=0;i<=objects.length;i++)
{
    objects[i].stuff();

    for(j=i+1;j<=objects.length;j++)
    {
        if (collision(objects[i], objects[j]))
        doStuff();
    }

    bla.draw();
}

Se usarmos a matriz contendo 0,1,2,3 novamente, teremos o seguinte comportamento:

• No loop 0, você testa contra 1, 2, 3
• No loop 1 você testa contra 2, 3
• No loop 2 você testa contra 3
• No loop 3, você testa contra nada

Com o segundo algoritmo, obtivemos 6 testes de colisão, enquanto o anterior solicitou 12 testes de colisão.

Crie seu algoritmo de acordo com suas necessidades, mas mantenha os detalhes da implementação encapsulados. Mesmo em Javascript, os conceitos básicos de POO se aplicam.

Pois N =~ 30, O(N*N)não é uma preocupação e é provável que sua pesquisa linear seja tão rápida quanto qualquer outra alternativa existente. Mas você não deseja codificar suposições no seu código. No pseudocódigo, você teria uma interface

interface itemContainer { 
    add(BoundingBox);
    remove(BoundingBox);
    BoundingBox[] getIntersections();
}

Isso descreve o que sua lista de itens pode fazer. Em seguida, você pode escrever uma classe ArrayContainer que implementa essa interface. Em Javascript, o código ficaria assim:

function ArrayContainer() { ... } // this uses an array to store my objects
ArrayContainer.prototype.add = function(box) { ... };
ArrayContainer.prototype.remove = function(box) { ... };
ArrayContainer.prototype.getIntersections = function() { ... };

function QuadTreeContainer { ... } // this uses a quadtree to store my objects
... and implement in the add/remove/getIntersections for QuadTreeContainer too

E aqui está um código de exemplo que cria 300 caixas delimitadoras e obtém todas as interseções. Se você implementou ArrayContainer e QuadTreeContainer corretamente, a única coisa que você precisa mudar no seu código é a mudança var allMyObjects = new ArrayContainer()para var allMyObjects = QuadTreeContainer().

var r = Math.random;
var allMyObjects = new ArrayContainer();
for(var i=0; i<300; i++)
    allMyObjects.add(new BoundingBox(r(), r()));
var intersections = allMyObjects.getIntersections();

Fui em frente e preparei a implementação do ArrayContainer padrão aqui:

http://jsfiddle.net/SKkN5/1/

Você também deve considerar os tipos de objetos que podem colidir sensatamente.

Por exemplo, o jogador provavelmente precisa ser verificado quanto a colisão com tudo, exceto suas próprias balas. No entanto, os inimigos podem precisar apenas checar as balas do jogador. As balas quase certamente não precisam colidir umas com as outras.

Para implementar isso com eficiência, você provavelmente deseja manter listas separadas de objetos, uma por tipo de objeto.