Deteksi tabrakan berbasis Tile yang efisien untuk banyak kotak?

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.

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.

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.

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