Combinando muitos coletores pequenos em outros maiores

13

Estou criando um jogo usando um mapa de peças composto por muitos milhares de quadrados da grade. No momento, cada quadrado possui um colisor para verificar colisões.

insira a descrição da imagem aqui

No entanto, com muitos milhares de blocos minúsculos, verificar todos por colisões é ineficiente. Se eu soubesse que o tilemap ficaria assim com antecedência, poderia ter usado apenas 3 ou 4 grandes colisores em vez de milhares de minúsculos:

insira a descrição da imagem aqui

Existe algum tipo de algoritmo padrão para combinar muitos blocos adjacentes pequenos em blocos maximamente grandes? Nesse caso, alguém poderia descrevê-lo aqui ou apontar para a literatura sobre tais algoritmos?

Como alternativa, talvez o pré-processamento dos coletores de ladrilhos dessa maneira seja completamente a abordagem errada. Em caso afirmativo, qual é o correto para lidar com a eficiência de um número extremamente grande de coletores?

Craig Innes
fonte
Você está planejando ter o terreno destrutível?
jgallant
@Jon. Eu não tinha considerado isso. Imagino permitindo destructibility faria o problema significativamente mais difícil (porque um dos pequenos aceleradores podem ser destruídos, ou seja, os grandes combinado colliders teria de ser recalculado, né?)
Craig Innes
Sim. É por isso que eu estava perguntando. Normalmente, você combinaria todo o seu terreno em uma malha. Se você planeja permitir que seu terreno seja destrutível, existe um método alternativo que pode ser usado, que define coletores apenas nos blocos externos. Você pré-calcularia quais blocos são "blocos de borda" e depois atribuiria esses blocos com um colisor agrupável. ( jgallant.com/images/uranus/chunk.png - A imagem é antiga e não é perfeita, mas demonstra a técnica) O que você está usando para um mecanismo / plataforma de jogo?
jgallant
@ Jon Estou usando o Unity como meu mecanismo de jogo, com componentes BoxCollider2D para colisões de blocos. Eu não mencionei minha plataforma específica, pois achei que seria mais útil para a troca de pilhas de desenvolvedores de jogos para obter uma resposta mais geral para esse problema. No que diz respeito ao seu método "edge blocks", você poderia enviar uma resposta com detalhes precisos do algoritmo para esse método? Ou você tem um link para recursos sobre essas técnicas?
Craig Innes
1
Eu tenho uma implementação do Unity para isso, levarei algum tempo para escrever, pois não é realmente fácil. Estou no trabalho no momento e o código fonte está em casa. Se você pode esperar até hoje à noite para obter uma resposta. Aqui está o que parece: jgallant.com/images/landgen.gif
jgallant 14/15

Respostas:

5

Achei útil esse algoritmo para o mecanismo love2d ( linguagem lua )

https://love2d.org/wiki/TileMerging

-- map_width and map_height are the dimensions of the map
-- is_wall_f checks if a tile is a wall

local rectangles = {} -- Each rectangle covers a grid of wall tiles

for x = 0, map_width - 1 do
    local start_y
    local end_y

    for y = 0, map_height - 1 do
        if is_wall_f(x, y) then
            if not start_y then
                start_y = y
            end
            end_y = y
        elseif start_y then
            local overlaps = {}
            for _, r in ipairs(rectangles) do
                if (r.end_x == x - 1)
                  and (start_y <= r.start_y)
                  and (end_y >= r.end_y) then
                    table.insert(overlaps, r)
                end
            end
            table.sort(
                overlaps,
                function (a, b)
                    return a.start_y < b.start_y
                end
            )

            for _, r in ipairs(overlaps) do
                if start_y < r.start_y then
                    local new_rect = {
                        start_x = x,
                        start_y = start_y,
                        end_x = x,
                        end_y = r.start_y - 1
                    }
                    table.insert(rectangles, new_rect)
                    start_y = r.start_y
                end

                if start_y == r.start_y then
                    r.end_x = r.end_x + 1

                    if end_y == r.end_y then
                        start_y = nil
                        end_y = nil
                    elseif end_y > r.end_y then
                        start_y = r.end_y + 1
                    end
                end
            end

            if start_y then
                local new_rect = {
                    start_x = x,
                    start_y = start_y,
                    end_x = x,
                    end_y = end_y
                }
                table.insert(rectangles, new_rect)

                start_y = nil
                end_y = nil
            end
        end
    end

    if start_y then
        local new_rect = {
            start_x = x,
            start_y = start_y,
            end_x = x,
            end_y = end_y
        }
        table.insert(rectangles, new_rect)

        start_y = nil
        end_y = nil
    end
end
Here's how the rectangles would be used for physics.
-- Use contents of rectangles to create physics bodies
-- phys_world is the world, wall_rects is the list of...
-- wall rectangles

for _, r in ipairs(rectangles) do
    local start_x = r.start_x * TILE_SIZE
    local start_y = r.start_y * TILE_SIZE
    local width = (r.end_x - r.start_x + 1) * TILE_SIZE
    local height = (r.end_y - r.start_y + 1) * TILE_SIZE

    local x = start_x + (width / 2)
    local y = start_y + (height / 2)

    local body = love.physics.newBody(phys_world, x, y, 0, 0)
    local shape = love.physics.newRectangleShape(body, 0, 0,
      width, height)

    shape:setFriction(0)

    table.insert(wall_rects, {body = body, shape = shape})
