Kombinieren vieler kleiner Collider zu größeren

13

Ich erstelle ein Spiel mit einer Kachelkarte, die aus Tausenden von Gitterfeldern besteht. Derzeit ist auf jedem Quadrat ein Rechteckcollider zum Überprüfen von Kollisionen vorhanden.

Bildbeschreibung hier eingeben

Bei vielen tausend winzigen Blöcken ist es jedoch ineffizient, alle auf Kollisionen zu überprüfen. Wenn ich im Voraus gewusst hätte, dass die Tilemap so aussehen würde, hätte ich einfach 3 oder 4 große Collider anstelle von Tausenden von kleinen verwenden können:

Bildbeschreibung hier eingeben

Gibt es eine Art Standardalgorithmus zum Kombinieren vieler kleiner benachbarter Kacheln zu maximal großen? Wenn ja, könnte es hier jemand beschreiben oder auf Literatur zu solchen Algorithmen verweisen?

Alternativ ist die Vorverarbeitung der Kachelcollider auf diese Weise möglicherweise der völlig falsche Ansatz. Wenn ja, welche ist die richtige, um mit der Effizienz einer extrem großen Anzahl von Collidern umzugehen?

Craig Innes
quelle
Planen Sie, das Gelände zerstörbar zu machen?
jgallant
@ Jon. Das hatte ich nicht bedacht. Ich stelle mir vor, dass das Problem durch das Zulassen der Zerstörbarkeit erheblich schwieriger wird (weil einer der kleinen Collider zerstört werden könnte, was bedeutet, dass die großen kombinierten Collider neu berechnet werden müssten, oder?)
Craig Innes
Ja. Deshalb habe ich gefragt. Normalerweise kombinieren Sie Ihr gesamtes Terrain zu einem Netz. Wenn Sie vorhaben, Ihr Gelände zerstörbar zu machen, können Sie eine alternative Methode verwenden, mit der Kollider nur für die äußeren Blöcke festgelegt werden. Sie würden vorausberechnen, welche Blöcke "Kantenblöcke" sind, und diese Blöcke dann mit einem Pool-Collider zuweisen. ( jgallant.com/images/uranus/chunk.png - Bild ist alt und nicht perfekt, zeigt aber die Technik) Was benutzt du für eine Game Engine / Plattform?
Jgallant
@Jon Ich verwende Unity als Spiel-Engine mit BoxCollider2D-Komponenten für Kachelkollisionen. Ich habe meine spezielle Plattform nicht erwähnt, da ich dachte, dass sie für den Austausch von Spielentwicklungsstapeln von größerem Nutzen sein könnte, um eine allgemeinere Antwort auf dieses Problem zu erhalten. Könnten Sie in Bezug auf Ihre "Kantenblöcke" -Methode eine Antwort mit genauen Details des Algorithmus für diese Methode einreichen? Oder haben Sie einen Link zu Ressourcen zu solchen Techniken?
Craig Innes
1
Ich habe eine Unity-Implementierung dafür, es wird einige Zeit dauern, bis ich sie geschrieben habe, da sie nicht wirklich geschnitten und trocken ist. Ich bin gerade auf der Arbeit und der Quellcode ist zu Hause. Wenn Sie bis heute Abend auf eine Antwort warten können. So sieht es aus: jgallant.com/images/landgen.gif
jgallant

Antworten:

5

Ich fand diesen Algorithmus nützlich für die love2d Engine ( lua language )

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

Hier folgt das love2d Beispiel zu meinem aktuellen Projekt. In rot sehen Sie meine Wandcollider.

Bildbeschreibung hier eingeben

dnk drone.vs.drones
quelle
Gibt es eine C # -Version? Gibt es eine Version mit Dokumentationskommentaren? Kann dieser Algorithmus für 3D angepasst werden?
Aaron Franke
3

Wenn Sie zerstörbares Terrain erschaffen möchten, besteht meine Vorgehensweise in Unity darin, Collider nur an den Randblöcken Ihrer Welt zu platzieren. So möchten Sie zum Beispiel Folgendes erreichen:

Grüne Blöcke kennzeichnen die Kacheln, die einen Collider enthalten

Alle diese grünen Blöcke enthalten einen Collider, der Rest nicht. Das spart eine Menge Rechenaufwand. Wenn Sie einen Block zerstören, können Sie die Collider auf benachbarten Blöcken ziemlich einfach aktivieren. Denken Sie daran, dass das Aktivieren / Deaktivieren eines Colliders teuer ist und sparsam erfolgen sollte.

Die Tile-Ressource sieht also folgendermaßen aus:

Kachelressource in Einheit

Es ist ein Standard-Spielobjekt, aber es kann auch gepoolt werden. Beachten Sie auch, dass der Box-Collider standardmäßig deaktiviert ist. Wir würden nur aktivieren, wenn es sich um ein Randplättchen handelt.

Wenn Sie Ihre Welt statisch laden, müssen Sie Ihre Kacheln nicht bündeln. Sie können sie alle auf einmal laden, ihren Abstand von der Kante berechnen und bei Bedarf einen Collider anwenden.

Wenn Sie dynamisch laden, empfiehlt es sich, einen Kachelpool zu verwenden. Hier ist ein bearbeitetes Beispiel für meine Aktualisierungsschleife. Es werden Kacheln basierend auf der aktuellen Kameraansicht geladen:

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;
}

Im Idealfall würde ich einen viel ausführlicheren Beitrag verfassen, da sich hinter den Kulissen einiges mehr abspielt. Dies kann Ihnen jedoch helfen. Bei Fragen stehe ich Ihnen gerne zur Verfügung.

jgallant
quelle
Akzeptierte die Antwort von dnkdrone, da es die ursprüngliche gestellte Frage direkter beantwortet. Habe diese Antwort jedoch positiv bewertet, da sie wertvolle Hinweise für eine effiziente Alternative gibt
Craig Innes,
@CraigInnes Keine Probleme, Mann. Ich helfe nur gerne aus. Punkte sind egal :)
jgallant