Łączenie wielu małych zderzaków w większe


13

Tworzę grę za pomocą mapy kafelkowej złożonej z wielu tysięcy kwadratowych pól. W tej chwili każdy kwadrat ma kwadratowy zderzak do sprawdzania kolizji.

wprowadź opis zdjęcia tutaj

Jednak w przypadku wielu tysięcy małych bloków sprawdzanie ich pod kątem kolizji jest nieefektywne. Gdybym wiedział, że mapa tilem będzie z góry wyglądać tak, mógłbym po prostu użyć 3 lub 4 dużych zderzaków zamiast tysięcy małych:

wprowadź opis zdjęcia tutaj

Czy istnieje jakiś standardowy algorytm łączenia wielu sąsiadujących płytek w maksymalnie duże? Jeśli tak, czy ktoś mógłby to tutaj opisać lub wskazać literaturę na temat takich algorytmów?

Alternatywnie, być może wstępne przetwarzanie w ten sposób zderzaków płytek jest całkowicie niewłaściwe. Jeśli tak, to jaki jest właściwy sposób radzenia sobie z wydajnością bardzo dużej liczby zderzaczy?


Czy planujesz zniszczyć teren?
jgallant

@Jon. Nie zastanawiałem się nad tym. Wyobrażam sobie, że zezwolenie na zniszczenie znacznie utrudniłoby problem (ponieważ jeden z małych zderzaków może zostać zniszczony, co oznacza, że ​​duże połączone zderzaki musiałyby zostać ponownie obliczone, prawda?)
Craig Innes

Tak. Właśnie dlatego pytałem. Zazwyczaj łączysz cały swój teren w siatkę. Jeśli planujesz pozwolić na zniszczenie terenu, możesz zastosować alternatywną metodę, która ustawia zderzaki tylko na zewnętrznych blokach. Należy wstępnie obliczyć, które bloki są „blokami krawędzi”, a następnie przypisać te bloki zderzaczowi pulowemu. ( jgallant.com/images/uranus/chunk.png - Obraz jest stary i nie jest idealny, ale pokazuje technikę) Czego używasz do silnika / platformy gry?
jgallant

@Jon Używam Unity jako silnika gry z komponentami BoxCollider2D do kolizji płytek. Nie wspomniałem o mojej konkretnej platformie, ponieważ myślałem, że może być bardziej przydatna do wymiany stosów deweloperów gry, aby uzyskać bardziej ogólną odpowiedź na ten problem. Jeśli chodzi o metodę „bloków krawędzi”, czy mógłbyś przesłać odpowiedź z dokładnymi szczegółami algorytmu dla tej metody? Czy masz link do zasobów na temat takich technik?
Craig Innes,

1
Mam do tego implementację Unity, zajmie mi trochę czasu, aby napisać, ponieważ nie jest tak naprawdę wycięty i suchy. W tej chwili jestem w pracy, a kod źródłowy jest w domu. Jeśli możesz poczekać do dzisiejszej nocy na odpowiedź. Oto jak to wygląda: jgallant.com/images/landgen.gif
jgallant

Odpowiedzi:


5

Znalazłem użyteczny ten algorytm dla silnika love2d ( język 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

Oto przykład love2d z mojego obecnego projektu. Na czerwono widać moje zderzaki ścienne.

wprowadź opis zdjęcia tutaj


Czy jest wersja C #? Czy jest wersja z komentarzami do dokumentacji? Czy ten algorytm można dostosować do 3D?
Aaron Franke,

3

Jeśli chcesz stworzyć zniszczalny teren, tak jak ja to zrobiłem w Unity, ustawianie zderzaków tylko na skrajnych blokach twojego świata. Na przykład to, co chciałbyś osiągnąć:

Zielone bloki wskazują płytki zawierające zderzacz

Wszystkie te zielone bloki zawierają zderzak, a reszta nie. To oszczędza mnóstwo obliczeń. Jeśli zniszczysz blok, możesz dość łatwo aktywować zderzaki na sąsiednich blokach. Pamiętaj, że aktywacja / dezaktywacja zderzaka jest kosztowna i powinna być wykonywana oszczędnie.

Zasób kafelków wygląda następująco:

Płytka zasobów w jedności

Jest to standardowy obiekt gry, ale można go również pulować. Zauważ również, że moduł zderzający jest domyślnie wyłączony. Aktywowalibyśmy się tylko, jeśli jest to kafelek krawędzi.

Jeśli ładujesz swój świat statycznie, nie ma potrzeby łączenia płytek. Możesz po prostu załadować je wszystkie w jednym ujęciu, obliczyć ich odległość od krawędzi i w razie potrzeby zastosować zderzak.

Jeśli ładujesz się dynamicznie, najlepiej użyć puli kafelków. Oto edytowany przykład mojej pętli odświeżania. Ładuje kafelki na podstawie bieżącego widoku kamery:

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

Idealnie napisałbym o wiele bardziej szczegółowy post, ponieważ za kulisami dzieje się o wiele więcej. Może ci to jednak pomóc. W razie pytań możesz zapytać lub skontaktować się ze mną.


Zaakceptowano odpowiedź dnkdrone, ponieważ bardziej bezpośrednio odpowiada na postawione pierwotne pytanie. Jednak nie upvoted tę odpowiedź, ponieważ daje cenne kierunku skutecznej alternatywy
Craig Innes

@CraigInnes Żadnych problemów, człowieku. Po prostu lubię pomagać. Punkty nie mają znaczenia :)
jgallant
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.