Resolução de colisão em caso de colisão com vários objetos

15

Eu tenho objetos estáticos e objetos móveis. As colisões são detectadas usando o teorema do eixo separador.

Por exemplo, nessa situação, tenho dois objetos estáticos (em vermelho):

insira a descrição da imagem aqui

e um objeto móvel entre os dois:

insira a descrição da imagem aqui

Meu algoritmo é capaz de calcular a colisão entre dois desses objetos e também cospe um vetor de resolução perfeita (significando um vetor de deslocamento mínimo) para a colisão.

Por exemplo, quando eu checo a colisão entre o retângulo verde e o retângulo vermelho direito, o algoritmo cospe um vetor que me diz como eu preciso mover o retângulo verde para resolver a colisão:

insira a descrição da imagem aqui

Observe que eu desenhei isso rapidamente no MSPaint, então nessa imagem pode ser que o vetor de tradução mínimo empurre o retângulo verde para cima, mas presumo que o empurre para a esquerda / certo é realmente mais curto.

A maneira geral de abordar isso seria resolver apenas a colisão de uma colisão por quadro, em vez de todos de uma vez. Mas no meu caso, isso resultaria em flip-flopping:

Primeiro, o solucionador detecta duas colisões, mas apenas resolve a colisão entre o retângulo direito e o retângulo verde:

insira a descrição da imagem aqui

Em seguida, no próximo quadro, ele detecta apenas uma colisão que está entre o retângulo vermelho esquerdo e o retângulo verde e o resolve:

insira a descrição da imagem aqui

Como você pode ver, isso realmente não resolve a colisão (por exemplo, empurrando o retângulo verde para cima) e, em vez disso, apenas inverta os flops infinitamente.

Como posso resolver isso?

TravisG
fonte
Você está usando retângulos no seu exemplo. Seu algoritmo de colisão resolve apenas a colisão em apenas um eixo? Nesse caso, faz sentido que o comportamento que você descreve esteja ocorrendo.
chaosTechnician
Não, ele pode resolvê-los com qualquer tipo de forma em todos os eixos possíveis (não apenas retângulos, eles são os mais fáceis de desenhar com tinta MS: P) e sempre encontrará o vetor mais curto existente que separa os dois objetos .
TravisG
+1 boa pergunta. Eu removi a "tag" (2D) do título, é algo que você deve evitar (consulte a meta ).
bummzack

Respostas:

7

Dependendo exatamente do que você está tentando alcançar (alta precisão física ou apenas uma simulação em tempo real suficientemente próxima), você pode tentar usar contatos especulativos.

Aqui estão os detalhes: http://www.wildbunny.co.uk/blog/2011/03/25/speculative-contacts-an-continuous-collision-engine-approach-part-1/

Ele descreve nesse artigo o que você precisa saber para implementá-lo, e é muito simples comparado a outras abordagens (como projeção de esferas e classificação das resoluções de colisão por tempo de impacto).

Se você precisar / quiser mais, poderá comprar o código-fonte por US $ 7 (IIRC).

Aqui está um vídeo da minha implementação em 3D: http://www.youtube.com/watch?v=JvT2H1RmOas

Observe como a simulação é estável com apenas uma única iteração. Você poderia facilmente usar várias iterações por quadro para resolver várias colisões para um estado estável, o que seria mais preciso.

Olhovsky
fonte
2

Você pode primeiro calcular todos os vetores necessários para resolver cada colisão e depois calcular uma resultante deles.

O único caso em que isso pode ser byte é se esses vetores se anulam, como no seu exemplo. Nesse caso, a colisão não pode ser resolvida.

Mihai Maruseac
fonte
Adicione um pequeno vetor aleatório com uma magnitude de cerca de epsilon * 10 às colisões? A aritmética de ponto flutuante deve fazer o resto.
Martin Sojka
2
Sim, isso pode funcionar, eu acho. Mas também pode criar movimentos trêmulos.
Mihai Maruseac
11
Espero ainda poder obter uma resposta sobre isso: calcular um resultante corrige o problema do "loop infinito", mas reintroduz o problema do "crack", onde mover-se enquanto desliza sobre uma parede feita de ladrilhos do mesmo tamanho faz com que o corpo fique preso entre as "rachaduras" dos azulejos. Existe alguma maneira de resolver esses dois problemas?
Vittorio Romeo
Concordo ... não existe a melhor "resposta certa" para resolver uma colisão impossível de corpos rígidos como essa. Ou ele se agita, ou você permite um pouco de "bolor" em um ou mais dos objetos.
David van brink
0

Se você olhar atentamente, esse estado de objetos é (ou deveria ser) inatingível.

Deixe a forma vermelha mais à esquerda ter a forma R1 e a forma vermelha mais à direita ter a forma R2. Deixe a forma verde ser G.

Dado o tamanho e a geometria dos três objetos, e considerando que todos os objetos não são penetráveis:

 (1) G could not have been just directly to the left of R2, since R1 has been there 
     already. Consequently, the translation of G from left to right, penetrating R2
     could not have occurred.
 (2) G could not have been just directly to the right of R1 since R2 has been there 
     already. Consquence of which is the same as that from (1).
 (3) Had G come from the top, the movement will be blocked by both R1 and R2, given
     that their geometry and Y coordinate is the same.

Agora, tudo se resume a isso: se seu algoritmo consulta seus objetos um por um, é uma questão de simultaneidade, ou seja, de certa forma, o algoritmo deve verificar TODOS os objetos ao mesmo tempo, mas o algoritmo limita você a fazer objetos e processá-los um de cada vez ...

Se G é checado contra R1 depois de checado com R2, então G parece legalmente estar à direita de R1 (se G diz aproxima-se de R1 com a direção do vetor <-1, -1> com magnitude (ou distância) arbitrária ), porque a verificação entre R1 e G permite isso e esquece a verificação entre R2 e G, que foi feita antes.

Uma solução que você pode fazer é coletar todos os vetores de deslocamento mínimo em uma matriz ou em qualquer estrutura de dados desejada e escolher uma que seja legal para TODOS os Objetos.

Observe que em um determinado quadro, o objeto (G, por exemplo) pode ter apenas UMA direção. (oh cara, parece a boyband ...)

Liu Mao Hsing
fonte