Sortir, Sweep, Prune: Algoritme Deteksi Tabrakan (2023)

• Menjelaskan alur optimasi dari pemeriksaan semua pasangan ke sweep-and-prune, dengan memecahkan deteksi tabrakan yang berulang dalam fisika gim melalui simulasi bola
• Pendekatan sederhana memanggil intersects() untuk semua pasangan kandidat dari n objek, sehingga melakukan sekitar (n*(n-1))/2 pemeriksaan dan cepat membesar sebagai O(n²)
• Uji irisan AABB terdiri dari beberapa pertidaksamaan dan &&; dengan evaluasi short-circuit dan transitivitas pertidaksamaan, kandidat yang tidak mungkin bertabrakan dapat dibuang lebih awal
• Setelah objek diurutkan berdasarkan batas kiri, yaitu minimum x, saat ball2.left > ball1.right terjadi, loop bagian dalam di-break untuk mengecualikan semua kandidat berikutnya sekaligus
• Dengan menambahkan biaya pengurutan O(n log n) dan biaya loop sebesar jumlah tumpang tindih pada sumbu x m, rata-rata menjadi sekitar O(n log n + m), dan pemanggilan intersects() yang tidak perlu berkurang drastis

---

Titik awal deteksi tabrakan dalam gim

• Deteksi tabrakan menjadi prasyarat bagi banyak perilaku dalam pemrograman video game
  • Mencegah karakter saling menembus
  • Mengubah arah Goomba ketika menabrak objek lain
  • Di agar.io, sel besar memakan sel kecil saat bersentuhan
  • Menangani fisika gim secara umum
• Contoh ini menggunakan simulasi bola benda tegar untuk membandingkan beberapa pendekatan deteksi tabrakan
• Cakupannya adalah pendekatan dari cara paling sederhana hingga sweep-and-prune, tidak termasuk pembagian ruang atau subdivisi pohon spasial

Pendekatan sederhana yang memeriksa semua pasangan

• Cara paling langsung adalah menganggap semua pasangan objek sebagai kandidat
  • Loop luar menelusuri setiap bola
  • Loop dalam dimulai dari i + 1 untuk menghindari pasangan duplikat seperti A-B dan B-A
  • Untuk setiap pasangan kandidat, panggil intersects(ball1, ball2), dan jika benar jalankan bounce(ball1, ball2)
• Pemeriksaan ini diulang pada setiap langkah waktu, sehingga bola diproses untuk memantul pada saat bertabrakan
• Saat jumlah objek sedikit, ini sudah memadai, tetapi ketika jumlahnya bertambah, volume pemeriksaan cepat menjadi bottleneck performa

Batasan yang ditimbulkan O(n²)

• Algoritme sederhana berjalan dalam waktu O(n²) menurut Big O
• Untuk n bola, pasangan yang perlu diperiksa kira-kira (n*(n-1))/2, yaitu 0.5n² - 0.5n
  • Jika n = 5, ada 10 pasangan
  • Jika n = 10, ada 45 pasangan
  • Jika n = 15, ada 105 pasangan
  • Jika n = 20, ada 190 pasangan
• Dalam kasus terburuk ketika semua objek saling tumpang tindih pada saat yang sama, algoritme deteksi tabrakan apa pun sulit menghindari pemrosesan tabrakan O(n²)
• Dalam perbandingan nyata, kasus rata-rata dan kasus terbaik lebih praktis daripada kasus terburuk
• Pendekatan sederhana selalu bergerak sebagai Θ(n²) terlepas dari jumlah tabrakan sebenarnya, sehingga ruang perbaikannya besar

Pekerjaan berulang di dalam intersects()

• Titik awal optimasi adalah fungsi intersects() yang dipanggil untuk setiap pasangan kandidat
• Uji irisan AABB umum terdiri dari beberapa pemeriksaan pertidaksamaan yang membandingkan batas di setiap arah

function intersects(object1, object2) {
  // compare objects' bounds to see if they overlap
  return object1.left < object2.right
      && object1.right > object2.left
      && object1.top < object2.bottom
      && object1.bottom > object2.top;
}

• Pemeriksaan ini terbagi menjadi empat kondisi
  • object1.left < object2.right
  • object1.right > object2.left
  • object1.top < object2.bottom
  • object1.bottom > object2.top
