Detecção de colisão 2D

11

Vamos supor que estou usando esse personagem.

pássaro
(fonte: iconbug.com )

Como você implementaria a detecção de colisão para isso? Usar uma caixa delimitadora não parece ser uma boa aproximação, porque a forma do pássaro não está nem perto de um quadrado.

Eu estava pensando em ter uma espécie de estrutura de dados em quatro árvores dentro do objeto que representa partes da imagem. Cada folha pode ser false(caso cubra o espaço branco / transparente fora do pássaro) ou true(caso represente uma área do pássaro, isto é, bico, olho etc.). Então teste de alguma maneira o único obstáculo na cena para colisão com o pássaro.

Mas meus problemas na minha abordagem são:

  1. Não sei como inicializar o quad tree.
  2. Depois que a árvore quádrupla é inicializada, não sei como atravessá-la e usá-la quando o obstáculo estiver dentro das coordenadas da imagem.

Como você faria a detecção de colisões com caracteres não quadrados?

LE: A outra abordagem que vi foi usar várias caixas delimitadoras. Por exemplo, eu teria uma ou algumas caixas delimitadoras para o bico, depois algumas para o cabelo ou a cauda. Mas pode ser entediante. Se essa é uma abordagem válida no meu caso, como eu geraria essas caixas delimitadoras? Duvido que eu tenha que codificá-las no meu programa.

LE2: Eu me preocupo com colisões bastante precisas. Não consigo imaginar como uma única caixa ou círculo delimitador possa pelo menos se aproximar decentemente dessa forma, para que essa abordagem não funcione.

assíncrono
fonte
2
Uma observação geral: eu usaria ambos, uma caixa delimitadora e uma verificação mais granular: a verificação granular terá uma penalidade de desempenho mais alta; portanto, você deseja que ela seja executada o mais raramente possível. Portanto, primeiro marque a caixa delimitadora e somente se isso for atingido, vá um nível mais profundo e teste sua abordagem mais granular (o que quer que seja).
Philip Allgaier 12/03
Obrigado, eu estava planejando fazer isso de qualquer maneira, mas não tenho certeza de qual deveria ser a 'verificação granular'. :)
assíncrono
1
O único detalhe importante está faltando: o que você quer fazer com isso? Você se importa com colisões exatas? Você está feliz em aproximar o personagem com um círculo? Você quer que as partículas de poeira colidam com os olhos do personagem separadamente do resto?
Anko
@ Anko Como você pode aproximar essa forma com um círculo? Eu me preocupo com colisões bastante precisas - não muito precisas em pixels, mas com algo que pareça bom / natural -.
assíncrono
1
Como este . O que significam "bom" e "natural"? Esta é uma pergunta filosófica?
precisa

Respostas:

12

Colisor de círculo. Bom o suficiente, eu diria, a menos que você esteja fazendo algo chique com certas partes sendo afetadas pela física ou a colisão parecer antinatural, e mesmo que você precise dividi-la em várias partes, tenho uma coisa a dizer para você:

Não complique demais.

Você não precisa de uma estrutura completa de árvores quádruplas para isso. Basta ter várias caixas ou círculos em uma matriz reta e, em seguida, cruzar com todas elas. Isso não pode ser suficientemente crítico para o desempenho e você não ganhará muito com o uso de uma árvore quádrupla.

Jonkel
fonte
3
Sim, basta fazer uma pequena variedade de várias formas se uma única forma não a cobrir. Por exemplo: i.imgur.com/Dd4yyGN.png
MichaelHouse
Obrigado Jonkel & @ Byte56. Usar algumas formas parece a solução certa na minha situação. Simples de implementar, preciso e rápido. Não posso acreditar que pulei direto para quad árvores sem considerar isso! Uh
assíncrono
Um colisor circular para o corpo e um retangular para o bico, para maior precisão.
Kroltan
14

Um processo de verificação em duas etapas

Na primeira etapa, marque a caixa delimitadora e, se não houver colisão, o teste será concluído. Se houver colisão, você passa para a segunda passagem

Na segunda passagem , se você deseja mais precisão e deseja uma solução perfeita em pixels, pode fazer exatamente isso, um passe de verificação perfeito em pixels

Como sua imagem é PNG (ou qualquer outro formato de arquivo que contenha um canal alfa), isso seria bastante fácil

  1. Calcule a área de interseção entre esse objeto na cena e o pássaro, gerando um simples retângulo de interseção nas duas imagens
  2. Nessa interseção, verifique se cada pixel tem um valor alfa> 0 em AMBAS as imagens
  3. Se algum desses pixels existir, você terá sua colisão. Caso contrário, não

Se você observar o canal alfa de suas imagens, poderá ver como ele já possui todas as informações necessárias para uma colisão perfeita de pixels

canal alfa da imagem

As colisões perfeitas em pixels são geralmente caras, portanto, fazer uma estimativa aproximada com uma caixa delimitadora ou uma figura de colisão mais detalhada (como a sugerida por Anko) pode economizar um tempo precioso

A caixa delimitadora de colisão detalhada "mais fina" Anko sugeriu:

caixa delimitadora mais detalhada

PS: Se sua imagem possui um halo, um efeito ou outro canal alfa diferente de 0 em torno do qual você não deseja colidir, o limite do algoritmo pode ser facilmente ajustado para acomodar esse

codemonkey
fonte
1
Obrigado! Mas eu não vou precisar de precisão perfeita de pixel, afinal. Excelente resposta, porém, será útil posteriormente.
assíncrono
é claro companheiro, sim, pixel perfeito colisão é quase sempre um exagero, exceto em jogos que realmente precisam dele (como lutadores 2D)
codemonkey
3

Eu usaria um círculo para o corpo e um único retângulo para o bico, mas essa é apenas a minha opinião. A complicação excessiva da geometria de colisão pode desacelerar o aplicativo, você praticamente está dobrando (ou mais) o número de caracteres na tela.

igrad
fonte
0

Talvez você possa usar algum tipo de colisor de polígono / borda instável.

Não sei exatamente como isso funcionaria, mas:

dois objetos: objeto 1: o pássaro (o1), objeto 2: a coisa que pode atingir o pássaro (o2)

1) Defina uma forma delimitadora que é um polígono que se encaixa bem no primeiro objeto (o1) em questão.

2) Obtenha as arestas de o1, o2 que poderiam colidir concebivelmente sem poderiam colidir sem o2 passar por o1 ou vice-versa.

Com a posição e o tamanho da forma (o2), você provavelmente poderia isolar arestas (de o1) que não podem ser atingidas, seja porque estão "por trás" de outra aresta (de o1) mais próxima de o2. Se você tivesse um triângulo retângulo cuja hipotenusa estava voltada para cima e para a direita e um retângulo se aproximando diretamente (com o lado comprido ao longo do eixo x), poderá dizer quais arestas devem ser omitidas porque são os valores inicial e final de y. acima ou abaixo do retângulo.

3) Determine se um dos pontos em uma aresta de o2 é igual a um ponto em qualquer uma das arestas de o1 que você selecionou na etapa 2.

esse conceito provavelmente funciona melhor para coligir polígonos (ou seja, itens com arestas claras), mas talvez você possa tratar um círculo como uma aresta longa (por exemplo, se o2 fosse um círculo).

Jeremy Harton
fonte