Sıralama, süpürme, budama: Çarpışma algılama algoritması (2023)

 (leanrada.com)
3 puan yazan GN⁺ 2024-08-15 | 1 yorum | WhatsApp'ta paylaş
  • Oyun fiziğinde tekrarlanan çarpışma algılama sorununu bir top simülasyonu üzerinden ele alıyor; tüm çiftleri denetlemekten sweep-and-prune’a uzanan optimizasyon akışını açıklıyor
  • Basit yöntem, n nesne için tüm aday çiftlerde intersects() çağırır ve yaklaşık (n*(n-1))/2 denetim yaptığı için hızla O(n²) seviyesine büyür
  • AABB kesişim testi birden çok eşitsizlik ve && ile kurulur; kısa devre değerlendirme ve eşitsizliklerin geçişliliğinden yararlanarak çarpışma ihtimali olmayan adaylar erken elenebilir
  • Nesneler sol sınırları olan minimum x değerine göre sıralandıktan sonra, ball2.left > ball1.right olduğu anda iç döngü break ile kesilir ve sonraki adaylar topluca dışarıda bırakılır
  • Sıralama maliyeti O(n log n) ile x eksenindeki örtüşme sayısı m kadar döngü maliyeti eklenerek ortalamada O(n log n + m) düzeyine gelir; gereksiz intersects() çağrıları büyük ölçüde azalır

Oyunlarda çarpışma algılamanın çıkış noktası

  • Çarpışma algılama, video oyunu programlamasında birçok davranışın önkoşuludur
    • Karakterlerin birbirinin içinden geçmesini engeller
    • Bir Goomba başka bir nesneye çarptığında yönünü değiştirir
    • agar.io’da büyük bir hücre, temas ettiğinde küçük hücreyi yer
    • Genel oyun fiziğini işler
  • Örnek, çeşitli çarpışma algılama yaklaşımlarını karşılaştırmak için katı cisim top simülasyonu kullanır
  • Kapsam, en basit yöntemden sweep-and-prune yaklaşımına uzanan çizgidir; uzamsal bölme veya uzamsal ağaç alt bölümlendirmesi kapsam dışıdır

Tüm çiftleri denetleyen basit yaklaşım

  • En doğrudan yöntem, tüm nesne çiftlerini aday olarak görmektir
    • Dış döngü her topun üzerinden geçer
    • İç döngü i + 1den başlayarak A-B ve B-A gibi yinelenen çiftleri önler
    • Her aday çift için intersects(ball1, ball2) çağrılır; sonuç doğruysa bounce(ball1, ball2) çalıştırılır
  • Bu denetim her zaman adımında tekrarlandığı için toplar çarpıştıkları anda sektirilir
  • Nesne sayısı az olduğunda yeterlidir; ancak sayı arttıkça denetim miktarı hızla performans darboğazına dönüşür

O(n²)’nin getirdiği sınır

  • Basit algoritma, Big O açısından O(n²) zamanda çalışır
  • n top için denetlenmesi gereken çift sayısı kabaca (n*(n-1))/2, yani 0.5n² - 0.5n adettir
    • n = 5 ise 10 çift
    • n = 10 ise 45 çift
    • n = 15 ise 105 çift
    • n = 20 ise 190 çift
  • Tüm nesnelerin aynı anda örtüştüğü en kötü durumda, herhangi bir çarpışma algılama algoritmasının O(n²) çarpışma işleminden kaçınması zordur
  • Pratik karşılaştırmalarda en kötü durumdan çok ortalama ve en iyi durum daha kullanışlıdır
  • Basit yöntem, gerçek çarpışma sayısından bağımsız olarak her zaman Θ(n²) davranır; bu yüzden iyileştirme payı büyüktür

intersects() içindeki tekrarlı iş

  • Optimizasyonun başlangıç noktası, tüm aday çiftler için çağrılan intersects() fonksiyonudur
  • Tipik bir AABB kesişim testi, her yöndeki sınırları karşılaştıran birden çok eşitsizlik denetiminden oluşur
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;
}
  • Bu denetim dört koşula ayrılır
    • object1.left < object2.right
    • object1.right > object2.left
    • object1.top < object2.bottom
    • object1.bottom > object2.top
  • && operatörünün kısa devre değerlendirmesi sayesinde koşullardan biri bile yanlışsa tüm kesişim testi hemen yanlış olur
  • Birden çok test boyunca “en az bir koşul yanlış” durumunu genelleştirirsek intersects() çağrısının kendisini azaltabiliriz
  • Bu, bir eksende izdüşümler örtüşmüyorsa iki nesnenin çarpışmayacağı fikrini temel alan ayıran eksen teoremi ile aynı yönde bir yaklaşımdır

