um algoritmo simples de colisão de retângulos 2D que também determina quais lados os retângulos colidem?

16

Inicialmente, experimentei implementar a interseção retangular, que funciona bem. No entanto, quando preciso aplicar o sistema de física, como velocidade, aceleração e vetores direcionais, precisaria encontrar uma maneira de determinar qual lado dos retângulos colide. Agora, no meu sistema, não há retângulo girado, então isso simplificou o problema. No entanto, não consegui encontrar uma maneira fácil de determinar qual lado do retângulo colidiu. Já lidei com esse problema antes, mas falhei miseravelmente.

O que fiz no passado foi determinar a distância entre os lados retangulares paralelos e verificar se a distância é próxima de 0 (use alguma faixa de distância definida inicialmente) ou é 0. No entanto, para aritmética de ponto flutuante, isso se mostra instável porque de tempo desconhecido decorrido. Em algum momento, os retângulos se cruzariam antes de atingir o intervalo definido.

Por outro lado, eu estava pensando em gerar vários retângulos, cada retângulo para cada lado. No entanto, depois de pensar novamente, seria o mesmo que ter um lado paralelo com a verificação da faixa de distância, apenas que essa faixa de distância é a largura de cada mini-retângulo.

Portanto, alguma sugestão para esse problema?

user1542
fonte
Você está usando atualizações de posição discretas ou contínuas? (você está atualizando sua velocidade pela aceleração uma vez a cada quadro e, em seguida, calcular a posição, ou usando uma função de extrapolar a posição)
Casey Kuball

Respostas:

24

Adaptado da minha resposta para "Qual lado foi atingido?" :

Eu sugiro computar o soma de Minkowski de B e A, que é um novo retângulo, e verificar onde o centro do retângulo A se encontra relativamente ao novo retângulo (para saber se uma colisão está acontecendo) e às suas diagonais (para saber onde a colisão está) está acontecendo):

float w = 0.5 * (A.width() + B.width());
float h = 0.5 * (A.height() + B.height());
float dx = A.centerX() - B.centerX();
float dy = A.centerY() - B.centerY();

if (abs(dx) <= w && abs(dy) <= h)
{
    /* collision! */
    float wy = w * dy;
    float hx = h * dx;

    if (wy > hx)
        if (wy > -hx)
            /* collision at the top */
        else
            /* on the left */
    else
        if (wy > -hx)
            /* on the right */
        else
            /* at the bottom */
}
sam hocevar
fonte
1
Gostaria de acrescentar que 'top' e 'bottom' são relativos ao seu sistema de coordenadas. No meu jogo, por exemplo, (0,0) está no canto superior esquerdo, então eles são invertidos do seu exemplo. Apenas algo para ter em mente.
Neikos
ótima solução, funcionou muito bem para minhas necessidades.
Opiatefuchs
1
Existe alguma falha com dx se tornando 0 ou dy se tornando 0 ou ambos? Deixe-me pensar sobre isso ... se dx = 0 && dy == 0, isso significa que ambos os retângulos estão na mesma origem, então o algoritmo retorna ao fundo por padrão? se um deles for 0, o resultado correto é esperado. Então, acho que esse algoritmo está correto, exceto no caso em que dx == 0 && dy == 0, que deve ser indeterminado e não inferior. Portanto, cuidado e obrigado.
Prasanth
1
Agora, eu estava pensando o que acontece quando dx == dy, w == h ... também, o código decide que o resultado é um lado quando na verdade é indeterminado ... imagine dois quadrados se cruzando de modo que o centro de um quadrado esteja no um canto de outro quadrado e o centro do outro quadrado fica no canto do primeiro quadrado. Aqui, o lado deve ser indeterminado - não está certo ou embaixo. São os dois ?!
Prasanth