Detecção de colisão eficiente baseada em ladrilhos para muitos quadrados?

9

Atualmente, estou trabalhando por conta própria em um jogo baseado em blocos (pense em Terraria, mas menos fantástico (acho que é uma palavra? Desculpe se não é)).

De qualquer forma, atualmente tenho a detecção de colisão funcionando (mesmo nos casos de canto!), O que foi um grande passo para mim. Há algo extremamente gratificante em ver um sprite não correr por um bloco. Mas então tive a ideia de fazer benchmark. Péssima ideia.

1.000 quadrados, não há problema. 10.000 quadrados, para 3 caracteres, era meio que lento. 100.000 quadrados (mapa realmente grande), para 3 personagens, não eram jogáveis.

Estou tendo o problema em que não quero nem considerar os blocos que estão muito longe do jogador, personagens, itens etc., mas não quero carregar esses in-out de memória constantemente.

Aqui está o meu algoritmo até agora, fique à vontade para criticar.

foreach (Block in level)
{
    if (distance from block to player > a specified amount)
        ignore this block;
    else
    {
        get the intersection depth between the two bounding boxes
        if (depth of intersection != Zero-vector)
        {
            check y size vs x size
            resolve on smallest axis
        }
    }
}

Como você notará, quando o tamanho do nível aumentar, a ordem desse algoritmo aumentará em N blocos. Eu gostaria de nem considerar blocos que nem sequer estão perto do jogador.

Acho que talvez use um (0,0) para (mapWidth, mapHeight) matriz dupla de blocos em vez de uma lista, calculando uma zona de perigo dependendo da posição da pessoa, por exemplo, se a posição do jogador estiver em (10, 20) parecerá de (0, 10) a (20, 30) ou mais.

Quaisquer pensamentos e considerações são impressionantes, obrigado.

Ross
fonte
11
E bem-vindo ao stackexchange! :-) Não se esqueça de ler as perguntas frequentes se não souber como funciona todo o sistema de controle de qualidade e reputação.
David Gouveia
Certamente esses blocos são maiores que 16 por 16 pixels, em 1920 por 1080, ou seja, 8.100. Certamente você sabe onde estão as entidades móveis e só pode verificar os ladrilhos na grade que possam estar dentro do alcance (se um for 160 * 160 e o centro estiver no ladrilho (12,12), você só precisará verificar entre os ladrilhos (6 , 6) e (18,18) para um total de aproximadamente 150 peças possíveis.). Certamente os blocos sob gravidade apenas caem e, portanto, você precisa apenas procurar o próximo bloco abaixo dele.
DampeS8N
Você acha que 16x16 é muito pequeno? Não seria difícil alterar o tamanho dos ladrilhos, pois qualquer coisa que faça referência a largura / altura é uma constante estática. Tudo o que eu teria que fazer é aumentá-los no Paint.NET, o que é bom porque adiciona mais detalhes.
30511 Ross
Você se importaria de compartilhar seu código de colisão? : /
ashes999

Respostas:

7

Sim, você está pensando corretamente. Você deve usar uma matriz 2D de blocos, pois isso permite indexar blocos por posição.

Block[,] level = new Block[width, height];

E como o jogador só pode colidir com as peças ao redor, o número de verificações de colisão que você precisa fazer é muito pequeno. Obviamente, isso depende do tamanho do jogador. A amostra do Platformer faz o seguinte:

int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{
    for (int x = leftTile; x <= rightTile; ++x)
    {
        // Handle collisions with the tile level[x,y] just like you were doing!
    }
}

Verifique a amostra se você ainda tiver algum problema.

David Gouveia
fonte
Este é um pequeno algoritmo muito bom, eu nem tinha ouvido falar da amostra de Platformer (eu deveria ter, mas afirmo ignorância). Obrigado!
Ross
@Ross Really? Você ficaria surpreso com a similaridade da sua solução com a amostra. :-) Menos a parte da lista, todo o resto é praticamente idêntico (cruze caixas delimitadoras, obtenha profundidade de interseção, resolva no menor eixo).
David Gouveia
11
Oh cara, eu apenas olhei para isso. >. <Gostaria de saber isso há 2 dias !! Bem, eu sou novo no XNA, mas me aprofundou nos gráficos 2D (apenas OpenGL, não muita programação de jogos). Acho que devo verificar mais recursos antes de começar a codificar.
Ross
1

Eu acho que minha resposta seria sua resposta! ;-)

Se você tiver a posição (e o tamanho) do jogador, poderá calcular os índices das peças adjacentes (que são as únicas a serem verificadas em detalhes). Dessa forma, deve ser irrelevante o tamanho do seu mapa, depende apenas do tamanho real do seu jogador, resultando em mais peças possíveis para serem verificadas.

Talvez verifique o tutorial sobre colisões em riemers.net, se você ainda não o fez.

Príncipe Charles
fonte
Eu ouvi falar de Riemer, mas nunca cheguei a procurar, obrigado!
Ross
1

Ao lidar com um grande número de colisões, geralmente você deseja adotar uma estrutura mais avançada , como um Quadtree ou Hashmap para verificar essas colisões.

Como as peças são estáticas, sugiro o uso de um Quadtree. Uma árvore quad é composta de quads. Cada quad é composto de quatro retângulos e cada um desses retângulos são quads. Isso continua recursivamente até um tamanho especificado. Cada quad pode conter uma lista de peças que habitam essa área da tela. Dessa forma, quando você estiver verificando colisões, poderá

  1. Restrinja as verificações àquelas próximas
  2. Restringir verificações apenas aos objetos que estão se movendo

Agora, se você não quiser nem olhar para as telhas fora da tela, poderá fazer algo como

public bool CheckCollision(myPosition) {
    if(quadNodes.Count > 0) {
        // This is not a leaf, keep checking
        foreach(Quad node in quadNodes) {
            if(node.Position is insideViewport && nearPlayer)
                // Continue recursion
            }
        }
    }
    else {
        // This is a leaf, do checks
        foreach(Tile tile in tileList) {
            if(collision)
                return true;
        }
        return false;
    }
}
Mike Cluck
fonte
Hmm, eu ouvi falar de Octrees na detecção de colisão 3D, mas nunca vi uma Estrutura de dados avançada sendo usada para detecção de colisão 2D. Muito obrigado!
Ross
11
Como o jogo dele (assumindo Terraria) é composto de peças uniformemente espaçadas, o uso de uma grade seria muito mais fácil e rápido do que um quadtree. Um quadtree funciona melhor em mundos mais complexos, onde seria difícil ajustar uma grade e tudo tem tamanho arbitrário.
David Gouveia
11
Você está certo se for um jogo puramente baseado em grade, mesmo com o tamanho dos personagens. Eu sei que em Terraria eles também têm monstros que não se encaixam prontamente em um formato de grade. Eu estava correndo sob a suposição de que o mundo básico é feito de ladrilhos, mas outros objetos seriam diferentes e eles poderiam armazená-los em uma estrutura semelhante para evitar a construção de outro. Suponho que eles poderiam usar uma grade para blocos e, em seguida, uma estrutura diferente (se necessário) para outros objetos arbitrários.
quer
11
Isso é o que eu estava prestes a sugerir :) A grade deve ser usada para lidar com colisões com o terreno, enquanto um quadtree pode ser usado para lidar com colisões entre objetos.
David Gouveia
Verdade. No momento, todas as caixas delimitadoras têm 2 ^ dimensões de potência. Isso facilita muito a detecção de colisões. Uma grade atenderia às minhas necessidades por enquanto.
Ross