Como funciona um mecanismo de colisão?

Como exatamente um mecanismo de colisão funciona?

Esta é uma questão extremamente ampla. Que código mantém as coisas batendo contra o outro, que código faz o jogador entrar em uma parede em vez de atravessar a parede? Como o código atualiza constantemente a posição dos jogadores e a posição dos objetos para manter a gravidade e a colisão funcionando como deveriam?

Se você não sabe o que é um mecanismo de colisão, basicamente é geralmente usado em jogos de plataforma para fazer o jogador bater de maneira aguda nas paredes e coisas do gênero. Existe o tipo 2D e o tipo 3D, mas todos realizam a mesma coisa: colisão.

Então, o que mantém um mecanismo de colisão funcionando?

Há uma grande diferença entre um mecanismo de colisão e um mecanismo de física. Eles não fazem a mesma coisa, embora o mecanismo de física geralmente dependa de um mecanismo de colisão.

O mecanismo de colisão é então dividido em duas partes: detecção e resposta à colisão. Este último geralmente faz parte do mecanismo de física. É por isso que os mecanismos de colisão e os mecanismos de física geralmente são colocados na mesma biblioteca.

A detecção de colisão vem em duas formas, discreta e contínua. Os mecanismos avançados suportam ambos, pois eles têm propriedades diferentes. Em geral, a detecção contínua de colisões é muito cara e usada apenas onde é realmente necessária. A maioria das colisões e da física é tratada usando métodos discretos. Em métodos discretos, os objetos acabam se penetrando, e o mecanismo de física trabalha para separá-los. Portanto, o mecanismo não impede um jogador de andar parcialmente através de uma parede ou do chão, apenas o conserta depois de detectar que o jogador está parcialmente na parede / piso. Vou focar aqui na detecção discreta de colisões, já que é isso que tenho mais experiência na implementação do zero.

Detecção de colisão

A detecção de colisão é relativamente fácil. Todo objeto tem uma transformação e uma forma (possivelmente várias formas). Abordagens ingênuas fazem com que o mecanismo de colisão faça um loop O (n ^ 2) através de todos os pares de objetos e testa se há sobreposição entre os pares. Nas abordagens mais inteligentes, existem várias estruturas de dados espaciais (por exemplo, para objetos estáticos e dinâmicos), uma forma delimitadora para cada objeto e sub-formas convexas de várias partes para cada objeto.

As estruturas de dados espaciais incluem coisas como árvores KD, árvores dinâmicas AABB, árvores / árvores, árvores de particionamento de espaço binário e assim por diante. Cada um tem suas vantagens e desvantagens, e é por isso que alguns motores de ponta usam mais de um. Árvores AABB dinâmicas, por exemplo, são realmente muito rápidas e boas para lidar com muitos objetos em movimento, enquanto uma Árvore KD pode ser mais adequada para a geometria de nível estático com a qual os objetos colidem. Existem outras opções também.

A fase ampla usa as estruturas de dados espaciais e um volume delimitador abstrato para cada objeto. Um volume delimitador é uma forma simples que envolve todo o objeto, geralmente com o objetivo de incluí-lo o mais "firmemente" possível, mantendo-se barato para realizar testes de colisão. As formas delimitadoras mais comuns são caixas delimitadoras alinhadas por eixo, caixas delimitadoras alinhadas a objetos, esferas e cápsulas. Os AABBs são geralmente considerados os mais rápidos e fáceis (as Esferas são mais fáceis e mais rápidas em alguns casos, mas muitas dessas estruturas de dados espaciais exigiriam a conversão da esfera em um AABB de qualquer maneira), mas também tendem a se ajustar mal a muitos objetos. As cápsulas são populares nos mecanismos 3D para lidar com colisões no nível dos caracteres. Alguns motores usarão duas formas delimitadoras,

A última fase da detecção de colisão é detectar exatamente onde a geometria está se cruzando. Isso geralmente implica o uso da malha (ou polígono em 2D), embora nem sempre. O objetivo desta fase é descobrir se os objetos realmente colidem, se é necessário um bom nível de detalhes (por exemplo, colisão de balas em um atirador, em que você deseja ignorar tiros que mal erram) e também para descobrir exatamente onde os objetos colidem, o que afetará como os objetos respondem. Por exemplo, se uma caixa estiver na borda de uma mesa, o mecanismo deve saber em que pontos a mesa está empurrando contra a caixa; dependendo de quão longe a caixa está pendurada, a caixa pode começar a inclinar e cair.

Geração de coletores de contatos

Os algoritmos usados ​​aqui incluem os populares algoritmos GJK e Minkowski Portal Refinement, bem como o teste Separating Axis. Como os algoritmos populares normalmente funcionam apenas para formas convexas, é necessário dividir muitos objetos complexos em subobjetos convexos e fazer testes de colisão para cada um individualmente. Essa é uma das razões pelas quais malhas simplificadas são frequentemente usadas para colisão, bem como a redução no tempo de processamento para o uso de menos triângulos.