• Karena evaluasi short-circuit dari &&, jika satu saja kondisi salah, seluruh uji irisan langsung menjadi salah
• Dengan menggeneralisasi kasus “setidaknya satu kondisi salah” di banyak pengujian, pemanggilan intersects() itu sendiri dapat dikurangi
• Ini sejalan dengan gagasan dalam separating axis theorem, bahwa jika bayangan pada satu sumbu tidak tumpang tindih, dua objek tidak bertabrakan

Membuang kandidat dengan transitivitas pertidaksamaan

• Bahkan hanya dengan melihat kondisi object1.right > object2.left, ada peluang optimasi
• Ketika tiga objek A, B, C berada secara horizontal dalam urutan A-B-C, semua pemeriksaan berikut bisa bernilai salah

A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false

• Jika A > B salah dan B > C salah, maka melalui transitivitas pertidaksamaan dapat diketahui bahwa A > C juga salah
• Karena itu, tanpa memanggil intersects(A, C), kita dapat menentukan bahwa kedua objek tidak bertabrakan
• Penghilangan ini hanya berlaku ketika objek berada dalam urutan tertentu, tetapi label objek bersifat arbitrer, sehingga cukup tetapkan objek kiri sebagai A, tengah sebagai B, dan kanan sebagai C
• Pekerjaan menempatkan objek dalam urutan logis seperti ini adalah pengurutan

Mengurutkan berdasarkan nilai minimum sumbu x

• Daftar yang telah diurutkan memungkinkan transitivitas pertidaksamaan diterapkan ke banyak kandidat sekaligus
• Algoritme pengurutan cepat yang umum adalah O(n log n), lebih rendah daripada O(n²)
• Karena objek bukan titik melainkan menempati interval pada sumbu x, pengurutan berdasarkan posisi x memakai batas kiri, yaitu minimum x
• Dari kode O(n²) sederhana, perubahan yang diperlukan ada dua
  • Sebelum loop, urutkan bola berdasarkan koordinat x batas kiri dengan sortByLeft(balls)
  • Di loop bagian dalam, jika ball2.left > ball1.right, lakukan break

// sort by min x
sortByLeft(balls);

// for each ball
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  // check each of the other balls
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];

    // stop when too far away
    if (ball2.left > ball1.right) break;

    // check for collision
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

• Fungsi pengurutan mengurutkan array berdasarkan selisih batas kiri

function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

Mengapa break aman

• Jika daftar sudah diurutkan, untuk sembarang bilangan bulat positif c, hubungan berikut berlaku

balls[j + c].left >= balls[j].left

• Jika kandidat saat ini memenuhi kondisi berikut, pasangan saat ini tidak tumpang tindih pada sumbu x

balls[j].left > ball1.right

• Jika kedua pertidaksamaan digabungkan, didapat hubungan berikut

balls[j + c].left >= balls[j].left > ball1.right

• Berdasarkan transitivitas, balls[j + c].left > ball1.right juga benar, sehingga semua kandidat berikutnya juga tidak tumpang tindih dengan ball1 pada sumbu x
• Begitu ball2 saat ini tidak lagi tumpang tindih dengan ball1, sisa kandidat di loop bagian dalam dapat dihentikan tanpa diperiksa
• Optimasi ini membatasi pemanggilan intersects() nyata hanya pada pasangan yang tumpang tindih pada sumbu x

Kompleksitas waktu yang lebih baik

• Biaya pengurutan menambahkan komponen O(n log n) jika memakai pengurutan cepat seperti mergesort atau quicksort
• Loop ganda dengan penghentian awal rata-rata dapat dilihat sebagai O(n + m)
  • m adalah jumlah total tumpang tindih pada sumbu x
  • Pada kasus terbaik, jika tidak ada tumpang tindih, hampir tidak ada pemrosesan yang tidak perlu sehingga mendekati O(n)
  • Pada kasus terburuk, tetap dapat memburuk hingga O(n²)
• Kasus rata-rata mengasumsikan objek umumnya tersebar merata dan hanya beberapa tabrakan terjadi per objek
• Kompleksitas keseluruhan, menggabungkan pengurutan dan loop, adalah O(n log n + m)
• Alasannya lebih baik daripada pendekatan sederhana ada dua
  • n log n lebih kecil daripada n²
  • Karena sebagian bergantung pada jumlah tumpang tindih m, algoritme tidak memproses jauh lebih banyak dari yang diperlukan

Beban implementasi dan langkah berikutnya

