Seleção eficiente de objetos fora da tela em um mapa 2D de cima para baixo

8

Sei que a eficiência é fundamental na programação de jogos e já tive algumas experiências em renderizar um "mapa" anteriormente, mas provavelmente não da melhor maneira.

Para um jogo 2D TopDown: (simplesmente renderize as texturas / peças do mundo, nada mais)

Digamos que você tenha um mapa de 1000 x 1000 (blocos ou qualquer outra coisa). Se o bloco não estiver na vista da câmera, não deverá ser renderizado - é simples assim. Não há necessidade de renderizar um bloco que não será visto. Mas como você tem objetos de 1000 x 1000 em seu mapa, ou talvez menos, provavelmente não deseja percorrer todos os blocos de 1000 * 1000 apenas para ver se eles devem ser renderizados ou não.

Pergunta: Qual é a melhor maneira de implementar essa eficiência? Para que "mais rápido / mais rápido" possa determinar quais blocos devem ser renderizados?

Além disso, não estou construindo meu jogo em torno de peças renderizadas com um SpriteBatch, portanto não há retângulos, as formas podem ter tamanhos diferentes e ter vários pontos, digamos, um objeto curvo de 10 pontos e uma textura dentro dessa forma;

Pergunta: Como você determina se esse tipo de objeto está "dentro" da vista da câmera?

É fácil com um retângulo de 48x48, apenas veja se X + Width ou Y + Height estão na vista da câmera. Diferente com vários pontos.

Simplificando, como gerenciar o código e os dados de maneira eficiente, para não precisar executar / repetir um milhão de objetos ao mesmo tempo.

Deukalion
fonte

Respostas:

6

Quanto aos objetos complexos , acho que a melhor maneira é reduzi-los aos retângulos circundantes e verificar se esse retângulo está dentro da janela de visualização. Mesmo se você renderizar uma textura que não é realmente visível (por causa de sua forma), ela ainda será provavelmente mais rápida do que executar um algoritmo de detecção mais complexo.

Quanto ao manuseio eficiente de mapas grandes, você deve subdividi-lo em maior escala, digamos 10x10. Então você verifica o cruzamento da sua janela de exibição. Na pior das hipóteses, atinge 4 essas 'regiões', o que resultará em (100x100) * 4 = 40K objetos. Este é um exemplo simplificado. Para um uso real, você deve considerar a estrutura Quadtree, que é especialmente eficiente para essas subdivisões e detecção de colisões (a verificação da visibilidade da viewport é basicamente a verificação de colisão entre a viewport e o sprite).

Petr Abdulin
fonte
Usar um Quadtree para blocos de mapa é um exagero ... já que você pode apenas calcular os índices adequados de blocos que precisam ser renderizados. Além disso, as regiões são mais simples e eu recomendaria usá-las para a primeira rodada de otimizações. Isso ajudará a entender e usar os quadrees mais tarde :) +1.
Liosan
@ Liosan, não está claro se essas 'peças' são do mesmo tamanho, caso contrário, a solução seria bastante trivial, é claro.
precisa
você está certo, Deukalion até escreveu um comentário para uma resposta diferente dizendo 'E um ladrilho nem sempre é exatamente do mesmo tamanho'.
Liosan #
O QuadTree funciona mesmo com tamanhos exatos de região? Toda região não deve ser do tamanho de um retângulo, porque o objeto dentro do retângulo não é para que não faça um retângulo. Portanto, NÃO será uma grade digitada de 1024x1024 pixels que é renderizada; sua forma pode ser muito ortodoxa.
precisa
Bem, acho que não (eu realmente não usei quadtrees), mas isso realmente não importa se você pode colocar tudo na região do retângulo ao redor. De qualquer forma, se quadtree não for apropriado para sua tarefa por algum motivo, você provavelmente precisará usar uma abordagem semelhante.
precisa
3