Alguns desses algoritmos não apenas informam que os objetos colidiram com certeza, mas onde eles colidiram - até que ponto eles estão se penetrando e quais são os "pontos de contato". Alguns dos algoritmos requerem etapas adicionais, como o recorte de polígono, para obter essas informações.

Resposta Física

Nesse ponto, um contato foi descoberto e há informações suficientes para o mecanismo de física processar o contato. O manuseio da física pode ficar muito complexo. Algoritmos mais simples funcionam para alguns jogos, mas mesmo algo aparentemente simples como manter uma pilha de caixas estável acaba sendo bastante difícil e requer muito trabalho e hacks não óbvios.

No nível mais básico, o mecanismo de física fará algo assim: ele pegará os objetos em colisão e seu coletor de contatos e calculará as novas posições necessárias para separar os objetos colididos. Ele moverá os objetos para essas novas posições. Também calculará a mudança de velocidade resultante desse impulso, combinada com os valores de restituição (bounciness) e atrito. O mecanismo de física também aplicará quaisquer outras forças que atuam sobre os objetos, como a gravidade, para calcular as novas velocidades dos objetos e depois (no próximo quadro) suas novas posições.

Uma resposta física mais avançada fica complicada rapidamente. A abordagem acima será quebrada em muitas situações, incluindo um objeto em cima de outros dois. Lidar com cada par por si só causará "tremor" e os objetos irão ricochetear bastante. A técnica mais básica é fazer várias iterações de correção de velocidade sobre os pares de objetos em colisão. Por exemplo, com uma caixa "A" em cima de duas outras caixas "B" e "C", a colisão AB será tratada primeiro, fazendo com que a caixa A se incline ainda mais na caixa C. Em seguida, a colisão CA é manipulada à noite retire as caixas um pouco, mas puxe A para baixo e para dentro B. Em seguida, outra iteração é feita, para que o erro AB causado pela correção CA seja ligeiramente resolvido, criando um pouco mais de erro na resposta CA. Que é tratado quando a CA é processada novamente. O número de iterações feitas não é fixo e não há um ponto em que se torne "perfeito", mas apenas o número de iterações para de dar resultados significativos. 10 iterações é uma primeira tentativa típica, mas são necessários ajustes para descobrir o melhor número para um mecanismo específico e as necessidades de um jogo específico.

Cache de contato

Existem outros truques que são realmente úteis (mais ou menos necessários) ao lidar com muitos tipos de jogos. O cache de contatos é um dos mais úteis. Com um cache de contato, cada conjunto de objetos em colisão é salvo em uma tabela de pesquisa. Cada quadro, quando uma colisão é detectada, esse cache é consultado para verificar se os objetos estavam em contato anteriormente. Se os objetos não estavam em contato anteriormente, um evento de "nova colisão" pode ser gerado. Se os objetos estavam em contato anteriormente, as informações podem ser usadas para fornecer uma resposta mais estável. Quaisquer entradas no cache de contatos que não foram atualizadas em um quadro indicam dois objetos que se separaram, e um evento "objeto de separação" pode ser gerado. A lógica do jogo geralmente tem usos para esses eventos.

Também é possível que a lógica do jogo responda a novos eventos de colisão e os sinalize como ignorados. Isso é realmente útil para implementar alguns recursos comuns em plataformas, como plataformas pelas quais você pode avançar, mas permanecer firme. Implementações ingênuas podem simplesmente ignorar colisões que têm uma plataforma descendente -> colisão de personagem normal (indicando que a cabeça do jogador atingiu a parte inferior da plataforma), mas sem o cache de contato, isso será interrompido se a cabeça do jogador aparecer na plataforma e ele começar cair. Nesse ponto, o contato normal pode acabar apontando para cima, fazendo o jogador aparecer pela plataforma quando não deveria. Com o armazenamento em cache de contatos, o mecanismo pode observar com segurança a colisão inicial normal e ignorar todos os outros eventos de contato até que a plataforma e o jogador se separem novamente.

adormecido

Outra técnica muito útil é marcar objetos como "adormecidos" se não estiverem sendo interagidos. Objetos adormecidos não recebem atualizações físicas, não colidem com outros objetos adormecidos e basicamente ficam lá congelados no tempo até que outro objeto não adormecido colida com eles.

O impacto é que todos os pares de objetos colididos que estão apenas sentados ali sem fazer nada não levam tempo de processamento. Além disso, como não há uma quantidade constante de pequenas correções físicas, as pilhas serão estáveis.

Um objeto é candidato a dormir quando tiver uma velocidade quase zero por mais de um único quadro. Observe que o epsilon usado para testar essa velocidade quase zero provavelmente será um pouco maior do que o epsilon de comparação de ponto flutuante usual, pois você deve esperar alguma instabilidade com objetos empilhados e deseja que pilhas inteiras de objetos adormeçam se elas ' permanecendo "perto o suficiente" para estável. Obviamente, o limiar exigirá ajustes e experimentação.

Restrições