Eşitsizliklerin geçişliliğiyle adayları eleme

  • Yalnızca object1.right > object2.left koşuluna bakmak bile optimizasyon olanağı yaratır
  • A, B, C şeklinde üç nesne yatayda A-B-C sırasındayken aşağıdaki denetimlerin tümü yanlış olabilir
A.right > B.left // returns false
B.right > C.left // returns false
A.right > C.left // returns false
  • A > B yanlış ve B > C yanlışsa, eşitsizliklerin geçişliliği sayesinde A > Cnin de yanlış olduğunu bilebiliriz
  • Bu nedenle intersects(A, C) çağrılmadan da iki nesnenin çarpışmayacağına karar verilebilir
  • Bu atlama yalnızca nesneler belirli bir sıradayken uygulanabilir; ancak nesne etiketleri keyfî olduğundan soldaki nesne A, ortadaki B, sağdaki C olacak şekilde adlandırılabilir
  • Nesneleri bu mantıksal sıraya yerleştirme işi de aslında sıralamadır

x ekseninin minimum değerine göre sıralama

  • Sıralı liste, eşitsizliklerin geçişliliğini birden çok adaya topluca uygulamayı sağlar
  • Tipik hızlı sıralama algoritmaları O(n log n) çalışır ve O(n²)’den düşüktür
  • Nesneler nokta değil, x ekseni üzerinde bir aralık kapladığı için x konumuna göre sıralamada sol sınır olan minimum x kullanılır
  • Basit O(n²) kodda gereken değişiklikler ikidir
    • Döngülerden önce sortByLeft(balls) ile topları sol sınır x koordinatına göre sıralamak
    • İç döngüde ball2.left > ball1.right ise break yapmak
// 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);
    }
  }
}
  • Sıralama fonksiyonu diziyi sol sınır farkına göre sıralar
function sortByLeft(balls) {
  balls.sort((a,b) => a.left - b.left);
}

break neden güvenli?

  • Liste sıralıysa herhangi bir pozitif tamsayı c için aşağıdaki ilişki geçerlidir
balls[j + c].left >= balls[j].left
  • Mevcut aday aşağıdaki koşulu sağlıyorsa, mevcut çift x ekseninde örtüşmüyordur
balls[j].left > ball1.right
  • İki eşitsizliği birleştirince şu ilişki elde edilir
balls[j + c].left >= balls[j].left > ball1.right
  • Geçişlilik gereği balls[j + c].left > ball1.right da doğrudur; dolayısıyla sonraki tüm adaylar da mevcut ball1 ile x ekseninde örtüşmez
  • Mevcut ball2, ball1 ile artık örtüşmediği anda iç döngünün kalan adayları denetlenmeden durdurulabilir
  • Bu optimizasyon, gerçek intersects() çağrılarını x ekseninde örtüşen çiftlerle sınırlar

İyileştirilmiş zaman karmaşıklığı

  • Sıralama maliyeti, mergesort veya quicksort gibi hızlı sıralamalar baz alındığında O(n log n) terimini ekler
  • Erken durdurmalı çift döngü ortalamada O(n + m) olarak görülebilir
    • m, toplam x ekseni örtüşme sayısıdır
    • En iyi durumda hiç örtüşme yoksa gereksiz işlem neredeyse kalmaz ve O(n)’e yaklaşır
    • En kötü durumda hâlâ O(n²)’ye kadar kötüleşebilir
  • Ortalama senaryo, nesnelerin genel olarak dengeli dağıldığı ve nesne başına yalnızca birkaç çarpışma olduğu durumu varsayar
  • Toplam karmaşıklık, sıralama ve döngü birlikte O(n log n + m) olur
  • Basit yöntemden daha iyi olmasının iki nedeni vardır
    • n log n, n²den küçüktür
    • Kısmen örtüşme sayısı mye bağlı olduğu için gerekenden fazla işlem yapmaz

Uygulama yükü ve sonraki adım

  • Bu sıralama tabanlı yöntem, az kod değişikliğiyle çalışma zamanı performansını belirgin biçimde iyileştiren dengeli bir noktadır
  • Karşılaştırma demosunda sıralama tabanlı çift denetimi, küresel tüm çift denetimine göre kare başına intersects() testi sayısını gözle görülür ölçüde azaltır
  • Sıralama maliyeti karşılaştırma görselleştirmesinde gösterilmez; ancak kesişim testinin yeterince pahalı olduğu varsayılır
  • Daha gelişmiş yöntemler ve nihai kod Part 2 ile devam eder