Quando você tem muitos objetos móveis, deve armazená-los por suas coordenadas em uma estrutura de árvore multidimensional. Dessa forma, você pode obter com eficiência uma lista de todos os objetos que estão dentro de um determinado retângulo. Você pode até ordená-los por suas coordenadas x ou y, o que é importante para a ordem do desenho quando sprites de objetos se sobrepõem.

Isso também será muito útil para a detecção de colisões.

Veja o artigo da Wikipedia sobre árvores kd para detalhes.

Quando as árvores 2D são muito complicadas para você, também existe uma alternativa mais fácil, mas não muito menos eficaz: armazene os objetos como filhos dos ladrilhos. Quando você move um objeto, você o remove da lista de objetos de seu bloco antigo e o coloca na lista de objetos do novo. Quando você desenha os objetos, itera novamente sobre os blocos na viewport e recupera seus objetos. Depois, você as classifica por coordenadas y e as desenha.

Philipp
fonte
1

Não sei se é a melhor maneira, mas é assim que eu aprendo a fazê-lo:

você tem uma matriz bidimensional de "blocos"

public Tile tilemap[][];

e você decide a posição da "câmera" com um Vector2, você renderiza apenas o que está dentro da cena, o grande retângulo é o que você pode ver na tela, é inútil desenhar o resto da cena.

Agora você precisa obter as compensações, supondo que você queira que sua câmera esteja no centro da cena:

offsetX = (graphics().width() / 2 - Math.round(cam.Position().X));
offsetX = Math.min(offsetX, 0);
offsetX = Math.max(offsetX, graphics().width() / 2 - mapWidth);
offsetY = (graphics().height()) / 2 - Math.round(cam.getPosition().Y);
offsetY = Math.min(offsetY, 0);
offsetY = Math.max((graphics().height() / 2 - mapHeight), offsetY);

agora, em qual parte da matriz os blocos visíveis começam e terminam?

firstTileX = pixelsToTiles(-offsetX);

lastTileX = firstTileX + pixelsToTiles(graphics().width());

firstTileY = pixelsToTiles(-offsetY);

lastTileY = firstTileY + pixelsToTiles(graphics().height());

int pixelsToTiles(int pixels) {
    return (int) Math.floor((float) pixels / Tile.getHeight());
}

e no seu método de desenho, basta percorrer a parte visível da matriz:

   for (int x = firstTileX; x < lastTileX; x++) {
        for (int y = firstTileY; y < lastTileY; y++) {
              Vector2 position = new Vector2(tilesToPixelsX(x) + offsetX,
                        tilesToPixelsY(y) + offsetY);
              tilemap[x][y].Draw(surf, position);
        }
    }
riktothepast
fonte
11
Sim, mas o ladrilho foi um exemplo para simplificar as coisas. Eu já escrevi que entendo o processo de determinar se um objeto já está em "visualização" com formato de retângulo / título, não com formas mais avançadas que possuem vários pontos. Além disso, eu estava procurando por algo que me "não" passasse por todos os blocos durante cada método Update () no XNA. Se eu tenho um mapa "GRANDE", com cerca de 10000 objetos (formas de 3 pontos e mais), não é esse o caminho. Cada atualização eu tenho que executar um loop de 10000 atualizações e tantos cálculos. Eu não uso azulejos e isso não é eficiente; Eu estive lá.
Deucalião
E um bloco nem sempre é exatamente do mesmo tamanho, então também não posso fazer isso. Eu não uso retângulos.
precisa
Simplificando: eu só quero percorrer objetos que DEVEM ser renderizados, não percorrer objetos que não deveriam.
Deukalion
O código do @Deukalion Riktothepast apenas passa pelos blocos que devem aparecer dentro da caixa delimitadora da tela (embora isso não esteja muito claro). A mesma técnica básica pode ser usada para percorrer qualquer retângulo de blocos dentro de um determinado conjunto de coordenadas.
DampeS8N
0

Você pode ter um bitmap que é a cena inteira, mas não é exibido. E então, um bitmap da camada de câmera do tamanho da tela exibido, que apenas desenha a cena inteira, mas apenas a parte que precisa ser mostrada.

mrall
fonte