Resolução de colisão

23

Sei muito bem como verificar colisões, mas não sei como lidar com a colisão de uma maneira boa.

Simplificado, se dois objetos colidirem, uso alguns cálculos para alterar a direção da velocidade. Se eu não mover os dois objetos, eles ainda se sobreporão e se a velocidade não for grande o suficiente, eles ainda colidirão após a próxima atualização. Isso pode fazer com que os objetos fiquem presos um no outro.

Mas e se eu tentar mover os dois objetos para que eles não se sobreponham. Parece uma boa ideia, mas percebi que, se houver mais de dois objetos, isso se torna muito complicado. E se eu mover os dois objetos e um deles colidir com outros objetos, também tenho que movê-los e eles podem colidir com paredes etc.

Eu tenho um jogo 2D de cima para baixo em mente, mas não acho que tenha muito a ver com isso. Como as colisões são geralmente tratadas?

Esta pergunta é feita em nome de Wooh

CiscoIPPhone
fonte
1
Você pode esclarecer o tipo de jogo? "2D de cima para baixo" pode significar muitas coisas: um jogo de ação e aventura no estilo Zelda, um jogo de rolagem vertical ou um jogo de bilhar de bolso. Todos eles teriam estilos padrão muito diferentes de manipulação de colisões!
Ian Schreiber
2
Não consigo esclarecer isso. A questão não é sobre o que acontecerá como resultado de uma colisão, é sobre como lidar com o problema de múltiplas sobreposições. Acho que basta saber que estou riscando objetos um do outro e quero que eles se comportem realisticamente para responder a essa pergunta.
CiscoIPPhone

Respostas:

16

Daniel Kodicek aborda esse tópico em grande detalhe em seu livro Matemática e Física para Programadores .

Kodicek faz duas coisas para obter uma resolução de colisão com aparência natural:

  • Sua função de detecção de colisão calcula o tempo exato em que dois objetos colidirão.
  • Ele recalcula novas velocidades no momento da colisão, para que os objetos nunca se sobreponham.

Enviei uma demonstração com base na detecção e resolução de colisões da Kodicek .

update: Aqui está um algoritmo de detecção e resolução de colisões muito semelhante ao método de Kodicek. Com código fonte . Eu ainda recomendo o livro de Kodicek, pois seu algoritmo é implementado de maneira um pouco diferente e muito mais minuciosamente explicada.

Leftium
fonte
1
Seu link de demonstração parece estar quebrado.
ashes999
@ ashes999: link corrigido agora!
Leftium 18/09/11
É um algoritmo para círculos. E as caixas?
Anton Chikin
@AntonChikin: O algoritmo de resolução de colisão de Kodicek usa apenas três entradas: massa, velocidade e normal no ponto de colisão. Kodicek sempre calcula o normal no ponto de colisão ao detectar colisões. Ele explica muitos tipos diferentes de detecção de colisão, incluindo uma caixa atingindo outra. Basta conectar esse algoritmo de detecção de colisão ao algoritmo de resolução de colisão. Veja os capítulos 8 a 10 do livro de Kodicek para uma explicação completa. (Nota física de rotação requer mais matemática, que também é coberto mais tarde no livro ...)
Leftium
1
@ThomasHilbert: código-fonte de demonstração e executáveis ​​do Windows agora disponíveis em leftium.com/asteroid
Leftium
6

E se você verificar a colisão antes que os objetos se movam, em vez de depois? Ou, em outras palavras, você rejeita a nova posição se os objetos colidirem, reutilizando a antiga nesse caso?

Pseudo-código:

  tmpPosition1 = Obj1.position
  tmpPosition2 = Obj2.position
  updatePosition(Obj1)
  updatePosition(Obj2)
  if collided(Obj1,Obj2) then
      updateVelocities( Obj1, Obj2 )
      Obj1.position = tmpPosition1
      Obj2.position = tmpPosition2
  endif

Dessa forma, os objetos se chocam quando estão prestes a colidir , se a etapa de atualização for pequena o suficiente, o jogador não deve notar nada de estranho na representação.