İlgili okumalar

1 yorum

 
GN⁺ 2024-08-15
Hacker News yorumları

  • Bu yaklaşımda ilginç olan şey, yazarın en yüksek performans için merge sort/quick sort gibi “hızlı” sıralama algoritmalarını kullanmayı önermesi
    Ancak pratikte daha “kötü” bir sıralama algoritması olan insertion sort daha hızlı olabilir
    Çarpışma algılama sistemlerindeki nesneler genelde kareler arasında yalnızca az miktarda hareket eder, bu yüzden önceki karenin neredeyse sıralı listesini korumak mümkündür
    Böyle listelerde insertion sort O(n)'e yaklaşırken, quick sort O(n^2)'ye yaklaşabilir

    • Yazar Part 2'de neredeyse aynı noktayı ele alıyor
      Bunu şu şekilde açıklıyor: “Sıralama aşaması analizde darboğazdır, ama çoğu zaman sıralama hiçbir şey yapmaz. Liste neredeyse her zaman önceki karede zaten sıralanmıştır. Sıralama bozulsa bile genelde birkaç takasla yeniden düzelir. İşte insertion sort'un buna nasıl davrandığına dair bir örnek”
    • Her adımda sıralamak yerine, indeksleme yapısını biraz gevşek tutup nesne epsilon'dan daha az hareket ettiğinde çarpışma adaylarını yakalamak da mümkün
      Örneğin kürenin yarıçapını epsilon kadar büyüterek bu yapılabilir
      Küre epsilon kadar hareket etmediği sürece indeksi yeniden hesaplamaya gerek kalmaz
      Yeniden hesaplama gerektiğinde gecikme zirvelerini önlemek için her karede %10 sıralayıp geriden gelen bir indeks oluşturabilirsiniz
      10 kare sonra, 10 kare önceki konumdan epsilon içinde kaldığı sürece geçerli bir indeks elde etmiş olursunuz
    • Neredeyse sıralı bir listede quick sort'un O(n^2) olması yalnızca pivot gerçekten kötü seçildiğinde olur
      Pivot rastgele seçilirse O(n log n) olur; liste zaten neredeyse sıralıysa listenin ortasındaki öğeyi pivot olarak da seçebilirsiniz
      Yine de en iyi pivotla bile quick sort en iyi durumda O(n log n)'dir
      Verideki artan/azalan run sayısına k dersek, O(n log k) çalışan basit merge sort varyantları vardır
      Haskell standart kütüphanesindeki varsayılan sort böyle bir algoritma kullanır ve Python da muhtemelen öyledir

  • Yazının kurgusu çok iyiydi
    90'ların sonlarından beri şu ya da bu şekilde oyun geliştirme yaptım; bugün bunun çoğu motorların içinde soyutlanmış olsa da, karmaşık sistem simülasyonlarının nasıl çalıştığını anlamak için böyle içerikler şart
    Yazarın bu kadar erişilebilir bir yazı hazırlamasına teşekkürler

  • Sürekli çarpışma algılama konusunda şu belgeyi hep çok faydalı bulmuşumdur: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
    Kütüphanenin kendisi de performans açısından mükemmel
    Yalnız çok fazla optimizasyon içerdiği için entegrasyonu biraz zahmetli

  • “Bu saf algoritma Big O açısından O(n2) zamanda çalışır” ifadesinin doğru olup olmadığını merak ediyorum
    Dış döngü i, n - 1 kez dönüyor; iç döngü j ise i + 1'den başladığı için giderek n - 1'den daha az dönmüyor mu diye düşündüm
    Bu alandan değilim; n büyük olduğunda bunun yaklaşık O(n2) ile aynı mı kabul edildiğini, yoksa görünüşte olduğundan daha küçük mü sayıldığını merak ediyorum

    • Tam olarak n^2 değil
      i'inci öğe için karşılaştırma sayısı (n - i - 1)'dir; 0 tabanlı indeksle toplam karşılaştırma sayısı (n - 1) * n / 2 olur
      Bkz. https://en.wikipedia.org/wiki/Triangular_number
      Sonuçta Big O analizinde fark yoktur
      Çünkü Big O, n sonsuza giderkenki davranışı açıklar ve burada ikinci dereceden terim baskındır
    • İç döngüyü j = i + 1'den başlatan “optimizasyon”, tüm nesne çiftlerini iki kez kontrol etmemek içindir
      Ayrıca nesnenin kendisiyle karşılaştırılmasını da engeller
      Tüm çiftler bir kez kontrol edildiği için algoritma O(n^2)'dir
    • Big O, giriş boyutuna yani giriş listesinin uzunluğuna göre soyut işlem sayısının nasıl ölçeklendiğini anlatan bir karmaşıklık sınıflandırmasıdır
      Genel olarak işlem sayısını giriş boyutunun bir fonksiyonu olarak analitik biçimde ifade edebiliyorsanız, Big O en büyük terimi bırakır ve tüm katsayıları atar
      Algoritmanın gerçek performansını mutlaka açıklamaz
      20n2^+5n ile 2n^2 + 9001n ikisi de O(n^2)'dir
    • Bu, 1'den n'e kadar olan toplamdır; dolayısıyla n(n+1)/2 eder
      Big O gösteriminde tüm katsayılar ve daha yavaş büyüyen terimler göz ardı edildiğinden ikinci dereceden karmaşıklık olarak sadeleşir
    • Big O'yu kalkülüsteki limit hesabına benzetmek anlamayı kolaylaştırabilir

  • İllüstrasyon kullanımı çok iyiydi ve yerinde görünüyordu
    Bazen interaktif illüstrasyonlu yazılar, bir sürü havalı demo koymak için bahaneymiş gibi geliyor; TED konuşmaları gibi, içeriğinden çok süsü olan şeyler olabiliyor
    Ama bu yazıda illüstrasyonlar içeriğin önüne geçmemiş

  • Part 2: https://leanrada.com/notes/sweep-and-prune-2/
    Diğer güzel yazılarına da göz atmaya değer: https://leanrada.com/

  • Uzun zaman önce benzer bir şey yapmıştım; sıralama yerine her yön için indeks listeleri tutuyor ve nesnelerin kendilerini sıralamasını sağlıyordum
    Örneğin objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge gibi dört liste vardı
    Nesne yatay hareket ettiğinde leftEdge ve rightEdge dizilerindeki kendi indeksini güncelliyordu
    Çünkü hareket etse bile genelde yalnızca 1-2 indeks yer değiştirmek yetiyordu

    • Bu yaklaşım çoğunlukla statik sahnelerde faydalı görünüyor
      Dinamik öğe sayısı arttıkça grafiği yeniden kuran yaklaşım daha iyi görünüyor

  • Benim için yeni bir yaklaşım ama olası çarpışanların sayısını azaltmak için quadtree gibi bir şey kullanmaya benzemiyor mu?

    • Evet
      Yalnız gerçek zamanlı render'dan çok offline render tarafında k-d tree gibi yapıları daha sık görürsünüz

  • “Mekânsal bölme veya mekânsal ağaç alt bölme gibi diğer yaklaşımları ele almayacağım” kısmı ilgimi çekti
    Buradaki algoritmanın genel olarak mekânsal bölme/mekânsal ağaç alt bölme yöntemlerinden daha hızlı olup olmadığını bilen var mı?
    Uzun zaman önce mekânsal ağaç türü bir yaklaşım kullanmıştım ve ilk bakışta oldukça iyi görünüyordu; ama o zamanlar internet öncesi 80'lerdi, bu yüzden başkalarının kullandığı algoritmaları araştırma ya da karşılaştırma şansım olmadı

    • Mekânsal bölme ya da ağaç alt bölme gibi yapıları sürdürmenin karmaşıklığı, özellikle çok fazla hareketli nesne olduğunda ciddi bir yük olabilir
      Tek bir varlık listesi ya da her biri varlık listesi tutan 256x256 hücreli bir ızgara yönetmek; nesneler her hareket ettiğinde tüm ağaç değişmezlerini korumak zorunda olan karmaşık bölme yapılarından çok daha kolay yazılır, hata ayıklanır ve optimize edilir
      DOOM ve Quake döneminde bu tür temel sistemlerin performansı bugüne kıyasla çok daha kritik olduğu için, motor yazarlarının son derece karmaşık bölme sistemleri kurması daha anlamlıydı
      Günümüz CPU'ları sıralı dizileri taramakta çok güçlü ve pipelining nedeniyle bağlı listeleri ya da ağaçları takip etmek eskisine göre daha az avantajlı
      CPU zamanı artık varlık listelerini yönetmekten çok AI ve render gibi alanlarda harcanıyor