AABBs 2D e resolução de múltiplas colisões

8

Ok, então este é um problema que venho tentando descobrir há algum tempo. O Mine é um jogo de plataformas 2D com um mundo composto de (geralmente) blocos imóveis e sprites móveis, os quais usam AABBs para representar seus hitboxes. Este jogo NÃO é baseado em grade devido a algumas complicações com a movimentação de camadas de peças.

Eu posso detectar colisões e descobrir facilmente a profundidade da colisão. Eu uso o "método de eixo mais raso" para determinar qual caminho resolver uma colisão entre o sprite e o ladrilho. Se o sprite for mais profundo horizontalmente do que verticalmente, a direção a ser resolvida é para cima ou para baixo. Se o sprite for mais profundo verticalmente do que horizontalmente, a direção a ser resolvida é esquerda ou direita.

Diagrama # 1

Isso é bastante simples e funciona muito bem. Ou seja, até que você tenha um sprite colidindo com mais de um bloco. Como, por sua natureza, cada colisão deve ser verificada separadamente, diferentes colisões podem ter uma direção diferente para resolver. Por exemplo, se um sprite estiver tentando atravessar uma fileira de ladrilhos, para um quadro, eles cruzarão o próximo ladrilho, como que a profundidade horizontal é menor que a profundidade vertical. Como a colisão diz "resolva à esquerda", ela será empurrada para trás e ficará presa na esquina.

Diagrama # 2

Venho refletindo sobre esse problema há muito tempo, e há várias soluções para mim, mas todas têm falhas. Eu poderia marcar certos lados como inacessíveis, mas sem um mecanismo baseado em grade, a determinação de "inacessibilidade" é notavelmente complexa, especialmente com a possibilidade de mover camadas de ladrilhos sempre.

Outro método possível seria prever colisões antes que elas aconteçam e "retroceder" o movimento até o ponto da colisão, suponho, mas não tenho certeza de como a matemática funciona.

Sinto que estou perdendo algo incrivelmente óbvio, principalmente porque os jogos dos anos 80 já resolveram esse problema.

Celarix
fonte
Você pode alterar a localização do jogador com base em qual
peça

Respostas:

6

O problema

O problema está no seu método de resolução de colisões. Seu método é o seguinte:

  1. Mova o jogador.
  2. Verifique se há colisão.
  3. Determine a menor profundidade de colisão.
  4. Resolver colisão.

O problema é que ele pode mover o jogador facilmente na direção errada. Você pode ver como isso pode acontecer na imagem abaixo:

Bug de colisão

Como o jogador está se movendo para a direita e está acima do solo, seria de esperar que ele caísse em cima do solo (pela caixa verde). Mas, em vez disso, ele é empurrado do chão para a esquerda (representado pela caixa vermelha). Isso pode ser um problema se o jogador estiver tentando pular de uma plataforma para outra, porque o jogador pode acabar morrendo devido a um código de colisão incorreto.

A solução

A solução para esse problema é realmente bastante simples. Em vez de usar o método acima, você resolve a colisão da seguinte maneira:

  1. Mova o player ao longo do eixo X.
  2. Verifique se há blocos colidindo.
  3. Resolver a colisão X.
  4. Mova o player ao longo do eixo Y.
  5. Verifique se há blocos colidindo.
  6. Resolva a colisão em Y.

Agora, espero que você não tenha descartado seu código de verificação de profundidade, porque ainda precisará dele nas etapas 3 e 6.

Para resolver a colisão entre peças em qualquer um dos dois eixos (depois de mover o jogador), você primeiro obtém a profundidade da colisão. Você pega a profundidade da colisão e subtrai a dos eixos que você está verificando no momento. Observe que a profundidade deve ser negativa se você estiver se movendo para a esquerda, para que o jogador se mova na direção certa.

Usando esse método, você não apenas não precisará se preocupar com erros de colisão como o do cenário da imagem acima, mas também pode lidar com colisões com vários blocos.

Código de exemplo:

