Menggabungkan Banyak Colliders Kecil menjadi Yang Lebih Besar

13

Saya membuat game menggunakan ubin-peta yang terbuat dari ribuan kotak kotak. Saat ini, setiap kotak memiliki collider persegi untuk memeriksa tabrakan.

masukkan deskripsi gambar di sini

Namun, dengan ribuan blok kecil, memeriksa semuanya untuk tabrakan tidak efisien. Jika saya tahu tilemap akan terlihat seperti ini sebelumnya, saya bisa saja menggunakan 3 atau 4 colliders besar daripada ribuan yang kecil:

masukkan deskripsi gambar di sini

Apakah ada semacam algoritma standar untuk menggabungkan banyak ubin kecil yang berdekatan menjadi yang besar secara maksimal? Jika demikian, dapatkah seseorang menggambarkannya di sini, atau merujuk ke literatur tentang algoritma seperti itu?

Sebagai alternatif, mungkin pra-pemrosesan ubin colliders dengan cara ini adalah pendekatan yang sepenuhnya salah. Jika demikian, apa yang benar untuk menangani efisiensi jumlah colliders yang sangat besar?

Craig Innes
sumber
Apakah Anda berencana memiliki medan yang dapat dirusak?
jgallant
@ Jon. Saya tidak mempertimbangkan ini. Saya membayangkan membiarkan destructibility akan membuat masalah lebih sulit (karena salah satu colliders kecil mungkin dihancurkan, artinya colliders gabungan besar perlu dihitung ulang, kan?)
Craig Innes
Iya. Inilah sebabnya saya bertanya. Biasanya, Anda akan menggabungkan semua medan Anda menjadi jaring. Jika Anda berencana membiarkan medan Anda dapat dirusak, ada metode alternatif yang dapat Anda gunakan, yang menetapkan colliders hanya pada blok luar. Anda akan menghitung terlebih dahulu blok apa yang merupakan "blok tepi" dan kemudian menetapkan blok tersebut dengan collider yang dapat dikumpulkan. ( jgallant.com/images/uranus/chunk.png - Gambar sudah tua dan tidak sempurna, tetapi menunjukkan tekniknya) Apa yang Anda gunakan untuk mesin game / platform?
jgallant
@ Jon Saya menggunakan Unity sebagai mesin permainan saya, dengan komponen BoxCollider2D untuk tabrakan ubin. Saya tidak menyebutkan platform spesifik saya karena saya pikir itu mungkin lebih bermanfaat untuk pertukaran dev game stack untuk mendapatkan jawaban yang lebih umum untuk masalah ini. Berkenaan dengan metode "blok tepi" Anda, dapatkah Anda mengirimkan jawaban dengan detail algoritma yang tepat untuk metode ini? Atau apakah Anda memiliki tautan ke sumber daya tentang teknik seperti itu?
Craig Innes
1
Saya memiliki implementasi Unity untuk ini, saya perlu waktu untuk menulis, karena tidak benar-benar dipotong dan kering. Saya sedang bekerja saat ini, dan kode sumbernya ada di rumah. Jika Anda bisa menunggu hingga malam ini untuk jawaban. Begini tampilannya: jgallant.com/images/landgen.gif
jgallant

Jawaban:

5

Saya menemukan algoritm ini berguna untuk mesin love2d ( bahasa 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

Berikut ikuti contoh love2d pada proyek saya saat ini. Merah Anda dapat melihat dinding saya bertabrakan.

masukkan deskripsi gambar di sini

dnk drone.vs.drones
sumber
Apakah ada versi C #? Apakah ada versi dengan komentar dokumentasi? Bisakah algoritma ini diadaptasi untuk 3D?
Aaron Franke
3

Jika Anda ingin membuat medan yang dapat dirusak, cara saya melakukan ini di Unity, adalah dengan hanya mengatur colliders di blok tepi dunia Anda. Jadi misalnya, inilah yang ingin Anda capai:

Blok hijau menunjukkan ubin yang mengandung collider

Semua blok hijau itu mengandung collider, dan sisanya tidak. Itu menghemat satu ton pada perhitungan. Jika Anda menghancurkan blok, Anda dapat mengaktifkan colliders pada blok yang berdekatan dengan mudah. Perlu diingat bahwa mengaktifkan / menonaktifkan collider adalah mahal dan harus dilakukan hemat.

Jadi, sumber daya Tile terlihat seperti ini:

Sumber Daya Ubin Dalam Persatuan

Ini adalah objek game standar, tetapi juga bisa dikumpulkan. Perhatikan juga bahwa kotak collider diatur untuk dinonaktifkan secara default. Kami hanya akan mengaktifkan jika itu adalah ubin tepi.

Jika Anda memuat dunia Anda secara statis, tidak perlu menyatukan ubin Anda. Anda bisa memuat semuanya dalam satu tembakan, menghitung jaraknya dari tepi, dan menerapkan collider jika diperlukan.

Jika Anda memuat secara dinamis, yang terbaik adalah menggunakan kolam ubin. Ini adalah contoh loop refresh saya yang diedit. Ini memuat ubin berdasarkan tampilan kamera saat ini:

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

Idealnya, saya akan menulis posting yang jauh lebih rinci, karena ada sedikit lebih banyak terjadi di belakang layar. Namun, ini dapat membantu Anda. Jika ada pertanyaan, jangan ragu untuk bertanya atau menghubungi saya.

jallan
sumber
Menerima jawaban dnkdrone karena lebih langsung menjawab pertanyaan awal yang diajukan. Namun, telah mengangkat jawaban ini karena memberikan arahan berharga menuju alternatif yang efisien
Craig Innes
@CraigInnes Tidak ada masalah man. Hanya ingin membantu. Poin tidak masalah :)
jgallant