Quad tree / grid collision based - menempatkan logika dalam aksi

Pertama-tama, saya hanya menulis logika permainan saya sendiri sebentar, jadi saya minta maaf jika ini mungkin terlihat lurus ke depan.

Saya telah membaca banyak tentang quad tree dan grid collision detection. Saya mengerti logika - pada dasarnya tidak memeriksa tabrakan kecuali objek dekat pada dasarnya. Namun tidak pernah disebutkan bagaimana sebenarnya melaksanakan ini.

Saya memiliki beberapa metode kemungkinan di kepala saya tetapi saya tidak yakin mana yang terbaik

Tes tabrakan umum - tanpa optimasi

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }

tetangga toko (metode 1) Tetapi bagaimana jika kita ingin mengoptimalkan tabrakan hanya memeriksa objek yang dekat. Apakah kita masih menjalankan semua objek, atau kita membuat array dengan objek dekat untuk memeriksa?

var objects:Array = new Array();
    var neighbours:Array = new Array();

    for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){

               neighbours.push(objectA, objectB);
              }
        }

    }

    //somewhere else
    for(i:int = 0; i < neighbours.length; i++){
        //only check neighbours

        for(j:int = i + 1; j < neighbours.length; j++){

            if(objectA.collidesWith(objectB){

               //handle collision logic
              }
        }
    }

loop semua objek tetapi hanya memeriksa tetangga untuk tabrakan (metode 3) Kemungkinan lain adalah bahwa kita masih mengulangi semuanya tetapi memeriksa apakah objek dekat sebelum menguji tabrakan.

for(var i:int = 0; i < objects.length; i++){
        //find object A
        var objectA = objects[i];

        for(var j:int = i + 1; j < objects.length; j++){
            //find object B
            var objectB = objects[j];

            if(objectA.isNear(objectB){
               //they are near - check collision!
               if(objectA.collidesWith(objectB){

               //handle collision logic
              }
            }
        }

    }

Menyimpan objek dalam data ubin (metode 3) Menggunakan sistem berbasis ubin memungkinkan opsi lain; Simpan objek yang ada di ubin tertentu dalam data ubin itu sendiri. Periksa untuk melihat di mana ubin objek adalah ubin di sekitarnya berisi objek yang bisa bertabrakan:

var ObjectA;

for(var i:int = 0; i < 4; i ++){
//check 4 surrounding tiles from object A

   if(Object.currentTile + surroundingTile[i] CONTAINS collidable object){
   //check collision!
    if(objectA.collidesWith(surroundingTile.object){

    //handle collision logic
     }

}
}

Saya selalu mencoba melihat dunia nyata sebagai contoh. Jika saya ingin membandingkan item dengan warna yang sama, akan tampak tidak masuk akal untuk memeriksa setiap item meskipun tidak cocok dengan warna (Metode 2, periksa setiap item). Saya mungkin akan mengumpulkan barang-barang dengan warna yang sama (objek yang saling berdekatan) dan mengeceknya (metode 1), daripada memeriksa semuanya.

Ini bukan perbandingan yang tepat karena item dalam pemeriksaan tabrakan terus bergerak sehingga pesanan jadi tercampur. Itu yang membingungkan saya.

Apakah akan lebih efisien untuk memeriksa setiap item, sehingga menghilangkan tekanan terus menghasilkan array tetangga.

Atau lebih efisien untuk menemukan tetangga sehingga tidak harus melewati begitu banyak objek untuk memeriksa tabrakan?

Terus mengubah data pada setiap ubin juga tampaknya sangat intensif, jadi saya tidak yakin apakah itu ide yang bagus ..

Saya telah memikirkan permainan menara pertahanan di mana menara perlu mendeteksi objek jika benda-benda berada dalam jangkauan sebelum menembaknya. Dan sepertinya konyol untuk memeriksa semua item sementara pada beberapa waktu tidak akan ada benda di dekat sama sekali.

Saya minta maaf untuk posting lama, selalu mengalami kesulitan menjelaskan sendiri!

Anda perlu mengurangi jumlah pemeriksaan tabrakan yang sebenarnya. Ya jelas saya tahu. Jadi mari kita uraikan ini:

Algoritme pemeriksaan tabrakan pertama Anda tanpa optimasi apa pun: berapa banyak pemeriksaan yang akan dilakukannya dalam sekali jalan? Jika n adalah jumlah objek, ini akan menjadi sekitar n * (n-1) memeriksa. Untuk banyak objek (> 100) ini akan sangat lambat.

Metode pengecekan tetangga Anda tidak akan jauh lebih cepat. Jika objek Anda tidak statis dan sering berpindah-pindah, Anda harus membuat daftar tetangga ini untuk setiap objek setiap kali dalam loop game Anda. Ini sebenarnya lebih buruk daripada algoritma pertama karena Anda melakukan n * (n-1) untuk membangun daftar tetangga dan kemudian memeriksa setiap objek jika bertabrakan dengan salah satu tetangganya.

Anda perlu mempartisi ruang permainan Anda. Katakanlah ruang gim Anda berukuran 400x400 piksel. Anda dapat mempartisi ini menjadi 4 sub-spasi dengan ukuran masing-masing 200x200 dan memeriksa setiap objek yang termasuk sub-spasi (satu objek dapat berada di dalam lebih dari satu sub-ruang). Maka Anda hanya perlu memeriksa apakah objek di setiap ruang bagian bertabrakan dengan objek lain di ruang yang sama.

Jadi biaya runtime akan menjadi: n untuk membangun daftar 4 sub-ruang + (n / 4) * ((n-1) / 4) yang jauh lebih baik daripada biaya runtime sebelumnya. Ini dapat dikurangi lebih lanjut dengan membuat sub-spasi lebih kecil (misalnya 50x50).

Jadi algoritma kami sekarang terlihat seperti ini:

for each (object in objects)
  check into which subspace the object belongs

for each (subspace in subspaces)
  for each (object in subspace)
    check object for collision with other objects in same subspace

Ini agak mirip dengan ide data ubin Anda. Tetapi subruang tidak harus memiliki ukuran yang sama dengan ubin.

Kita dapat melakukan satu langkah terakhir untuk mengoptimalkan ini lebih lanjut menggunakan quadtree. Biarkan k menjadi hitungan subruang. Untuk membuat daftar objek spasi, kami melakukan pemeriksaan k * n, yang mengarah ke banyak pemeriksaan jika dunia game Anda menjadi besar.

Untuk mengurangi biaya ini, kami menggunakan quadtree. Quadtree adalah cara lain untuk mempartisi ruang permainan kami. Alih-alih membagi ruang 400x400 kami menjadi 64 ruang bagian 50x50 dan memeriksa setiap objek di mana dari 64 ruang bagian saat ini, ruang permainan dibagi menjadi 4 subruang setengah dari ukuran ruang permainan (200x200), yang pada gilirannya dibagi menjadi ruang bagian yang lebih kecil (100x100), yang pada gilirannya dibagi lagi menjadi ruang bagian 50x50. Ini adalah quadtree kami.

Sekarang jika kita ingin tahu ke dalam subruang 50x50 mana sebuah objek milik kita periksa ke dalam subruang 200x200 miliknya. Kemudian kita naik satu tingkat lebih dalam pada quadtree kita dan mengecek terhadap 4 subruang 100x100 yang berada di dalam subruang 200x200 yang baru saja kita temukan. Ini diulangi sampai kita tahu di mana 50x50 subruang objek milik. Jadi berapa banyak cek sekarang diperlukan? 4 untuk setiap tingkat quadtree (Ingat objek dapat berada di tepi dua subruang). Jadi kita perlu 4 * 3 pemeriksaan untuk menetapkan objek ke subruang 50x50 yang benar. Jauh lebih baik dari 64 cek.

Jadi algoritma quadtree kami membutuhkan 4 * 3 * n cek untuk membangun daftar subruang dan kemudian sesuatu seperti k * (n / k) memeriksa untuk memeriksa tabrakan masing-masing objek.