सॉर्टिंग, स्विप, प्रूनिंग: Collision Detection Algorithms (2023)

 (leanrada.com)
3 पॉइंट द्वारा GN⁺ 2024-08-15 | 1 टिप्पणियां | WhatsApp पर शेयर करें

टकराव पहचान एल्गोरिद्म

टकराव पहचान

  • वीडियो गेम प्रोग्रामिंग में टकराव पहचान एक बहुत ही आम समस्या है
  • यह इस बात के लिए आवश्यक है कि कैरेक्टर एक-दूसरे के आर-पार न जा सकें, या physics engine लागू किया जा सके

सरल तरीका 🐥

  • हर object pair की जाँच करके यह देखना कि टकराव है या नहीं
  • कोड उदाहरण: 
    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);
    }
  }
}
  • इस तरीके की time complexity O(n^2) है

परफ़ॉर्मेंस समस्या

  • objects की संख्या बढ़ने पर परफ़ॉर्मेंस समस्या आने लगती है
  • उदाहरण के लिए, n = 20 होने पर 190 pairs की जाँच करनी पड़ती है

समाधान में सुधार

  • अनावश्यक काम को कम करना महत्वपूर्ण है
  • intersects() फ़ंक्शन का optimization: 
    function intersects(object1, object2) {
  return object1.left < object2.right &&
         object1.right > object2.left &&
         object1.top < object2.bottom &&
         object1.bottom > object2.top;
}

सॉर्टिंग के ज़रिए optimization

  • objects को x coordinate के अनुसार sort करने पर अनावश्यक जाँच कम की जा सकती है
  • कोड उदाहरण: 
    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);
    }
  }
}

परफ़ॉर्मेंस विश्लेषण

  • sorting: O(n log n)
  • inner loop: औसतन O(n + m) (m x-axis पर overlap की कुल संख्या है)
  • अंतिम time complexity: O(n log n + m)

दृश्य तुलना

  • global pair checking और sorted pair checking की तुलना
  • sorted pair checking में काफ़ी कम जाँच होती है

GN⁺ का सार

  • यह लेख गेम डेवलपमेंट में टकराव पहचान एल्गोरिद्म को optimize करने के तरीकों पर है
  • यह सरल O(n^2) एल्गोरिद्म से शुरू होकर sorting के ज़रिए परफ़ॉर्मेंस को काफ़ी बेहतर बनाता है
  • यह गेम डेवलपर्स या software engineers के लिए बहुत उपयोगी जानकारी है
  • समान फ़ंक्शनैलिटी वाले अन्य प्रोजेक्ट्स में Box2D, Bullet Physics आदि शामिल हैं

संबंधित पढ़ाई

1 टिप्पणियां

 
GN⁺ 2024-08-15
Hacker News टिप्पणियाँ

  • लेखक ने सर्वोत्तम प्रदर्शन के लिए mergesort या quicksort जैसे "तेज़" sorting algorithms इस्तेमाल करने का सुझाव दिया है

    • लेकिन व्यवहार में insertion sort जैसे "कम अच्छे" sorting algorithms बेहतर प्रदर्शन दिखा सकते हैं
    • collision detection system के objects फ़्रेमों के बीच अपेक्षाकृत छोटे steps में move करते हैं, इसलिए पिछले फ़्रेम की लगभग sorted list को बनाए रखा जा सकता है
    • ऐसी लगभग sorted list को sort करते समय insertion sort O(n) के क़रीब होता है और Quicksort O(n^2) के क़रीब

  • पहले इसी तरह का काम किया था, लेकिन sorting की जगह हर दिशा के लिए index lists maintain की थीं

    • उदाहरण के लिए, objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge जैसी 4 lists होती हैं
    • जब object क्षैतिज रूप से move करता है, तो वह leftEdge और rightEdge arrays में अपना index update करता है
    • move करते समय ज़्यादा से ज़्यादा 1~2 indices ही swap करने पड़ते हैं

  • यह लेख सच में बहुत अच्छी तरह व्यवस्थित है

    • 90 के दशक के आख़िर से game development कर रहा हूँ, लेकिन ज़्यादातर काम engine द्वारा abstract कर दिया जाता है
    • जटिल system simulations को समझने के लिए यह ज़रूरी है
    • लेखक ने बहुत सुलभ लेख लिखा, इसके लिए आभार

  • continuous collision detection पर दस्तावेज़ पढ़ना हमेशा पसंद रहा है

  • illustrations का इस्तेमाल अच्छा लगा

    • कभी-कभी ऐसे articles ऐसा महसूस होते हैं जैसे वे बस शानदार demos इकट्ठा करने का बहाना हों, लेकिन इस बार illustrations हावी नहीं हैं

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

    • उनकी दूसरी posts भी देखने की सिफ़ारिश है: https://leanrada.com/

  • "यह simple algorithm Big O terms में O(n^2) time में चलता है" इस दावे पर सवाल उठाया गया

    • outer loop (i) n - 1 तक गिनता है, और inner loop (j) i + 1 से शुरू होकर हर बार कम elements गिनता है
    • मैं CS major नहीं हूँ, लेकिन सोच रहा हूँ कि बड़े n values के लिए क्या यह लगभग O(n^2) के बराबर है, या इससे कम

  • जिज्ञासा थी कि क्या यह तरीका potential colliders को कम करने के लिए quad tree इस्तेमाल करने जैसा है

  • जिज्ञासा थी कि क्या कभी linear programming method प्रस्तावित की गई है

  • यह वेबसाइट मुझे अच्छे अर्थ में भटका गई

    • मज़ेदार और प्रेरक है