Combinando muchos colisionadores pequeños en unos más grandes

13

Estoy creando un juego usando un mapa de mosaico hecho de miles de cuadrados de cuadrícula. Por el momento, cada cuadrado tiene un colisionador cuadrado para verificar las colisiones.

ingrese la descripción de la imagen aquí

Sin embargo, con muchos miles de pequeños bloques, verificarlos en busca de colisiones es ineficiente. Si hubiera sabido que el tilemap se vería así de antemano, podría haber usado 3 o 4 colisionadores grandes en lugar de miles de pequeños:

ingrese la descripción de la imagen aquí

¿Existe algún tipo de algoritmo estándar para combinar muchos mosaicos adyacentes pequeños en los más grandes? Si es así, ¿podría alguien describirlo aquí o señalar literatura sobre tales algoritmos?

Alternativamente, tal vez preprocesar los colisionadores de mosaico de esta manera es un enfoque completamente incorrecto. Si es así, ¿cuál es el correcto para lidiar con la eficiencia de un número extremadamente grande de colisionadores?

Craig Innes
fuente
¿Estás planeando destruir el terreno?
jgallant
@Jon. No lo había considerado. Me imagino que permitir la destructibilidad haría que el problema fuera mucho más difícil (porque uno de los pequeños colisionadores puede ser destruido, lo que significa que los colisionadores grandes combinados tendrían que volver a calcularse, ¿verdad?)
Craig Innes
Si. Por eso estaba preguntando. Por lo general, combinarías todo tu terreno en una malla. Si planea permitir que su terreno sea destructible, hay un método alternativo que puede usar, que establece colisionadores solo en los bloques exteriores. Pre-calcularía qué bloques son "bloques de borde" y luego asignaría esos bloques con un colisionador agrupable. ( jgallant.com/images/uranus/chunk.png - La imagen es antigua y no perfecta, pero demuestra la técnica) ¿Qué estás usando para un motor / plataforma de juego?
jgallant
@ Jon Estoy usando Unity como mi motor de juego, con componentes BoxCollider2D para colisiones de fichas. No mencioné mi plataforma específica, ya que pensé que podría ser más útil para el intercambio de la pila de desarrolladores de juegos para obtener una respuesta más general a este problema. Con respecto a su método de "bloques de borde", ¿podría enviar una respuesta con detalles precisos del algoritmo para este método? ¿O tiene un enlace a recursos sobre tales técnicas?
Craig Innes
1
Tengo una implementación de Unity para esto, me llevará algún tiempo hacer una redacción, ya que en realidad no está cortada y seca. En este momento estoy en el trabajo y el código fuente está en casa. Si puedes esperar hasta esta noche para una respuesta. Así es como se ve: jgallant.com/images/landgen.gif
jgallant

Respuestas:

5

Encontré útil este algoritmo para el motor love2d ( lenguaje 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

Aquí sigue el ejemplo de love2d en mi proyecto actual. En rojo puedes ver mis colisionadores de pared.

ingrese la descripción de la imagen aquí

dnk drone.vs.drones
fuente
¿Hay una versión de C #? ¿Hay una versión con comentarios de documentación? ¿Se puede adaptar este algoritmo para 3D?
Aaron Franke el
3

Si estás buscando crear un terreno destructible, la forma en que lo hice en Unity es solo colocar colisionadores en los bloques de borde de tu mundo. Entonces, por ejemplo, esto es lo que le gustaría lograr:

Los bloques verdes indican las fichas que contienen un colisionador

Todos esos bloques verdes contienen un colisionador, y el resto no. Eso ahorra una tonelada en cálculos. Si destruye un bloque, puede activar los colisionadores en bloques adyacentes con bastante facilidad. Tenga en cuenta que activar / desactivar un colisionador es costoso y debe hacerse con moderación.

Entonces, el recurso Tile se ve así:

Recurso de mosaico en la unidad

Es un objeto de juego estándar, pero también se puede agrupar. Observe también que el colisionador de cuadros está configurado para deshabilitarse de manera predeterminada. Solo se activaría si se trata de un mosaico de borde.

Si está cargando estáticamente su mundo, no hay necesidad de agrupar sus fichas. Puede cargarlos todos de una sola vez, calcular su distancia desde el borde y aplicar un colisionador si es necesario.

Si está cargando dinámicamente, es mejor usar un grupo de mosaicos. Aquí hay un ejemplo editado de mi ciclo de actualización. Carga mosaicos basados ​​en la vista actual de la cámara:

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, escribiría una publicación mucho más detallada, ya que hay bastante más detrás de escena. Sin embargo, esto puede ayudarte. Si hay preguntas, no dude en preguntarme o contactarme.

jgallant
fuente
La respuesta de dnkdrone aceptada, ya que responde más directamente a la pregunta original planteada. Sin embargo, he votado a favor de esta respuesta, ya que da una valiosa dirección hacia una alternativa eficiente
Craig Innes
@ CraigInnes No hay problemas hombre. Solo me gusta ayudar. Los puntos no importan :)
jgallant