Como resolver colisões de corpos rígidos em 2D
(sassnow.ski)- A resolução de colisões de corpos rígidos na física 2D de jogos é o problema de calcular mudanças de velocidade para que objetos que já se tocaram ou se sobrepuseram não atravessem uns aos outros no próximo frame
- Como o loop do jogo atualiza a posição usando a velocidade e Δt a cada frame, se a geometria se sobrepõe na nova posição, os objetos acabam atravessando uns aos outros sem um tratamento adicional
- Colisão não é apenas uma questão de haver contato, mas também de verificar se os objetos em contato continuam se movendo um em direção ao outro com suas velocidades atuais
- É possível determinar se estão se afastando da superfície pelo sinal do produto escalar entre a normal e a velocidade: se for positivo, há componente na mesma direção; se for negativo, há componente na direção oposta
- No caso de dois objetos, mais importante que as velocidades individuais são a velocidade relativa e a normal da colisão; quando há contato e a velocidade normal relativa é negativa, isso pode ser considerado uma colisão
Física de corpos rígidos e o escopo da resolução de colisões
- O tema aqui é física de corpos rígidos (rigid body physics), isto é, objetos que não se deformam mesmo quando submetidos a forças
- Na realidade, todos os objetos se deformam em nível molecular, então corpos perfeitamente rígidos não existem
- Em grande parte das simulações físicas, calcular esse nível de deformação em detalhe é muito difícil ou caro computacionalmente
- Se os objetos parecerem realistas o bastante, simplificá-los como corpos rígidos é uma abordagem prática
- O tratamento de colisões em engines de jogo normalmente se divide em duas etapas
- Detecção de colisão (collision detection): determina quais objetos da cena estão colidindo
- Resolução de colisão (collision resolution): define o estado posterior com base na direção de movimento, velocidade, material etc. dos objetos em colisão
- O foco aqui não é a etapa de encontrar interseções geométricas, mas sim a resolução de colisão, que determina o movimento após a colisão
Como as colisões surgem no loop do jogo
- A maioria dos jogos recalcula repetidamente a posição dos objetos da cena dentro de um grande loop
- Em cada iteração, a posição do objeto é atualizada com base na velocidade (velocity) atual
- Velocidade é uma grandeza vetorial com magnitude e direção
- O comprimento da seta representa a rapidez, e a direção da seta indica a direção do movimento
- A mudança de posição durante um intervalo de tempo Δt é expressa como deslocamento (displacement)
- Deslocamento também é uma grandeza vetorial com magnitude e direção
- Se o loop do jogo roda 60 vezes por segundo, então Δt é 1/60 de segundo
- A nova posição é obtida somando à posição anterior o deslocamento calculado a partir da velocidade atual
- Se a nova posição de dois objetos fizer com que suas geometrias se sobreponham, então, sem tratamento adicional, eles irão se penetrar e atravessar um ao outro
O que a resolução de colisão busca encontrar
- O objetivo da resolução de colisão é determinar a mudança de velocidade de cada objeto para que eles não continuem se penetrando à medida que a simulação avança
- As velocidades antes e depois da colisão são representadas pelos seguintes símbolos
v_a,i,v_b,i: velocidades deaebantes da colisãov_a,f,v_b,f: velocidades deaebdepois da colisãoΔv_a,Δv_b: mudanças de velocidade de cada objeto causadas pela colisão
- No fim, resolver a colisão é encontrar os valores de Δv_a e Δv_b
- Para produzir colisões com aparência realista, a mudança de velocidade escolhida deve satisfazer as leis físicas relevantes
Só o contato não basta para identificar uma colisão
- Dois objetos estarem se tocando nem sempre significa que estão em colisão
- Há colisão quando, se continuarem se movendo com as velocidades atuais, os objetos irão se penetrar
- Mesmo com a mesma cena de contato, dependendo da direção das velocidades dos dois objetos, pode haver colisão ou não
- Portanto, a condição de colisão exige duas coisas ao mesmo tempo
- As geometrias dos objetos devem estar em contato ou sobreposição
- Os objetos ainda devem estar se movendo na direção da colisão
Normal da superfície e direção de afastamento
- É possível determinar se um objeto está se afastando de uma superfície pela direção normal (normal direction) da superfície
- A direção normal é perpendicular à superfície e aponta diretamente para fora dela
- Em uma superfície plana, a direção normal é a mesma em todos os pontos
- Em uma superfície curva, a direção normal muda de ponto para ponto
- Na circunferência de um círculo, a direção que vai do centro até um ponto da borda é a direção normal naquele ponto
- A direção normal é representada por um vetor normalizado de comprimento 1
- Um vetor de comprimento 1 também é chamado de vetor unitário (unit vector)
- Para indicar que um vetor está normalizado, pode-se usar o símbolo
^sobre a variável
- Em qualquer ponto, a direção normal é perpendicular à tangente (tangent) da superfície naquele ponto
Usando o produto escalar para determinar componentes de direção
- Quando se quer calcular o quanto um vetor aponta na mesma direção que outro, pode-se usar o produto escalar (dot product)
- Em vetores bidimensionais, o produto escalar é a soma dos produtos de componentes correspondentes, e o resultado é um escalar, não um vetor
- Geometricamente, o produto escalar pode ser visto como o comprimento escalar da projeção de um vetor na direção do outro, multiplicado pelo comprimento do vetor sobre o qual foi projetado
- O sinal do produto escalar informa a relação direcional entre dois vetores
- Se o ângulo entre dois vetores for menor que 90°, o produto escalar será positivo e eles apontam, em geral, para a mesma direção
- Se o ângulo entre eles for maior que 90°, o produto escalar será negativo e eles apontam, em geral, para direções opostas
- Se o ângulo for exatamente 90°, o produto escalar será 0
- Se o produto escalar entre o vetor velocidade de um objeto e a normal da superfície for positivo, o objeto está se afastando daquela superfície
Aplicando ao caso de colisão entre dois objetos
- Quando há dois objetos, como duas caixas, existe um vetor velocidade para cada um deles
- Nesse caso, usa-se a velocidade relativa (relative velocity) entre os dois objetos, em vez das velocidades individuais
- Velocidade relativa é a diferença entre as velocidades dos dois objetos
- Geometricamente, é o vetor que vai da ponta de
v_baté a ponta dev_a - Por exemplo, se dois carros colidem de frente, cada um a 50 km/h, isso é equivalente, nas mesmas condições, a um carro a 100 km/h batendo em um carro parado
- A direção correspondente à superfície é expressa pela normal da colisão (collision normal)
- A forma de calcular a normal da colisão depende da forma ou da geometria dos objetos em colisão
- O exemplo aqui é uma colisão vértice-aresta (vertex-edge collision), em que um ponto ou vértice de um objeto colide com a aresta de outro objeto
- Em uma vertex-edge collision, a normal da colisão é perpendicular à aresta correspondente
- Por convenção, se os objetos são indicados por
aeb, a normal da colisão aponta para o objetoa- Não importa qual objeto é chamado de
aoub, desde que essa escolha permaneça consistente em todo o cálculo
- Não importa qual objeto é chamado de
Definindo colisão pela velocidade normal relativa
- Ao calcular o produto escalar entre a velocidade relativa
v_abe a normal da colisãon^, é possível determinar se os dois objetos estão se movendo na direção da colisão - Esse valor é chamado de velocidade normal relativa (relative normal velocity)
- É a componente da velocidade relativa na direção da normal da colisão
- Aqui, o sinal é importante, mas esse valor também desempenha papel importante mais adiante no cálculo das forças que atuam durante a colisão
- O sinal da velocidade normal relativa distingue os estados de colisão
- Se o valor for positivo, os dois objetos já estão se afastando um do outro
- Se o valor for negativo, os dois objetos ainda estão se chocando
- Em termos finais, ocorre colisão quando um ponto de um objeto está em contato com o outro objeto e a velocidade normal relativa é negativa
1 comentários
Opiniões do Hacker News
O texto foi pensado para pessoas que, como eu, não são desenvolvedoras de jogos e não têm uma formação forte em matemática. Por isso, expliquei por bastante tempo até conceitos que podem parecer quase óbvios para quem tem experiência na área. Se tiverem perguntas, terei prazer em responder
Iniciantes em desenvolvimento de jogos muitas vezes entendem equivocadamente que, para tratar colisões, precisam de cálculos de colisão de corpos rígidos ou de um motor de física 2D como o Box2D. Se você quer fazer um jogo de bilhar ou um jogo como Angry Birds, com caixas desmoronando, isso faz sentido; mas, para um platformer 2D, basta detectar colisões comparando retângulos alinhados aos eixos e então mudar as coordenadas X/Y do personagem para desfazer a sobreposição, ou definir a velocidade em Y após um salto ou pouso. Assim também fica mais fácil ajustar com precisão a sensação de controle do personagem; há inércia, mas geralmente não é uma inércia fisicamente realista. Quando iniciantes tentam usar física realista, é fácil o movimento ficar flutuante e insatisfatório
Um exemplo de tutorial para começar com essa abordagem simples, sem motor de física: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
Fui empilhando componentes como pontos e linhas repetidamente e, com muitos passos pequenos e linhas visuais de depuração, o resultado ficou bem rangente e lento, mas, de algum modo, funcionou até certo ponto
Você também pretende ler e explicar XPBD (Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) no futuro? Esse conceito parece estar ganhando cada vez mais atenção, e eu o usei com bastante sucesso no Bevy por meio de https://github.com/Jondolf/bevy_xpbd. Parece mais estável do que a abordagem comum
Seria ótimo se você adicionasse um feed RSS para eu poder continuar acompanhando
Por curiosidade, quais ferramentas você usou para criar essa página?
Sinceramente, quando vi o nome de domínio no começo e percebi que o domínio de topo era “.ski”, achei que fosse o site da pessoa que escreveu Mechanical Watch [1] e outros textos excelentes. No fim, era uma pessoa completamente diferente, mas a qualidade é parecida. Qual é o molho secreto desse domínio de topo “.ski”? :)
O autor de https://ciechanow.ski, de quem gostamos aqui, também é um programador polonês que trabalha na Apple
Um elemento importante do jogo é que os detritos espaciais possam ser movidos dentro da arena e usados de forma criativa para encurralar o adversário ou impedir que ele alcance objetivos. Como parte do projeto, pretendíamos pular completamente o motor de jogo. Eu queria ensinar um pouco mais de estrutura de aplicações ao meu filho e, mesmo que no futuro usemos um motor de jogo pronto, queria que ele passasse pelo processo de implementar tudo pelo menos uma vez. Estava tudo bem até chegarmos à detecção e ao tratamento de colisões. A partir daí, a situação piorou rapidamente. Mesmo tendo formação em matemática teórica, fiquei rapidamente sobrecarregado com a enorme quantidade de casos de borda e, no fim, desisti e resolvi usar Box2D. Não sou desenvolvedor profissional de jogos, mas tenho mais de 20 anos de experiência em desenvolvimento e formação em matemática; ainda assim, cometi o erro de subestimar esse problema. Parece uma daquelas coisas que, falando, soa fácil, mas cuja complexidade cresce exponencialmente conforme você entra nos detalhes
Um método comum para fazer um jogo de tiro usando comparações de retângulos bem simples está aqui: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
Dito isso, se os objetos de detrito espacial precisam colidir e se agrupar de forma realista, e se você quer dificultar que a nave do jogador empurre conjuntos de objetos pesados, faz sentido usar uma biblioteca de física
[1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...
[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...
Era a época em que Flash estava em toda parte
Código: https://github.com/vandrieu/canvas-bouncing-ball
A lógica de colisão está em src/collision.ts
Resultado/demo: https://vandrieu.github.io/canvas-bouncing-ball/
Se possível, você poderia adicionar uma licença?
Mas, em jogos, muitas vezes as atualizações de física caem para 30 Hz e usam um esquema Euler-Cromer arbitrário, então é preciso uma abordagem bem diferente
Levei meses, mas, em um nível um pouco além do básico amplamente conhecido, só consegui arranhar a superfície. Criar um motor estável em que os objetos não se pressionem para dentro uns dos outros nem fiquem tremendo é uma toca de coelho sem fundo, e os textos mais carregados de matemática que encontrei quase não tratavam disso. Eu entendi a matemática com a antiga série de artigos de Chris Hecker
http://www.chrishecker.com/Rigid_Body_Dynamics
A parte difícil é a colisão de projéteis. Eu precisava pegar a posição atual da bala e a posição no próximo passo de tempo, e fazer o mesmo com a hitbox do inimigo para verificar se havia interseção, mas eu só verificava o passo de tempo atual. Por isso, a bala pode passar magicamente desviando do inimigo! Uma coisa boba. Talvez algum dia eu volte e conserte