Como determinar a direção da colisão entre dois retângulos?

Estou tentando descobrir como determinar a direção em que uma colisão ocorre entre dois retângulos.

Um retângulo não se move. O outro retângulo tem uma velocidade em qualquer direção. Quando ocorre uma colisão, quero poder definir a posição do retângulo em movimento para o ponto de impacto.

Parece que estou decidido a determinar em que direção o impacto ocorre. Se estou me movendo estritamente vertical ou horizontalmente, gerencio uma ótima detecção. Mas ao se mover nas duas direções ao mesmo tempo, coisas estranhas acontecem.

Qual é a melhor maneira de determinar em que direção ocorre uma colisão entre dois retângulos?

Parece que estou decidido a determinar em que direção o impacto ocorre. Se eu estiver me movendo estritamente vertical ou horizontalmente, gerencio uma ótima detecção. Mas ao se mover nas duas direções ao mesmo tempo, coisas estranhas acontecem.

tl; dr A solução é mover e verificar colisões, um eixo por vez .

Eu tive esse mesmo problema. Aposto que a fase de atualização do loop do seu jogo é mais ou menos assim:

• object.x + = object.vx
• object.y + = object.vy
• verifique se há colisões
• resposta a colisões

O truque aqui é mover e verificar colisões, um eixo por vez. Como você disse: "Se estou me movendo estritamente vertical ou horizontalmente, gerencio uma ótima detecção". Então você já resolveu 99% do problema. Apenas mude sua lógica para ficar assim:

• object.x + = object.vx
• verificar / responder colisões
• object.y + = object.vy
• verificar / responder colisões

Em casos simples, não importa qual eixo você faz primeiro. Se você não se sente bem ao escolher um ou outro arbitrariamente, é razoável verificar primeiro o eixo em que a velocidade absoluta do objeto é a maior.

De acordo com a resposta de larsbutler, em casos simples, não importa se você verifica primeiro as colisões x ou y. No entanto, isso pode levar rapidamente à imprecisão, mais tarde no caminho (especialmente com formas mais complexas, maiores velocidades e mais objetos).

Se alguém estiver interessado em implementar um algoritmo de detecção de colisão mais sofisticado, aqui está um resumo do que é necessário:

1. Primeiro, o algoritmo faz uma varredura e poda para diminuir o número de objetos necessários para verificar. Se você estiver verificando cada objeto em relação a qualquer outro objeto, pode ser bastante caro, computacionalmente. Basicamente, você prevê se um objeto provavelmente colidirá no futuro; se não for muito provável, você não faz os cálculos.
2. Após a poda, você executa um teste de colisão preliminar. Cada objeto possui um retângulo ou círculo delimitador (algo fácil de calcular colisões). Detectar se dois círculos / retângulos colidem é bastante simples e pode eliminar rapidamente cálculos desnecessários entre dois objetos em lados opostos da tela.
3. Se uma detecção preliminar foi feita, você precisa percorrer as bordas de cada forma e detectar pontos de colisão (interseção de dois segmentos de linha). No caso de Jon, este seria o ponto de colisão no eixo vertical e no eixo horizontal.
4. Depois de ter uma lista de pontos de colisão, você precisa calcular o ponto de colisão exato . Existem várias maneiras de fazer isso, e tudo depende da precisão que você deseja ser. Uma opção é a metade do incremento de tempo (do seu integrador física ), recalcular as posições das formas, e executar novamente a detecção de colisão até que não é apenas um ponto de colisão. Basicamente, você está se aproximando do "momento do impacto". Se a sua simulação não possui muitas forças diferenciais parciais, você pode simplesmente usar a velocidade da integração anterior, com reduções de tempo subsequentes.
5. Os resultados da etapa quatro fornecerão os pontos de colisão aproximados (dentro de um limite superior / inferior, como 3px ou algo assim). Se houver mais de um ponto de colisão, você terá que tratá-los como uma aresta imaginária. Você pode executar cálculos de resolução de colisão (velocidade, momento, fricção, etc.)

Espero que isso ajude alguém.

Específico à pergunta de Jon:

A etapa que está faltando no algoritmo de colisão é a etapa 4. Pelo que entendi, seus retângulos se cruzam na diagonal e acabam recebendo dois pontos de colisão (um na horizontal e outro na vertical). Determinar qual ponto de colisão ocorreu primeiro depende realmente do que você está usando para a integração da física.

Pela sua descrição, parece que os retângulos não giram e coisas como forças diferenciais parciais não são motivo de grande preocupação. Se for esse o caso, descobrir qual borda colide primeiro é bastante simples. Aqui está algum pseudo-código:

/*
   Assume Obj1 is stationary
   Assume Obj2's velocity is -x and -y (to bottom left)
   From this, we know the collision edges are:
*/
colEdgesObj1 = [1,0]; //right, top
colEdgesObj2 = [0,1]; //left, bottom
//... where [0=left/1=right, 0=top/1=bottom]

//Calculate distances between Obj1 edges and Obj2 edges
distX = Math.Abs(Obj1[colEdgesObj1[0] ? "right" : "left"] -
                 Obj2[colEdgesObj2[0] ? "right" : "left"]);
distY = Math.Abs(Obj1[colEdgesObj1[1] ? "bottom" : "top"] -
                 Obj2[colEdgesObj2[1] ? "bottom" : "top"]);

//Calculate time object would take to go those distances
//(assuming Obj2 is the only moving object)
timeX = distX/Obj2.VelX;
timeY = distY/Obj2.VelY;

//If time is greater, that axis has been colliding longer
if timeX > timeY
    //collided X axis first
else if timeY > timeX
    //collided Y axis first
else
    //collided at a corner