Penyortiran, Sweep, Pruning: Algoritme Deteksi Tabrakan (2023)

 (leanrada.com)
3 poin oleh GN⁺ 2024-08-15 | 1 komentar | Bagikan ke WhatsApp

Algoritme deteksi tabrakan

Deteksi tabrakan

  • Dalam pemrograman video game, deteksi tabrakan adalah masalah yang sangat umum
  • Ini sangat penting untuk mencegah karakter saling menembus, atau untuk mengimplementasikan physics engine

Pendekatan sederhana 🐥

  • Metode untuk memeriksa setiap pasangan objek guna memastikan apakah terjadi tabrakan
  • Contoh kode: 
    for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}
  • Metode ini memiliki kompleksitas waktu O(n^2)

Masalah performa

  • Semakin banyak jumlah objek, semakin besar masalah performa yang muncul
  • Misalnya, saat n = 20, perlu memeriksa 190 pasangan

Perbaikan solusi

  • Mengurangi pekerjaan yang tidak perlu adalah hal yang penting
  • Optimasi fungsi intersects(): 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Optimasi melalui penyortiran

  • Dengan mengurutkan objek berdasarkan koordinat x, pemeriksaan yang tidak perlu bisa dikurangi
  • Contoh kode: 
    sortByLeft(balls);
for (let i = 0; i < balls.length; i++) {
  const ball1 = balls[i];
  for (let j = i + 1; j < balls.length; j++) {
    const ball2 = balls[j];
    if (ball2.left > ball1.right) break;
    if (intersects(ball1, ball2)) {
      bounce(ball1, ball2);
    }
  }
}

Analisis performa

  • Penyortiran: O(n log n)
  • Loop internal: rata-rata O(n + m) (m adalah total jumlah tumpang tindih pada sumbu x)
  • Kompleksitas waktu akhir: O(n log n + m)

Perbandingan visual

  • Perbandingan antara pemeriksaan semua pasangan global dan pemeriksaan pasangan yang sudah diurutkan
  • Pemeriksaan pasangan yang sudah diurutkan melakukan jauh lebih sedikit pengecekan

Ringkasan GN⁺

  • Artikel ini membahas cara mengoptimalkan algoritme deteksi tabrakan dalam pengembangan game
  • Dimulai dari algoritme sederhana O(n^2), lalu meningkatkan performa secara signifikan melalui penyortiran
  • Informasi ini sangat berguna bagi pengembang game maupun software engineer
  • Proyek lain dengan fungsi serupa antara lain Box2D, Bullet Physics, dan lainnya

Bacaan terkait

1 komentar

 
GN⁺ 2024-08-15
Opini Hacker News

  • Penulis menyarankan penggunaan algoritma pengurutan "cepat" seperti mergesort atau quicksort untuk performa optimal

    • Namun, dalam praktiknya algoritma pengurutan "yang kurang baik" seperti insertion sort bisa menunjukkan performa yang lebih baik
    • Objek dalam sistem deteksi tabrakan bergerak dalam langkah yang relatif kecil antar-frame, sehingga daftar yang hampir terurut dari frame sebelumnya dapat dipertahankan
    • Saat mengurutkan daftar yang hampir terurut seperti ini, insertion sort mendekati O(n) sedangkan Quicksort mendekati O(n^2)

  • Pernah mengerjakan hal serupa di masa lalu, tetapi alih-alih mengurutkan, mempertahankan daftar indeks untuk tiap arah

    • Misalnya, ada 4 daftar seperti objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge
    • Jika objek bergerak secara horizontal, ia memperbarui indeksnya sendiri di array leftEdge dan rightEdge
    • Saat bergerak, paling banyak hanya perlu menukar 1–2 indeks

  • Tulisan ini benar-benar tersusun dengan baik

    • Sudah mengembangkan game sejak akhir 90-an, tetapi sebagian besar pekerjaan diabstraksikan oleh engine
    • Ini penting untuk memahami simulasi sistem yang kompleks
    • Terima kasih kepada penulis karena telah menulis artikel yang sangat mudah diakses

  • Selalu senang membaca dokumen tentang continuous collision detection

  • Penggunaan ilustrasinya bagus

    • Terkadang artikel seperti ini terasa seperti alasan untuk mengumpulkan demo-demo keren, tetapi kali ini ilustrasinya tidak mendominasi

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/

  • Mempertanyakan klaim bahwa "algoritma sederhana ini berjalan dalam waktu O(n^2) dalam istilah Big O"

    • Loop luar (i) menghitung hingga n - 1, dan loop dalam (j) dimulai dari i + 1 sehingga menghitung semakin sedikit elemen
    • Bukan lulusan CS, tetapi penasaran apakah untuk nilai n yang besar ini kira-kira sama dengan O(n^2), atau sebenarnya lebih kecil

  • Bertanya-tanya apakah metode ini mirip dengan penggunaan quadtree untuk mengurangi calon tabrakan potensial

  • Bertanya-tanya apakah metode linear programming pernah diusulkan

  • Terdistraksi oleh situs web ini, dalam arti yang baik

    • Menyenangkan dan menginspirasi