CeeJay
fonte
1
Isso é muito chato, porque você não pode se mover facilmente paralelamente aos objetos, porque você não pode se mover se tocar em outros objetos.
Ikke
A menos que você resolver x e y separadamente
instantaphex
6

Sempre que dois objetos se sobrepõem, verifique se eles estão se aproximando ou afastando um do outro. Faça a colisão somente se eles se moverem um em direção ao outro.

É bem fácil com a matemática vetorial, basta calcular:

dot_product (B.position - A.position, A.velocity - B.velocity)

Se o resultado for positivo, os objetos se moverão um em direção ao outro.

aaaaaaaaaaaa
fonte
4

Eu poderia estar entendendo mal, mas parece que você está fazendo duas perguntas: 1. Quais são algumas maneiras gerais de lidar com a resolução de colisões, o termo que você procura é 'simulação baseada em impulso' e há vários papéis que pode fazer melhor justiça do que eu.

Em resumo, você deseja executar uma simulação de física no espaço de momento, que é a massa vezes a velocidade (não faça coisas baseadas na força, seu integrador não está fazendo direito de qualquer maneira).

Para resposta angular, felizmente, os maiores e menores momentos de inércia sempre podem ser reduzidos a dois eixos ortogonais (em 2D), o que significa que uma multiplicação de matrizes funcionará geralmente, e se você alinhá-los com os eixos X e Y, ele se transforma em um vetor 2D.

Quando você colide, descobre a resposta com base nos momentos linear e angular no ponto de colisão, e um bom fator de fudge é, se você tiver interpenetração, aplicar alguma força de penalidade (como mencionado acima) para separar os dois corpos.

A partir do momento, você acabará adicionando mais e mais regras para controlar comportamentos aberrantes, como limitar o momento angular máximo para que as coisas não girem como tops, etc., mas este é um bom começo.

Mantenha-o simples, se puder.

  1. Como você resolve problemas de colisão de corpos múltiplos

A única maneira real de fazer isso é com um sistema de equações lineares e muita solução. A maneira prática de fazer isso é ter um sistema como o descrito acima e fazer com que a física resolva naturalmente com o tempo.

A maioria dos jogos que fazem coisas como rolar ou ficar de pé em superfícies em movimento tem um modelo híbrido no qual seus pés estão presos a uma superfície (ou rodas na estrada) para acomodar o tempo da física (o que resultaria em ciclos de interpenetração-resposta e não funcionaria).

Espero que isto ajude. Se você precisar de exemplos de matemática, me avise.

Aaron Brady
fonte
3

A maneira como isso geralmente é resolvido nos motores de física é aplicando uma força de penalidade. Mover o corpo rígido após a interpenetração não parecerá bom se seus corpos rígidos estiverem se movendo em velocidades mais altas (você verá movimentos bruscos momentâneos), embora, como primeiro passo, tente isso e verifique se ele atende às suas necessidades.

A penalty forceé aplicado como um amortecedor de mola, onde a força da penalidade é aumentada quanto mais você penetrar no corpo rígido e diminui nos quadros subsequentes. Pense nisso como fontes. Quando dois corpos rígidos interpenetram, cada um deles encontra uma mola invisível que amortece sua progressão (isto é, impede mais interpenetração) e aplica o mencionado anteriormente penalty forceaté que os corpos não estejam mais penetrando.

É um tópico amplo, mas espero que as informações acima o ajudem a começar.

Samaursa
fonte
Então, em vez de impedir a interpenetração, esse método permite, mas fornece resistência, quase como se os objetos estivessem sendo comprimidos?
CiscoIPPhone
Ele fornece resistência, sim, a resistência aumenta quanto mais o corpo está tentando penetrar. Na prática, se você tiver um tempo delta baixo o suficiente (por exemplo, 10 ms), ele não produzirá interpenetrações. A vantagem real desse método, porém, é quando você tem corpos que entraram em contato por várias razões (a posição foi alterada, eles são corpos rígidos em rede e suas posições foram corrigidas) e agora precisam ser separados, porque sem essa técnica, os corpos explodirá em vez de gradualmente se separar.
Samaursa