• Pendekatan berbasis pengurutan ini adalah titik keseimbangan yang sangat meningkatkan performa waktu eksekusi dengan perubahan kode yang kecil
• Dalam demo perbandingan, pemeriksaan pasangan berbasis pengurutan mengurangi jumlah pengujian intersects() per frame secara mencolok dibandingkan pemeriksaan semua pasangan secara global
• Biaya pengurutan tidak ditampilkan dalam visualisasi perbandingan, tetapi diasumsikan bahwa uji irisan cukup mahal
• Pendekatan yang lebih lanjut dan kode final berlanjut di Part 2

[GN⁺]

Komentar Hacker News

• Hal yang menarik dari pendekatan ini adalah penulis menyarankan memakai algoritme pengurutan yang “cepat” seperti merge sort/quicksort demi performa terbaik.
  Namun dalam praktiknya, algoritme pengurutan yang lebih “buruk”, yaitu insertion sort, bisa saja lebih cepat.
  Objek dalam sistem deteksi tabrakan biasanya hanya bergerak sedikit antar-frame, sehingga daftar dari frame sebelumnya yang hampir sudah terurut dapat dipertahankan.
  Pada daftar seperti ini, insertion sort mendekati O(n), sementara quicksort bisa mendekati O(n^2).

  • Penulis membahas hal yang hampir sama di Part 2.
    Penjelasannya kira-kira: “Tahap pengurutan secara analisis adalah bottleneck, tetapi sebagian besar waktu pengurutan tidak melakukan apa-apa. Daftar hampir selalu sudah terurut dari frame sebelumnya. Bahkan ketika urutannya rusak, biasanya hanya perlu beberapa pertukaran untuk mengurutkannya lagi. Berikut contoh cara kerja insertion sort.”
  • Alih-alih mengurutkan di setiap tahap, ada juga cara membuat struktur pengindeksan sedikit longgar untuk menangkap kandidat tabrakan ketika objek bergerak kurang dari epsilon.
    Misalnya, ini bisa dilakukan dengan memperbesar radius bola sebesar epsilon.
    Selama bola belum bergerak sejauh epsilon, indeks tidak perlu dihitung ulang.
    Untuk menghindari lonjakan latensi saat harus menghitung ulang, kita bisa mengurutkan 10% tiap frame untuk membuat indeks yang tertinggal.
    Setelah 10 frame, kita akan mendapatkan indeks yang valid selama posisinya masih berada dalam epsilon dari posisi 10 frame sebelumnya.
  • Quicksort menjadi O(n^2) pada daftar yang hampir terurut hanya jika pivot dipilih dengan sangat buruk.
    Jika pivot dipilih secara acak, hasilnya O(n log n), dan untuk daftar yang sudah hampir terurut, kita juga bisa memilih elemen tengah daftar sebagai pivot.
    Namun bahkan dengan pivot optimal, quicksort tetap O(n log n) dalam kasus terbaik.
    Ada varian merge sort sederhana yang berjalan O(n log k), dengan k adalah jumlah run menaik/menurun dalam data.
    sort bawaan di standard library Haskell memakai algoritme seperti itu, dan sepertinya Python juga demikian.

• Struktur artikelnya sangat bagus.
  Saya sudah mengembangkan game dalam berbagai bentuk sejak akhir 90-an, dan sekarang sebagian besar hal ini diabstraksikan oleh engine, tetapi materi seperti ini penting untuk memahami bagaimana simulasi sistem yang kompleks bekerja.
  Terima kasih kepada penulis karena membuat tulisan yang mudah didekati.

• Untuk continuous collision detection, saya selalu menganggap dokumen ini bagus: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
  Library-nya sendiri juga sangat bagus dari sisi performa.
  Namun karena banyak optimasi di dalamnya, integrasinya agak rumit.