O último grande pedaço de muitos mecanismos de física é o solucionador de restrições. O objetivo desse sistema é facilitar a implementação de coisas como molas, motores, eixo das rodas, corpos moles simulados, tecidos, cordas e correntes e, às vezes, até fluidos (embora o fluido seja frequentemente implementado como um sistema totalmente diferente).

Até o básico da solução de restrições pode ser muito intensivo em matemática e vai além da minha experiência neste assunto. Eu recomendo verificar a excelente série de artigos de Randy Gaul sobre física para obter uma explicação mais aprofundada do tópico.

O problema geral: determine qual de todas as combinações possíveis de objetos tem um volume de interseção diferente de zero.

A abordagem geral ingênua é simples: para cada par possível de objetos, calcule o volume da interseção. Isso geralmente não é prático, pois requer O (n ^ 2) operações de interseção relativamente caras.

Portanto, as implementações práticas são geralmente especializadas, fazendo certas suposições para permitir evitar verificações cruzadas ou reduzir seu custo. O particionamento espacial aproveita o fato de que os objetos geralmente são pequenos em relação ao volume total e reduzem o número de comparações com O (n log n). Caixas delimitadoras e esferas delimitadas alinhadas ao eixo fornecem verificações de interseção grosseiras e baratas, desde que os objetos obedeçam a certas suposições de compactação. E assim por diante.

Um "mecanismo de colisão" que eu usei parecia extremamente fácil de entender.

Basicamente, a API forneceu um tipo de objeto com método collidesWith, de modo que

1. seus parâmetros eram diferentes tipos de objetos "elegíveis" para colisão
2. retornou verdadeiro ou falso, dependendo se a colisão aconteceu ou não
3. havia uma opção que permitia escolher se todos os retângulos delimitadores dos objetos acionam o evento de colisão ou apenas pixels opacos dentro desses retângulos (detecção no nível de pixel)

Na minha inscrição, eu apenas invocava periodicamente collidesWithpara descobrir se a colisão aconteceu ou não.

Muito simples, não é?

Talvez a única coisa que exigisse um pouco de imaginação fosse quando retângulos delimitadores simples não eram suficientes para simular a geometria de objetos em colisão. Nesse caso, seria necessário simplesmente usar vários objetos colidíveis em vez de um.

Geralmente, quando você descobre que um retângulo de colisão única não faz o que você precisa, inventa uma maneira de decompor as coisas em subelementos mais retangulares para que, quando combinados, esses elementos simulem / aproximem o comportamento desejado.

• Os usuários finais simplesmente não se importam com quantos objetos existem nos bastidores. Eles ficam felizes desde que o resultado final pareça com o que esperam, por exemplo, como uma casa com uma cerca do quintal ao redor:

  

Eu acho que você está um pouco confuso sobre o que está falando, e está falando sobre algumas coisas diferentes.

a capacidade de dizer que esse item é movido do local X para o local Y é baseada na física (isso também ataca como eles se movem e por que eles se movem)

o método usado para a detecção de colisões é determinado com base na estrutura do seu jogo. se o seu jogo é um mundo aberto, considere o particionamento espacial (quad-tree [oct-tree para 3D], BSP, uma grade tradicional ou o antiquado teste de tudo).

a melhor maneira de implementar um sistema de detecção de colisão é fazê-lo em etapas.

1. coloque todos os objetos em um formato / volume delimitador genérico e teste-os

2. se 1 passou, repita com uma repetição de volume / forma mais complexa até estar pronto para testar a geometria absoluta

3. teste a geometria absoluta, o número de vezes que você repete a etapa 2 deve ser determinado com base na complexidade de suas formas e na precisão dessas formas.

você deve considerar cada uma dessas etapas o mais cedo possível, e com o objetivo de eliminar colisões à medida que avança, e retornar somente na etapa 3 se elas realmente estiverem tocando.

Então, a última parte é a resolução de colisão. isso determina o que acontece depois que você encontra uma colisão e provou que realmente é uma colisão e o que fazer a respeito. isso geralmente é tratado pela física.

o loop tradicional fica assim:

receive input
update physics
collision detection
collision resolution
render
repeat

No nível da placa gráfica (onde você lida normalmente com triângulos), a idéia geral é particionar sua cena de alguma maneira, para que você não precise verificar todos os N triângulos (isso pode ser feito como uma etapa de pré-processamento). ) e descubra onde você está na cena e verifique apenas os 10-50 triângulos nessa partição.

Veja árvores BSP e Kd para mais informações. Existem também outras abordagens de particionamento.

Em primeiro lugar, acho que o trabalho mais importante de um mecanismo de colisão é determinar o que não precisa ser verificado quanto à colisão em qualquer situação específica quadro a quadro e selecionar esses objetos de verificações adicionais.

Secundariamente, mas também importante, verifique de maneira mais detalhada (precisa) os objetos restantes que não foram descartados na primeira etapa.

Em terceiro lugar, utilize os métodos mais eficientes / adequados para realizar as verificações.