end

Aqui segue o exemplo do love2d no meu projeto atual. Em vermelho, você pode ver meus coletores de parede.

insira a descrição da imagem aqui

dnk drone.vs.drones
fonte
Existe uma versão c #? Existe uma versão com comentários da documentação? Esse algoritmo pode ser adaptado para 3D?
Aaron Franke
3

Se você deseja criar terrenos destrutíveis, a maneira como fiz isso no Unity é colocar apenas coletores nos limites do seu mundo. Então, por exemplo, é isso que você gostaria de realizar:

Blocos verdes indicam os blocos que contêm um colisor

Todos esses blocos verdes contêm um colisor e o restante não. Isso economiza muito em cálculos. Se você destruir um bloco, poderá ativar os colisores em blocos adjacentes com bastante facilidade. Lembre-se de que ativar / desativar um colisor é caro e deve ser feito com moderação.

Portanto, o recurso Tile é assim:

Recurso de bloco na unidade

É um objeto de jogo padrão, mas também pode ser agrupado. Observe também que o colisor de caixa está definido para ser desativado por padrão. Somente ativaríamos se for um bloco de borda.

Se você está carregando estaticamente seu mundo, não há necessidade de juntar seus ladrilhos. Você pode carregar todos eles de uma só vez, calcular a distância da borda e aplicar um colisor, se necessário.

Se você estiver carregando dinamicamente, é melhor usar um pool de blocos. Aqui está um exemplo editado do meu loop de atualização. Carrega blocos com base na visualização atual da câmera:

public void Refresh(Rect view)
{       
    //Each Tile in the world uses 1 Unity Unit
    //Based on the passed in Rect, we calc the start and end X/Y values of the tiles presently on screen        
    int startx = view.x < 0 ? (int)(view.x + (-view.x % (1)) - 1) : (int)(view.x - (view.x % (1)));
    int starty = view.y < 0 ? (int)(view.y + (-view.y % (1)) - 1) : (int)(view.y - (view.y % (1)));

    int endx = startx + (int)(view.width);
    int endy = starty - (int)(view.height);

    int width = endx - startx;
    int height = starty - endy;

    //Create a disposable hashset to store the tiles that are currently in view
    HashSet<Tile> InCurrentView = new HashSet<Tile>();

    //Loop through all the visible tiles
    for (int i = startx; i <= endx; i += 1)
    {
        for (int j = starty; j >= endy; j -= 1)
        {
            int x = i - startx;
            int y = starty - j;

            if (j > 0 && j < Height)
            {
                //Get Tile (I wrap my world, that is why I have this mod here)
                Tile tile = Blocks[Helper.mod(i, Width), j];

                //Add tile to the current view
                InCurrentView.Add(tile);

                //Load tile if needed
                if (!tile.Blank)
                {
                    if (!LoadedTiles.Contains(tile))
                    {                           
                        if (TilePool.AvailableCount > 0)
                        {
                            //Grab a tile from the pool
                            Pool<PoolableGameObject>.Node node = TilePool.Get();

                            //Disable the collider if we are not at the edge
                            if (tile.EdgeDistance != 1)
                                node.Item.GO.GetComponent<BoxCollider2D>().enabled = false;

                            //Update tile rendering details
                            node.Item.Set(tile, new Vector2(i, j), DirtSprites[tile.TextureID], tile.Collidable, tile.Blank);
                            tile.PoolableGameObject = node;
                            node.Item.Refresh(tile);

                            //Tile is now loaded, add to LoadedTiles hashset
                            LoadedTiles.Add(tile);

                            //if Tile is edge block, then we enable the collider
                            if (tile.Collidable && tile.EdgeDistance == 1)
                                node.Item.GO.GetComponent<BoxCollider2D>().enabled = true;
                        }
                    }                       
                }                  
            }
        }
    }

    //Get a list of tiles that are no longer in the view
    HashSet<Tile> ToRemove = new HashSet<Tile>();
    foreach (Tile tile in LoadedTiles)
    {
        if (!InCurrentView.Contains(tile))
        {
            ToRemove.Add(tile);
        }
    }

    //Return these tiles to the Pool 
    //this would be the simplest form of cleanup -- Ideally you would do this based on the distance of the tile from the viewport
    foreach (Tile tile in ToRemove)
    {
        LoadedTiles.Remove(tile);
        tile.PoolableGameObject.Item.GO.GetComponent<BoxCollider2D>().enabled = false;
        tile.PoolableGameObject.Item.GO.transform.position = new Vector2(Int32.MinValue, Int32.MinValue);
        TilePool.Return(tile.PoolableGameObject);            
    }

    LastView = view;
}

Idealmente, eu escreveria um post muito mais detalhado, pois há muito mais nos bastidores. No entanto, isso pode ajudá-lo. Se houver perguntas, não hesite em perguntar ou entrar em contato comigo.

jgallant
fonte
A resposta do dnkdrone aceita, pois responde mais diretamente à pergunta original colocada. No entanto, ter upvoted esta resposta, pois dá sentido valiosa para uma alternativa eficiente
Craig Innes
@CraigInnes Sem problemas cara. Apenas gostaria de ajudar. Os pontos não importam :)
jgallant 15/10