Sıralama, sweep ve budama: Collision Detection Algorithms (2023)

 (leanrada.com)
3 puan yazan GN⁺ 2024-08-15 | 1 yorum | WhatsApp'ta paylaş

Çarpışma algılama algoritması

Çarpışma algılama

  • Video oyunu programlamada çarpışma algılama çok yaygın bir problemdir
  • Karakterlerin birbirinin içinden geçmesini engellemek veya bir fizik motoru uygulamak için gereklidir

Basit yaklaşım 🐥

  • Tüm nesne çiftlerini kontrol ederek çarpışma olup olmadığını doğrulama yöntemi
  • Kod örneği: 
    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);
    }
  }
}
  • Bu yöntem O(n^2) zaman karmaşıklığına sahiptir

Performans sorunu

  • Nesne sayısı arttıkça performans sorunları ortaya çıkar
  • Örneğin, n = 20 olduğunda 190 çifti kontrol etmek gerekir

Çözümü iyileştirme

  • Gereksiz işleri azaltmak önemlidir
  • intersects() fonksiyonunu optimize etme: 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

Sıralama ile optimizasyon

  • Nesneleri x koordinatına göre sıralarsanız gereksiz kontrolleri azaltabilirsiniz
  • Kod örneği: 
    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);
    }
  }
}

Performans analizi

  • Sıralama: O(n log n)
  • İç döngü: ortalama olarak O(n + m) (m, x ekseninde çakışan toplam sayıdır)
  • Nihai zaman karmaşıklığı: O(n log n + m)

Görsel karşılaştırma

  • Tüm çiftlerin küresel olarak kontrol edilmesi ile sıralanmış çift kontrolünün karşılaştırması
  • Sıralanmış çift kontrolü çok daha az sayıda denetim gerçekleştirir

GN⁺ özeti

  • Bu yazı, oyun geliştirmede çarpışma algılama algoritmalarını nasıl optimize edebileceğini ele alıyor
  • Basit O(n^2) algoritmadan başlayıp sıralama yoluyla performansı büyük ölçüde artırıyor
  • Oyun geliştiricileri veya yazılım mühendisleri için çok faydalı bilgiler içeriyor
  • Benzer işlevlere sahip diğer projeler arasında Box2D ve Bullet Physics bulunuyor

İlgili okumalar

1 yorum

 
GN⁺ 2024-08-15
Hacker News yorumları

  • Yazar, en iyi performans için mergesort veya quicksort gibi "hızlı" sıralama algoritmalarının kullanılmasını öneriyor

    • Ancak pratikte insertion sort gibi "daha kötü" sıralama algoritmaları daha iyi performans gösterebilir
    • Çarpışma algılama sistemindeki nesneler frameler arasında görece küçük adımlarla hareket ettiğinden, önceki frameden kalma neredeyse sıralı liste korunabilir
    • Bu tür neredeyse sıralı listeler sıralanırken insertion sort O(n)'e yakın, Quicksort ise O(n^2)'ye yakın davranır

  • Geçmişte benzer bir iş yaptım ama sıralama yerine her yön için indeks listeleri tuttum

    • Örneğin objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge gibi 4 liste var
    • Bir nesne yatay hareket ettiğinde leftEdge ve rightEdge dizilerindeki kendi indeksini güncelliyor
    • Hareket ederken en fazla 1-2 indeksin yerini değiştirmek yeterli oluyor

  • Bu yazı gerçekten çok iyi derlenmiş

    • 90'ların sonlarından beri oyun geliştiriyorum ama işlerin çoğu motor tarafından soyutlanıyor
    • Karmaşık sistem simülasyonlarını anlamak için bu konu vazgeçilmez
    • Yazarın bu kadar erişilebilir bir metin yazmış olmasına minnettarım

  • Sürekli çarpışma algılama ile ilgili dokümanları okumaktan hep keyif aldım

  • İllüstrasyonların kullanımı hoştu

    • Bazen bu tür yazılar sadece havalı demolar toplamak için bir bahane gibi hissettiriyor ama bu yazıda illüstrasyonlar asıl odak değil

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

  • "Bu basit algoritma Big O terimleriyle O(n^2) zamanda çalışır" iddiasını sorguluyorum

    • Dış döngü (i) n - 1'e kadar sayıyor, iç döngü (j) ise i + 1'den başlayıp giderek daha az sayıda dönüyor
    • CS mezunu değilim ama büyük n değerleri için bunun kabaca O(n^2) ile aynı mı, yoksa daha düşük mü olduğunu merak ediyorum

  • Bunun, potansiyel çarpışanları azaltmak için quadtree kullanmaya benzer bir yöntem olup olmadığını merak ettim

  • Doğrusal programlama yöntemlerinin hiç önerilip önerilmediğini merak ettim

  • Bu web sitesi dikkatimi iyi anlamda dağıttı

    • Eğlenceli ve ilham verici