Estou trabalhando em um mecanismo de física puramente contínuo e preciso escolher algoritmos para detecção de colisão de fase ampla e estreita. "Puramente contínuo" significa que eu nunca faço testes de interseção, mas, em vez disso, quero encontrar maneiras de capturar todas as colisões antes que elas aconteçam e colocar cada uma delas na pilha de "colisões planejadas", ordenada pela TOI.

Fase Ampla O único método contínuo de fase larga em que consigo pensar é envolver cada corpo em um círculo e testar se cada círculo se sobrepõe a outro. No entanto, isso parece terrivelmente ineficiente e carece de abate.

Não tenho idéia de que análogos contínuos possam existir para os métodos discretos de abate de colisão de hoje, como quad-trees. Como posso evitar testes amplos inadequados e inúteis, como um mecanismo discreto? Eu também gostaria de poder ver colisões com mais de um quadro à frente.

Fase estreita
Consegui adaptar o SAT estreito a uma verificação contínua, em vez de discreta, mas tenho certeza de que existem outros algoritmos melhores nos documentos ou sites que vocês podem encontrar.
Quais algoritmos rápidos ou precisos você sugere que eu use e quais são as vantagens / desvantagens de cada um?

Nota final:
digo técnicas e não algoritmos, porque ainda não decidi como armazenarei polígonos diferentes que podem ser côncavos, convexos, redondos ou mesmo com orifícios. Eu pretendo tomar uma decisão sobre isso com base no que o algoritmo exige (por exemplo, se eu escolher um algoritmo que divida um polígono em triângulos ou formas convexas, simplesmente armazenarei os dados do polígono neste formulário).

Estou realmente apenas lançando idéias por aqui. Supondo que você tenha (no mínimo) a currentposição e nextposição; para cada quadro.

Você precisaria de duas fases amplas separadas, seguidas da sua fase estreita:

• Um que descobre que uma colisão ocorrerá.
• Um que descobre aproximadamente onde a colisão realmente ocorre (por exemplo, uma fase ampla / SAT impreciso)
• Finalmente, sua fase estreita melhoraria o resultado da segunda fase ampla.

Fase inicial ampla

Você pode examinar o hash espacial (usando a nextposição, não current) para a fase ampla inicial. Isso dividiria bem o espaço do problema em grupos de candidatos a colisão.

Segunda fase ampla

Faça uma amostra múltipla binária usando o método de interseção em círculo que você descreveu. Em outras palavras:

left = current
right = next
midpoint = (left + right) / 2
loop a desired amount of times tweaked to the accuracy you want:
  is a collision occuring at midpoint?
    right = midpoint
  else?
    left = midpoint
  midpoint = (left + right) / 2
pointOfCollision = midpoint

Esse ajuste de precisão também pode levar em consideração a distância - acho que usar o 'comprimento quadrado' de next - currentobteria um resultado perfeito em pixels.

Fase estreita

Faça uma amostra múltipla binária usando algo como PMask - a lógica será exatamente a mesma que acima; apenas usando uma rotina de colisão diferente.

Finalmente

Você será capaz de calcular o tempo de interseção de pointOfCollision, currente seu atual speede acceleration(supondo que você tenha um integrador razoável).

Tudo bem, vi que você atualizou sua pergunta para ser mais específica. Vou tentar ajudá-lo um pouco mais.

Para sua primeira verificação de fase ampla, recomendo fortemente o hash espacial .

Basicamente, você divide sua tela em grades de tamanho igual. Então, se um objeto estiver dentro de uma grade, você o adiciona a um "balde" em uma tabela de hash 1D.

Essa é sua primeira verificação feita. Se os objetos não estiverem no mesmo balde, seria impossível eles se cruzarem.

Continuando com isso, agora você tem uma lista de buckets com objetos (potencialmente) neles. Você pode fazer outra verificação de fase ampla aqui:

A.) Dividindo este balde em outros 4 baldes e verificando a tabela de hash 1D resultante. Se eles não estiverem no mesmo balde, não haverá colisão.

Ou:

B.) Fazendo uma verificação simples da distância e mantendo em mente a largura e / ou altura do objeto para garantir a precisão.

Mas e quando você potencialmente tem uma colisão?

Então eu recomendaria algo ao longo das linhas de presente . É essencialmente um tipo de mistura entre colisão poligonal (para formas complexas) ou retângulo / círculo para formas menos complexas.

Além disso, se você realmente deseja "capturar colisões antes que elas aconteçam e armazená-las", poderá sempre fazer algo assim:

Se dois objetos estiverem no mesmo balde, eles poderão colidir.

Além disso, os objetos estão próximos o suficiente para colidir em breve? (Considerando a velocidade, o tamanho do objeto e a distância)

Se a resposta para ambos for sim, vá em frente e guarde-a para fazer um teste de interseção posteriormente.

" Resposta antiga

Infelizmente, perdi o controle do meu manual "Todos os tipos de colisão e para que são usados". :)

No entanto, mesmo que essa seja uma missão extremamente ampla, eu vou começar.

Há uma boa pergunta (respondida) referente a algo assim aqui .

Bem como um artigo das pessoas que criaram N e N + por aqui .

Sem mencionar, você tem a boa e velha colisão por pixel de fallback .

Sinceramente, duvido que alguém tenha uma lista útil de todo tipo de colisão, mas isso deve ajudar você a começar.

No entanto, devo mencionar que o tipo de colisão que você precisa (e acabará usando) depende muito do tipo de jogo que você está criando. É por isso que você encontra tutoriais - a maioria das pessoas supõe que você tenha uma idéia do que deseja, para ajudá-lo nessa área específica. Percebo que a maioria dos meus links são tutoriais sobre um assunto específico, mas acho que um tutorial honestamente o ajudará mais. Uma lista é uma coisa, mas se você ler sobre cada marcador, poderá tomar uma decisão mais instruída que provavelmente atenderá às suas necessidades mais especificamente.