void move(velocity)
{
    top = player.y / TILE_HEIGHT;
    bottom = top + (player.height / TILE_HEIGHT);
    left = player.x / TILE_WIDTH;
    right = left + (player.width / TILE_WIDTH);

    // Check X

    player.x += velocity.x;
    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {
        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getXDepth(aabb);
                player.x -= depth;
            }
        }
    }

    // Now check Y

    player.y += velocity.y;
    player.updateAABB();
    for(int tx = left - 1; tx <= right + 1; tx++)
    {
        for(int ty = top - 1; ty <= bottom + 1; ty++)
        {
            aabb = world.getTileAABB(tx, ty);
            if(aabb.collidesWith(player.aabb))
            {
                depth = player.aabb.getYDepth(aabb);
                player.y -= depth;
            }
        }
    }

    player.updateAABB();
}
Lisol
fonte
Intrigante, mas ainda vejo um problema. No meu segundo cenário, o sprite colide com uma fileira de peças. Se eu verificar X as colisões primeiro, haverá uma detecção incorreta nesse cenário e ela ainda será resolvida para a esquerda incorretamente.
Celarix
@Celarix O segundo cenário não deve acontecer porque você não está apenas verificando o eixo X primeiro, mas sim movendo-o primeiro. O sprite nunca estaria em uma fileira de peças, porque o teste de colisão Y do movimento anterior impediria que você colidisse com uma linha de peças assim. Apenas verifique se as colisões são sempre resolvidas corretamente. Certa vez, tive alguns problemas causados ​​pelo fato de estar usando floats para armazenar minhas coordenadas. Então estava causando tremores. A solução foi arredondar as cordas quando terminei de resolver a colisão.
Lysol
Você está certo e acho que essa pode ser a solução para o meu problema de quase dois anos. (Eu sou um desenvolvedor lento.) Muito obrigado!
Celarix
Existem alguns problemas com a minha resposta. Funciona na maioria das situações, mas observe que haverá resultados diferentes, dependendo se você verificar a colisão X primeiro ou a colisão Y primeiro. Lembre-se também de que o tunelamento é um problema; isso falhará com objetos de alta velocidade, pois eles pularão sobre blocos.
Lysol
Acho que fui primeiro com o X para que as pistas funcionassem corretamente. Bullet-through-paper não é realmente um problema no meu jogo de plataformas, porque nada se move quase rápido o suficiente para passar por peças. Obrigado pela contribuição adicional!
Celarix
0

Você está pensando demais no problema e confundindo alguns problemas. Mas tudo bem, porque, como você disse, este é um problema muito resolvido, com muitas ótimas respostas por aí.

Vamos dividir:

  1. Tilemaps . Seu primeiro exemplo é de um sprite andando por um monte de ladrilhos dispostos horizontalmente (ou deslizando por uma parede de ladrilhos dispostos verticalmente, eles são isomórficos). Uma solução muito elegante para isso é simplesmente não verificar as arestas dos ladrilhos onde sabemos que um sprite não pode chegar, como arestas "subterrâneas" ou arestas que fazem fronteira com outro ladrilho completamente sólido.

    Você está certo de que o sprite desceria devido à gravidade, depois se moveria lateralmente e depois ficaria preso ... mas a resposta é não se importar com as bordas esquerda ou direita dos ladrilhos subterrâneos . Dessa forma, sua rotina de resolução de colisão apenas move o sprite verticalmente - e seu sprite pode seguir seu caminho alegre.

    Confira os tutoriais do bloco Metanet para obter uma explicação passo a passo disso. Você diz na sua pergunta que não está usando um mapa de mosaico tradicional, mas tudo bem: mosaicos estáticos estão no mapa de mosaicos e são atualizados como acima, enquanto movem plataformas e atualizações como # 2 abaixo.

  2. Outros AABBs . Você só terá problemas se, em um único quadro, seu sprite puder se mover uma distância maior que a largura / altura da maioria dos AABBs no seu jogo. Se não puder, você é de ouro: resolva as colisões uma por uma e funcionará bem.

    Se os AABBs puderem se mover muito rápido em um único quadro, você deve "varrer" o movimento ao verificar colisões: divida o movimento em frações menores e verifique se há colisões em cada etapa.

drhayes
fonte