Detecção de colisão 2D mais rápida

13

Recentemente, tenho trabalhado em um jogo de tiro em 2D em ritmo acelerado e me deparei com um grande problema. Detecção de colisão. Claro, está funcionando, mas é muito lento. Meu objetivo é: ter muitos inimigos na tela e fazê-los não se tocarem. Todos os inimigos estão perseguindo a entidade do jogador. A maioria deles tem a mesma velocidade; mais cedo ou mais tarde, todos acabam ocupando o mesmo espaço enquanto perseguem o jogador. Isso realmente diminui o fator divertido, pois, para o jogador, parece que você está sendo perseguido por apenas um inimigo. Para impedi-los de ocupar o mesmo espaço, adicionei uma detecção de colisão (uma detecção 2D muito básica, o único método que conheço) que é.

Enemy class update method
    Loop through all enemies (continue; if the loop points at this object)
        If enemy object intersects with this object
            Push enemy object away from this enemy object

Isso funciona bem. Contanto que eu tenha apenas <200 entidades inimigas. Quando me aproximo de 300-350 entidades inimigas, minha taxa de quadros começa a cair bastante. Primeiro, achei que a renderização estava ruim e removi a chamada de empate. Isso não ajudou em nada, é claro que percebi que era o método de atualização. A única parte pesada em seu método de atualização é essa parte de cada inimigo percorre todos os inimigos. Quando chego perto de 300 inimigos, o jogo faz uma iteração de 90000 (300x300). Meu meu ~

Tenho certeza de que deve haver outra maneira de abordar essa detecção de colisão. Embora eu não tenha idéia de como. As páginas que encontro são sobre como realmente fazer a colisão entre dois objetos ou como verificar a colisão entre um objeto e um bloco. Eu já sei essas duas coisas.

tl; dr? Como abordar a detecção de colisões entre MUITAS entidades?

Edição rápida: Se tiver alguma ajuda, estou usando o C # XNA.

eShredder
fonte
Eu estou querendo saber como você conseguiu chegar aos 90K em primeiro lugar. o meu engasga com 20K (embora eu esteja fazendo a detecção SAT MTV completa). Mas percorrer todos os inimigos é a única coisa que parece possível. No entanto, o que você precisa fazer é verificar se eles já foram verificados, porque se você gosta do que diz, todo mundo está sendo testado duas vezes.
Lógica delirante
3
Esta é uma possível duplicata de gamedev.stackexchange.com/questions/39931/…
Markus von Broady
Há uma resposta muito boa na pergunta que @MarkusvonBroady vinculou.
Cypher

Respostas:

11

Você já acertou na cabeça o seu problema, está fazendo com que todas as entidades sejam verificadas em relação a todas as outras entidades. O que você deseja é algum tipo de sistema 'Nível de detalhe' (é um gráfico de cena muito simples, você o está usando apenas para outras coisas que não a renderização :)) onde possíveis candidatos a colisão são mais bem selecionados.

Geralmente faço três coleções para sistemas como este. E quando você está falando sobre o número de entidades que pretende ter, pode ser necessário incluir um gráfico de cena completo para isso, pois os dados de rastreamento (3 listas por entidade com uma entrada para todas as outras entidades) podem sair rapidamente de controle.

Basicamente, embora você tenha três listas. A primeira deve ser uma lista muito pequena de entidades que você irá verificar com interações a cada quadro. Você determina isso porque eles estão dentro do intervalo X da entidade em questão. Como mencionado, o objetivo desta lista é conter todas as entidades que possam colidir razoavelmente com outra dessa estrutura.

A próxima lista são aqueles que estariam em um intervalo de buffer que poderia passar para o intervalo da entidade sem muito esforço. Vamos chamar esse intervalo de X * 1.5 apenas por uma questão de argumento. Esta é uma lista com fatias de tempo em que você atualizará apenas um punhado deles por quadro, mas assegure-se de analisá-los com rapidez suficiente para manter a aparência das coisas funcionando sem problemas.

A terceira lista é a lista de "tudo o resto" e uma maneira de evitar que essa possa valer a pena (Verificar a lista de entidades inteira e talvez verificar se está em uma das outras listas antes de avançar, talvez? podem funcionar ou podem piorar ainda mais as coisas.) Os objetos nesta lista são verificados menos do que tudo, pois deve levar mais do que alguns quadros para serem colocados em uma das outras duas listas.

O que você também precisará fazer para manter isso é quando estiver realizando os testes de colisão; atualize em qual lista as entidades estão. As que saírem do intervalo devem ser desclassificadas e as que se aproximam devem ser atualizadas para um lista mais ativamente verificada.

