Deteksi tabrakan berbasis Tile yang efisien untuk banyak kotak?

9

Saat ini saya sedang mengerjakan sendiri permainan berbasis ubin (pikirkan Terraria, tapi kurang fantastik (saya pikir itu sebuah kata? Maaf jika tidak)).

Ngomong-ngomong, saat ini saya memiliki pendeteksian tabrakan (untuk kasus sudut!) Yang merupakan langkah besar bagi saya. Ada sesuatu yang sangat memuaskan melihat sprite tidak berjalan melalui blok. Tapi kemudian saya punya ide untuk benchmark. Ide buruk.

1.000 kotak, tidak ada masalah. 10.000 kotak, untuk 3 karakter agak lamban. 100.000 kotak (peta sangat besar), untuk 3 karakter tidak dapat dimainkan.

Saya mengalami masalah di mana saya tidak ingin mempertimbangkan blok yang terlalu jauh dari pemain, karakter, item, dll., Tetapi saya tidak ingin memuat yang keluar dari memori terus-menerus.

Inilah algoritma saya sejauh ini, jangan ragu untuk mengkritik.

foreach (Block in level)
{
    if (distance from block to player > a specified amount)
        ignore this block;
    else
    {
        get the intersection depth between the two bounding boxes
        if (depth of intersection != Zero-vector)
        {
            check y size vs x size
            resolve on smallest axis
        }
    }
}

Seperti yang akan Anda perhatikan, ketika ukuran level semakin besar, Urutan algoritma ini tumbuh sebesar N blok. Saya bahkan tidak ingin mempertimbangkan blok yang tidak berada di dekat pemain.

Saya berpikir mungkin menggunakan (0,0) untuk (mapWidth, mapHeight) susunan ganda blok bukan daftar, menghitung zona bahaya tergantung pada posisi orang tersebut mis., Jika posisi pemain berada di (10, 20) akan terlihat dari (0, 10) hingga (20, 30), atau seterusnya.

Segala pemikiran dan pertimbangannya luar biasa, terima kasih.

Ross
sumber
1
Dan selamat datang di stackexchange! :-) Jangan lupa membaca FAQ jika Anda tidak mengetahui cara kerja seluruh QA dan sistem reputasi.
David Gouveia
Tentunya ubin ini lebih besar dari 16 kali 16 piksel, pada 1920 kali 1080 itu 8.100 ubin. Tentunya Anda tahu di mana entitas bergerak, dan Anda hanya dapat memeriksa ubin di grid yang mungkin berada dalam jangkauan (jika satu adalah 160 * 160 dan pusat berada di ubin (12,12) Anda hanya perlu memeriksa antar ubin (6, 12) , 6) dan (18,18) dengan total ~ 150 ubin yang mungkin.). Tentunya ubin di bawah gravitasi hanya jatuh, dan Anda hanya perlu mencari ubin berikutnya di bawahnya.
DampeS8N
Apakah menurut Anda 16x16 terlalu kecil? Tidak akan sulit bagi saya untuk mengubah ukuran ubin, karena apa pun yang merujuk tilewidth / tinggi adalah konstanta statis. Yang harus saya lakukan adalah memperbesarnya di Paint.NET, yang bagus karena menambahkan lebih detail.
Ross
Maukah Anda berbagi kode tabrakan? : /
ashes999

Jawaban:

7

Ya, Anda berpikir dengan benar. Anda harus menggunakan array ubin 2D karena itu memungkinkan Anda untuk mengindeks ubin dengan posisi.

Block[,] level = new Block[width, height];

Dan karena pemain hanya bisa bertabrakan dengan ubin di sekitarnya, jumlah pemeriksaan tabrakan yang perlu Anda lakukan sangat kecil. Ini tentu saja tergantung pada ukuran pemain. The platformer sampel melakukannya seperti ini:

int leftTile = (int)Math.Floor((float)characterBounds.Left / tileWidth);
int rightTile = (int)Math.Ceiling(((float)characterBounds.Right / tileWidth)) - 1;
int topTile = (int)Math.Floor((float)characterBounds.Top / tileHeight);
int bottomTile = (int)Math.Ceiling(((float)characterBounds.Bottom / tileHeight)) - 1;

for (int y = topTile; y <= bottomTile; ++y)
{
    for (int x = leftTile; x <= rightTile; ++x)
    {
        // Handle collisions with the tile level[x,y] just like you were doing!
    }
}

Periksa sampel jika Anda masih memiliki masalah.