• Saya penasaran apakah pernyataan “algoritme naif ini berjalan dalam waktu O(n2) menurut Big-O” benar.
  Loop luar i berjalan n - 1 kali, dan loop dalam j mulai dari i + 1, jadi bukankah jumlah iterasinya makin lama lebih sedikit dari n - 1?
  Saya bukan lulusan bidang ini, jadi saya penasaran apakah untuk n besar itu dianggap kira-kira sama dengan O(n2), atau memang lebih kecil seperti yang terlihat.

  • Tidak persis n^2.
    Untuk elemen ke-i, perbandingan dilakukan (n - i - 1) kali, dan jika memakai indexing mulai dari 0, total jumlah perbandingannya adalah (n - 1) * n / 2.
    Lihat https://en.wikipedia.org/wiki/Triangular_number.
    Pada akhirnya, dalam analisis Big-O tidak ada bedanya.
    Big-O menjelaskan perilaku saat n menuju tak hingga, dan pada titik itu suku kuadrat yang mendominasi.
  • “Optimasi” dengan memulai loop dalam dari j = i + 1 dimaksudkan agar tidak memeriksa setiap pasangan objek dua kali.
    Ini juga mencegah objek diperiksa terhadap dirinya sendiri.
    Karena setiap pasangan diperiksa sekali, algoritmenya adalah O(n^2).
  • Big-O hanyalah klasifikasi kompleksitas yang menjelaskan bagaimana jumlah operasi abstrak berskala terhadap ukuran input, yaitu panjang daftar input.
    Secara umum, jika jumlah operasi dapat dinyatakan secara analitis sebagai fungsi dari ukuran input, Big-O hanya menyisakan suku terbesar dan membuang semua koefisien.
    Ini tidak selalu menjelaskan performa nyata algoritme.
    20n2^+5n dan 2n^2 + 9001n sama-sama O(n^2).
  • Karena itu adalah jumlah dari 1 sampai n, hasilnya n(n+1)/2.
    Dalam notasi Big-O, semua koefisien dan suku yang tumbuh lebih lambat diabaikan, sehingga direduksi menjadi kompleksitas kuadrat.
  • Big-O mungkin lebih mudah dipahami jika dianggap mirip dengan perhitungan limit dalam kalkulus.

• Penggunaan ilustrasinya bagus dan terasa tepat.
  Kadang tulisan dengan ilustrasi interaktif terasa seperti alasan untuk memasukkan banyak demo keren, seperti presentasi TED yang lebih banyak hiasannya daripada substansinya.
  Namun di tulisan ini, ilustrasinya tidak menelan isi pembahasannya.

• Part 2: https://leanrada.com/notes/sweep-and-prune-2/
  Tulisan-tulisan bagus lainnya juga layak dilihat: https://leanrada.com/

• Dulu sekali saya pernah membuat sesuatu yang mirip; alih-alih mengurutkan, saya mempertahankan daftar indeks untuk tiap arah dan membiarkan objek-objek mengurutkan dirinya sendiri.
  Misalnya ada 4 daftar seperti objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge.
  Saat sebuah objek bergerak secara horizontal, ia memperbarui indeksnya sendiri di array leftEdge dan rightEdge.
  Sebab meskipun bergerak, biasanya cukup menukar 1–2 indeks saja.

  • Pendekatan itu tampaknya berguna untuk scene yang sebagian besar statis.
    Semakin banyak elemen dinamis, membangun ulang graf tampaknya lebih baik.

• Ini pendekatan yang baru saya lihat; bukankah mirip dengan memakai sesuatu seperti quadtree untuk mengurangi jumlah collider potensial?

  • Benar.
    Namun dalam rendering offline, dibanding rendering real-time, kita lebih sering melihat hal seperti k-d tree.

• Saya penasaran dengan bagian “pendekatan lain seperti pembagian ruang atau subdivisi pohon ruang tidak akan dibahas”.
  Apakah ada yang tahu apakah algoritme dalam tulisan ini secara umum lebih cepat daripada pembagian ruang/subdivisi pohon ruang?
  Dulu sekali saya pernah memakai pendekatan bertipe pohon ruang, dan secara naif tampaknya cukup bagus, tetapi saat itu masih era 80-an sebelum internet, jadi saya tidak pernah meneliti atau membandingkannya dengan algoritme yang dipakai orang lain.

  • Kompleksitas mempertahankan pembagian ruang, subdivisi pohon, dan sejenisnya bisa menjadi beban besar, terutama ketika ada sangat banyak objek yang bergerak.
    Mengelola satu daftar entitas tunggal, atau grid sel 256x256 yang masing-masing berisi daftar entitas, jauh lebih mudah ditulis, di-debug, dan dioptimalkan dibanding struktur pembagian yang rumit yang harus mempertahankan semua invarian pohon setiap kali objek bergerak.
    Pada era DOOM atau Quake, performa sistem dasar seperti ini jauh lebih penting daripada sekarang, sehingga lebih masuk akal bagi penulis engine untuk membuat sistem pembagian yang sangat kompleks.
    CPU modern sangat kuat dalam menelusuri array terurut, dan karena pipelining, mengikuti linked list atau tree relatif kurang menguntungkan dibanding dulu.
    Waktu CPU kini lebih banyak dipakai untuk hal-hal seperti AI dan rendering daripada untuk pengelolaan daftar entitas.