Supondo que você esteja mantendo as coisas simples o suficiente, isso deve atender às suas necessidades. Se você pode inserir informações extras em um gráfico de cena de renderização existente (supondo que você tenha um) para poder consultá-lo para obter uma lista de entidades que estão razoavelmente dentro do intervalo, seria ainda melhor, pois esse é o ponto inteiro de um gráfico de cena de qualquer maneira (acesso rápido a uma lista de dados relevantes com base em uma posição). Isso poderia levar mais trabalho a ser feito e você deve sempre considerar o que precisa fazer ou o que deve fazer praticamente.

Espero que isto ajude.

James
fonte
1
Esta é uma resposta vaga. E podemos aceitar perder algumas colisões? Muito mais simples, use uma estrutura de dados que faça o particionamento da superfície para você, como o Quad Tree de que falo aqui. Mesmo um Quad Tree precisa de um pouco de ajuste fino para evitar sobrecarga, então não consigo imaginar a complexidade da 'solução' de que você fala. Regra básica de programação: basta usar a estrutura de dados correta.
GameAlchemist
@VincentPiel Um gráfico de cena não é mais complexo que uma árvore quádrupla.
Cypher
@ James: obviamente, é mais complexo. Se você não se importa em entender a velocidade máxima do QuadTree, pode obter uma lib QuadTree na rede e fazê-la funcionar perfeitamente em algumas horas. Nenhuma pergunta como: o que coloco na primeira lista, na segunda, na terceira, como decido colocar uma entidade em outra lista ... e nenhuma colisão foi perdida. Por que usar uma bicicleta quando você pode ter um carro?
GameAlchemist
@VincentPiel Eu acho que você quis dizer @ seu comentário para Cypher em vez de mim aqui. Qualquer pessoa que tenha uma árvore quádrupla é apenas um tipo de gráfico de cena e você deve se lembrar de que está executando X quadros por segundo. Se você perceber colisões perdidas, precisará ajustar os limites do intervalo para equilibrar melhor as coisas. Minha solução é apenas uma abordagem muito simples de garantir que você verifique apenas as coisas em todos os quadros com chance de serem colididas e, em seguida, faça atualizações limitadas / em segundo plano no restante para ver se elas se qualificam para uma prioridade mais alta ainda.
James
6

Você precisa lidar com colisões com uma estrutura de dados classificada, para que você possa ter n * log (n) vezes em vez do terrível n ^ 2. E n * log (n) é quase linear como você deve saber. Um exemplo (clássico) é um quadtree, há um tutorial bastante simples e bem escrito aqui, com gráficos e código (Java):

http://gamedev.tutsplus.com/tutorials/implementation/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space/

Rq: é muito fácil encontrar uma implementação para o QuadTrees em qualquer idioma. Ainda assim, é necessário pensar na granularidade certa para a árvore e, quanto maior o tamanho da árvore, mais temos entidades que não cabem dentro de um nó. Rq3: Depois de ter sua árvore, uma "colisão" entre a tela e as entidades dá a você ... as entidades visíveis !! em um momento mais parecido com log (n), então por que não se n for grande? (o pior caso é obviamente um tempo em n para essa abordagem.)
Rq 2: como o particionamento de espaço é feito apenas para detecção de colisão, você tem perfeita liberdade para dividir o espaço como quiser. Por exemplo, eu não dividiria em quatro partes iguais, mas usaria o baricentro das entidades de nível atual como um centro para a nova divisão. 1) o algoritmo ainda é n * log (n), 2) você perde a possibilidade de 'reconstruir' a cena da árvore - mas você não se importa - e 3) você tem uma árvore muito mais equilibrada, menos sobrecarga .

GameAlchemist
fonte
Sim, um quad tree é apenas um tipo de gráfico de cena. Eu sempre assumo que as pessoas que estão aqui querem escrever as coisas por si mesmas, não usam a biblioteca de outra pessoa; nesse caso, por que parar em uma árvore quádrupla, basta encontrar uma biblioteca de colisão completa.
James
0

árvore de partição de espaço binário, quadtree, octree (para 3D) são possíveis árvores que você pode gerar (ou manter, se for ambicioso) a cada chamada de atualização para cada objeto que você deseja que a colisão aplique.

kchoi
fonte
3
Isso é mais apropriado para ser um comentário. Considere adicionar mais à sua resposta.
0

Sou bastante ingênuo quando se fala em quad ou oct tree. Mas acho que esse método deve fazer:

Você precisará modificar a estrutura / classe do jogador. Adicione uma matriz / vetor de ponteiros à outra estrutura do player.

A cada segundo, verifique a distância entre cada dois jogadores. Se é tão baixo que é possível alcançar dentro de 1 s, adicione o ponteiro desse jogador à matriz de colisão do jogador atual.

Agora verifique apenas a colisão entre jogadores na lista de outros jogadores.

user3042253
fonte