David Gouveia
sumber
Ini adalah algoritma kecil yang sangat bagus, saya bahkan belum pernah mendengar sampel Platformer (saya seharusnya, tapi saya mengklaim ketidaktahuan). Terima kasih!
Ross
@Ross Benarkah? Anda akan terkejut betapa miripnya solusi Anda dengan sampel. :-) Kurangi bagian daftar, yang lainnya hampir sama (kotak intersect bounding, dapatkan kedalaman persimpangan, ketelitian pada sumbu terkecil).
David Gouveia
1
Ya ampun, aku baru saja melihatnya. >. <Seandainya aku tahu ini 2 hari yang lalu !! Yah, saya baru mengenal XNA tapi saya sudah mempelajari grafis 2D (hanya OpenGL, tidak terlalu banyak pemrograman game). Saya kira saya harus memeriksa lebih banyak sumber daya sebelum saya pergi ke kepala terlebih dahulu dalam pengkodean.
Ross
1

Saya kira jawaban saya akan menjadi jawaban Anda! ;-)

Jika Anda memiliki posisi pemain (dan ukuran), Anda dapat menghitung indeks ubin di sekitarnya (yang merupakan satu-satunya yang akan diperiksa secara detail). Dengan cara ini seharusnya tidak relevan seberapa besar peta Anda, itu hanya tergantung pada ukuran sebenarnya dari pemain Anda sehingga menghasilkan lebih banyak ubin potensial untuk diperiksa.

Mungkin periksa tutorial tentang tabrakan di riemers.net jika Anda belum melakukannya.

Pangeran Charles
sumber
Saya pernah mendengar tentang Riemer tetapi tidak pernah sempat melihat, terima kasih!
Ross
1

Ketika berhadapan dengan sejumlah besar tabrakan, Anda biasanya ingin mengadopsi struktur yang lebih maju , seperti Quadtree atau Hashmap untuk memeriksa tabrakan tersebut.

Karena ubin statis saya sarankan menggunakan Quadtree. Pohon quad terdiri dari paha depan. Setiap quad terdiri dari empat persegi panjang dan masing-masing persegi panjang adalah paha depan. Ini berlanjut secara rekursif hingga ukuran yang ditentukan. Setiap quad dapat berisi daftar ubin yang menghuni area layar itu. Dengan begitu, saat Anda memeriksa tabrakan, Anda bisa

  1. Batasi cek untuk orang-orang di sekitarnya
  2. Batasi pemeriksaan hanya pada objek yang bergerak

Sekarang jika Anda tidak ingin melihat ubin dari layar maka Anda dapat melakukan sesuatu seperti

public bool CheckCollision(myPosition) {
    if(quadNodes.Count > 0) {
        // This is not a leaf, keep checking
        foreach(Quad node in quadNodes) {
            if(node.Position is insideViewport && nearPlayer)
                // Continue recursion
            }
        }
    }
    else {
        // This is a leaf, do checks
        foreach(Tile tile in tileList) {
            if(collision)
                return true;
        }
        return false;
    }
}
Mike Cluck
sumber
Hmm, saya pernah mendengar tentang Octrees dalam deteksi tabrakan 3D tetapi tidak pernah melihat Struktur Data canggih yang digunakan untuk deteksi tabrakan 2D. Terima kasih banyak!
Ross
1
Karena gimnya (dengan asumsi Terraria) terdiri dari ubin dengan spasi yang sama, menggunakan kisi akan jauh lebih mudah dan lebih cepat daripada quadtree. Quadtree berfungsi lebih baik untuk dunia yang lebih kompleks di mana kisi-kisi akan sulit masuk dan semuanya memiliki ukuran yang berubah-ubah.
David Gouveia
1
Anda benar jika itu adalah permainan murni berbasis grid, bahkan hingga ke ukuran karakter. Saya tahu bahwa di Terraria mereka juga memiliki monster yang tidak mudah masuk ke format grid. Saya berlari dengan asumsi bahwa dunia dasar terbuat dari ubin tetapi benda lain akan berbeda dan mereka bisa menyimpannya dalam struktur yang sama untuk menghindari membangun yang lain. Saya kira mereka bisa menggunakan kotak untuk ubin kemudian struktur yang berbeda (jika perlu) untuk objek sewenang-wenang lainnya.
Mike Cluck
1
Itulah yang akan saya sarankan :) Grid harus digunakan untuk menangani tabrakan dengan medan, sedangkan quadtree dapat digunakan untuk menangani tabrakan antar-objek.
David Gouveia
Benar. Saat ini setiap kotak pembatas memiliki dimensi daya 2 ^. Ini membuatnya lebih mudah saya temukan untuk mendeteksi tabrakan. Grid akan sesuai dengan kebutuhan saya untuk saat ini.
Ross