सॉर्टिंग, स्विप, प्रूनिंग: collision detection algorithm (2023)

(leanrada.com)

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

गेम physics में बार-बार होने वाली collision detection को बॉल simulation के जरिए समझाते हुए, सभी जोड़ों की जाँच से sweep-and-prune तक जाने वाली optimization flow को समझाया गया है
साधारण तरीका n objects के सभी candidate pairs पर intersects() कॉल करता है, इसलिए लगभग (n*(n-1))/2 बार जाँच होती है और यह जल्दी ही O(n²) तक बढ़ जाता है
AABB intersection test कई inequalities और && से बना होता है; short-circuit evaluation और inequalities की transitivity का उपयोग करके उन candidates को जल्दी हटाया जा सकता है जिनमें collision की संभावना नहीं है
objects को बाएँ boundary यानी minimum x के आधार पर sort करने के बाद, जैसे ही ball2.left > ball1.right हो, inner loop को break करके बाद के candidates को एक साथ बाहर किया जा सकता है
sorting cost O(n log n) में x-axis overlap count m के बराबर loop cost जोड़ने पर, औसतन यह O(n log n + m) के स्तर पर आ जाता है और अनावश्यक intersects() कॉल काफी कम हो जाती हैं

गेम collision detection की शुरुआत

collision detection वीडियो गेम programming में कई व्यवहारों की बुनियाद होती है
- characters को एक-दूसरे के आर-पार जाने से रोकना
- Goomba के किसी दूसरे object से टकराने पर दिशा बदलना
- agar.io में बड़े cell का छोटे cell को छूने पर खा जाना
- सामान्य गेम physics को संभालना
उदाहरण में rigid body ball simulation का उपयोग करके collision detection के कई approaches की तुलना की गई है
दायरा सबसे सरल तरीके से लेकर sweep-and-prune तक है, जबकि spatial partitioning या spatial tree refinement को शामिल नहीं किया गया है

सभी जोड़ों की जाँच करने वाला साधारण तरीका

सबसे सीधा तरीका हर object pair को candidate मानना है
- outer loop हर ball पर iterate करता है
- inner loop i + 1 से शुरू होता है ताकि A-B और B-A जैसे duplicate pairs से बचा जा सके
- हर candidate pair पर intersects(ball1, ball2) कॉल किया जाता है, और true होने पर bounce(ball1, ball2) चलाया जाता है
यह जाँच हर time step पर दोहराई जाती है, इसलिए balls टकराने के क्षण पर bounce के साथ संभाली जाती हैं
objects की संख्या कम हो तो यह पर्याप्त है, लेकिन संख्या बढ़ते ही जाँच की मात्रा जल्दी performance bottleneck बन जाती है

O(n²) की सीमा

साधारण algorithm Big O के हिसाब से O(n²) समय में चलता है
n balls के लिए जाँचने वाले pairs लगभग (n*(n-1))/2, यानी 0.5n² - 0.5n होते हैं
- n = 5 हो तो 10 pairs
- n = 10 हो तो 45 pairs
- n = 15 हो तो 105 pairs
- n = 20 हो तो 190 pairs
सबसे खराब स्थिति में, जब सभी objects एक साथ overlap कर रहे हों, तब कोई भी collision detection algorithm O(n²) collision handling से आसानी से नहीं बच सकता
व्यवहारिक तुलना में worst case से ज्यादा average और best case महत्वपूर्ण होते हैं
साधारण तरीका वास्तविक collisions की संख्या से अलग हमेशा Θ(n²) की तरह चलता है, इसलिए सुधार की काफी गुंजाइश रहती है

`intersects()` के अंदर दोहराया जाने वाला काम

optimization की शुरुआत उस intersects() function से होती है जिसे हर candidate pair के लिए कॉल किया जाता है
सामान्य AABB intersection test हर दिशा की boundaries की तुलना करने वाली कई inequality checks से बना होता है

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;
}

यह test चार conditions में बँटा है
- object1.left < object2.right
- object1.right > object2.left
- object1.top < object2.bottom
- object1.bottom > object2.top
&& की short-circuit evaluation की वजह से, एक भी condition false होते ही पूरा intersection test तुरंत false हो जाता है
अगर कई tests में “कम-से-कम एक condition false है” जैसी स्थिति को generalize किया जाए, तो intersects() calls को ही घटाया जा सकता है
यह उसी दिशा की सोच है जैसे separating axis theorem, जिसमें किसी एक axis पर projections न मिलें तो दो objects टकरा नहीं सकते

inequalities की transitivity से candidates हटाना

केवल object1.right > object2.left condition को देखने से भी optimization की संभावना मिलती है
जब तीन objects A, B, C क्षैतिज रूप से A-B-C क्रम में हों, तब ये सभी checks false हो सकते हैं

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

अगर A > B false है और B > C false है, तो inequality transitivity से हम जान सकते हैं कि A > C भी false है
इसलिए intersects(A, C) को कॉल किए बिना भी यह तय किया जा सकता है कि दोनों objects टकराते नहीं हैं
यह छोड़ना तभी लागू होता है जब objects किसी खास क्रम में हों, लेकिन objects के labels मनमाने होते हैं, इसलिए बाएँ object को A, बीच वाले को B और दाएँ वाले को C मान सकते हैं
objects को इस logical order में रखना ही sorting है

x-axis के minimum value के आधार पर sorting

sorted list होने पर inequalities की transitivity को कई candidates पर एक साथ लागू किया जा सकता है
सामान्य fast sorting algorithms O(n log n) में चलते हैं, जो O(n²) से कम है
objects point नहीं होते, वे x-axis पर interval घेरते हैं, इसलिए x position के आधार पर sorting के लिए बाईं boundary यानी minimum x का उपयोग किया जाता है
साधारण O(n²) code में ज़रूरी बदलाव सिर्फ दो हैं
- loop से पहले sortByLeft(balls) से balls को बाईं boundary x-coordinate के अनुसार sort करना
- inner loop में ball2.left > ball1.right होने पर 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);
    }
  }
}

sorting function array को बाईं boundary के अंतर के आधार पर sort करता है

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

`break` सुरक्षित क्यों है

अगर list sorted है, तो किसी भी धनात्मक पूर्णांक c के लिए यह संबंध सही होगा

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

अगर मौजूदा candidate यह condition पूरी करता है, तो वर्तमान pair x-axis पर overlap नहीं करता

balls[j].left > ball1.right

दोनों inequalities को मिलाने पर यह संबंध बनता है

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

transitivity के अनुसार balls[j + c].left > ball1.right भी true होगा, इसलिए बाद के सभी candidates भी वर्तमान ball1 के साथ x-axis पर overlap नहीं करेंगे
जिस क्षण मौजूदा ball2 अब ball1 से overlap नहीं करता, उसी क्षण inner loop के बाकी candidates को जाँचे बिना रोक दिया जा सकता है
यह optimization वास्तविक intersects() calls को सिर्फ x-axis पर overlap करने वाले pairs तक सीमित कर देता है

बेहतर time complexity

sorting cost mergesort या quicksort जैसी fast sorting के आधार पर O(n log n) term जोड़ती है
early stop वाला double loop औसतन O(n + m) माना जा सकता है
- m कुल x-axis overlaps की संख्या है
- best case में overlap न हों तो अनावश्यक processing लगभग नहीं होती और समय O(n) के करीब रहता है
- worst case में यह अब भी O(n²) तक बिगड़ सकता है
average case यह मानता है कि objects लगभग समान रूप से distributed हैं और हर object पर सिर्फ कुछ ही collisions आते हैं
कुल complexity sorting और loops को मिलाकर O(n log n + m) होती है
यह साधारण तरीके से बेहतर होने के दो कारण हैं
- n log n, n² से छोटा है
- यह overlap count m पर कुछ हद तक निर्भर करता है, इसलिए ज़रूरत से ज्यादा काम नहीं करता

implementation effort और अगला चरण

यह sorting-आधारित तरीका कम code changes के साथ runtime performance में बड़ा सुधार देने वाला संतुलित विकल्प है
comparison demo में, global all-pairs check की तुलना में sorting-based pair checking प्रति frame intersects() tests की संख्या को साफ़ तौर पर घटाती है
sorting cost comparison visualization में नहीं दिखाई गई है, लेकिन यह मान लिया गया है कि intersection tests पर्याप्त महंगे हैं
अधिक उन्नत तरीका और अंतिम code Part 2 में आगे बढ़ता है

1 टिप्पणियां

GN⁺ 2024-08-15

Hacker News की राय

इस तरीके में दिलचस्प बात यह है कि लेखक बेहतरीन performance के लिए merge sort/quick sort जैसे “तेज़” sorting algorithms इस्तेमाल करने का सुझाव देते हैं
लेकिन असल में एक “खराब” sorting algorithm, insertion sort, ज़्यादा तेज़ हो सकता है
collision detection system में objects आम तौर पर frames के बीच बस थोड़ा-थोड़ा ही हिलते हैं, इसलिए पिछले frame की लगभग sorted list को बनाए रखा जा सकता है
ऐसी list पर insertion sort O(n) के करीब हो जाता है, जबकि quick sort O(n^2) के करीब जा सकता है
- लेखक Part 2 में लगभग यही बात कवर करते हैं
  वे कुछ इस तरह समझाते हैं: “sorting step analysis के हिसाब से bottleneck है, लेकिन ज़्यादातर समय sorting कुछ नहीं करती। list लगभग हमेशा पिछले frame से ही sorted होती है। अगर order बिगड़ भी जाए, तो आमतौर पर कुछ swaps से ही फिर sorted हो जाती है। यहाँ insertion sort के behavior का उदाहरण है”
- हर step पर sort करने के बजाय, indexing structure को थोड़ा loose बनाकर उन collision candidates को पकड़ने का तरीका भी है जब object epsilon से कम हिला हो
  उदाहरण के लिए sphere का radius epsilon जितना बढ़ा देने से यह संभव है
  जब तक sphere epsilon जितना नहीं हिलता, index को दोबारा calculate करने की ज़रूरत नहीं होती
  जब दोबारा calculate करना पड़े, तो latency peaks से बचने के लिए हर frame में 10% sort करके पीछे रह गया index बनाया जा सकता है
  10 frames बाद आपके पास ऐसा valid index होगा, जब तक position 10 frames पहले वाली position से epsilon के भीतर है
- लगभग sorted list पर quick sort का O(n^2) होना सिर्फ़ तभी होता है जब pivot सचमुच बहुत खराब चुना गया हो
  अगर pivot random चुना जाए तो O(n log n) मिलता है, और अगर list पहले से लगभग sorted है तो list के बीच वाला element pivot के रूप में चुना जा सकता है
  हालांकि optimal pivot के साथ भी quick sort best case में भी O(n log n) ही है
  data में ascending/descending runs की संख्या k हो, तो merge sort के कुछ simple variants O(n log k) behavior देते हैं
  Haskell standard library का default sort ऐसा algorithm इस्तेमाल करता है, और शायद Python भी ऐसा ही करता है
लेख की structure बहुत अच्छी थी
90s के आखिर से किसी न किसी रूप में game development करता आया हूँ, और आज इसका ज़्यादातर हिस्सा engines में abstract हो चुका है, लेकिन complex system simulation कैसे काम करता है यह समझने के लिए ऐसी सामग्री जरूरी है
लेखक का शुक्रिया कि उन्होंने इसे approachable बनाया
continuous collision detection के बारे में मुझे यह document हमेशा अच्छा लगा है: https://github.com/bepu/bepuphysics2/blob/master/Documentati...
library खुद भी performance के लिहाज से शानदार है
हालांकि इसमें काफी optimizations हैं, इसलिए integrate करना थोड़ा मुश्किल है
मुझे आश्चर्य है कि “यह naive algorithm Big-O के हिसाब से O(n2) time में चलता है” कहना सही है या नहीं
outer loop i, n - 1 बार चलता है, और inner loop j, i + 1 से शुरू होता है, तो लगता है कि यह धीरे-धीरे n - 1 से कम बार चलेगा
मैं CS major नहीं हूँ, इसलिए जानना चाहता हूँ कि n बड़ा होने पर इसे लगभग O(n2) के बराबर माना जाता है, या यह दिखने में उससे कम है
- यह बिल्कुल n^2 नहीं है
  iवें element के लिए comparison (n - i - 1) बार होता है, और 0-based indexing में कुल comparisons (n - 1) * n / 2 होते हैं
  https://en.wikipedia.org/wiki/Triangular_number देखें
  अंत में Big-O analysis में फर्क नहीं पड़ता
  Big-O बताता है कि n infinity की ओर जाने पर behavior कैसा है, और उस समय quadratic term dominate करता है
- inner loop को j = i + 1 से शुरू करने वाला “optimization” हर object pair को दो-दो बार check करने से बचाने के लिए है
  इसका असर यह भी है कि object को खुद अपने साथ check नहीं किया जाता
  क्योंकि सभी pairs को एक-एक बार check किया जाता है, algorithm O(n^2) है
- Big-O सिर्फ़ complexity classification है, जो बताता है कि input size, यानी input list की length के साथ abstract operations की संख्या कैसे scale करती है
  आम तौर पर अगर operations की संख्या को input size के function के रूप में analytically express किया जा सके, तो Big-O सिर्फ़ सबसे बड़ा term रखता है और सभी coefficients हटा देता है
  यह जरूरी नहीं कि algorithm की actual performance बताए
  20n2^+5n और 2n^2 + 9001n दोनों O(n^2) हैं
- 1 से n तक जोड़ने का sum है, इसलिए n(n+1)/2 होता है
  Big-O notation में सभी coefficients और धीमे बढ़ने वाले terms को ignore किया जाता है, इसलिए यह quadratic complexity में reduce हो जाता है
- Big-O को calculus में limits calculate करने जैसा समझें तो शायद और बेहतर समझ आए
illustrations का इस्तेमाल अच्छा था, और सही जगह लगा
कभी-कभी interactive illustrations वाले लेख ढेर सारे cool demos डालने का बहाना लगते हैं, और TED talk की तरह substance से ज़्यादा सजावट हो जाती है
लेकिन इस लेख में illustrations ने content को दबाया नहीं
Part 2: https://leanrada.com/notes/sweep-and-prune-2/
दूसरे अच्छे लेख भी देखने लायक हैं: https://leanrada.com/
बहुत पहले मैंने कुछ ऐसा ही किया था; sorting के बजाय हर direction के लिए index lists बनाए रखे और objects को खुद sort होने दिया
उदाहरण के लिए objectIndicesSortedByLeftEdge/RightEdge/TopEdge/BottomEdge जैसी 4 lists होती हैं
object horizontal move करता है तो वह leftEdge और rightEdge arrays में अपना index update करता है
क्योंकि move करने पर भी आमतौर पर सिर्फ़ 1–2 indices swap करना काफी होता है
- वह तरीका ज़्यादातर static scenes के लिए उपयोगी लगता है
  dynamic elements बढ़ने पर graph को फिर से बनाने वाला तरीका बेहतर लगता है
यह तरीका पहली बार देख रहा हूँ; potential colliders की संख्या घटाने के लिए quadtree जैसी चीज़ इस्तेमाल करने जैसा नहीं है क्या?
- हाँ
  हालांकि real-time rendering के बजाय offline rendering में k-d tree जैसी चीज़ें ज़्यादा अक्सर दिखती हैं
“spatial partitioning या spatial tree subdivision जैसे दूसरे approaches को कवर नहीं करूंगा” वाला हिस्सा मुझे रोचक लगा
क्या किसी को पता है कि लेख का algorithm आम तौर पर spatial partitioning/spatial tree subdivision से तेज़ है या नहीं?
बहुत पहले मैंने spatial tree type approach इस्तेमाल किया था और naive नजरिए से वह काफी अच्छा तरीका लगा था, लेकिन वह internet से पहले का 80s का दौर था, इसलिए दूसरे लोग कौन से algorithms इस्तेमाल करते थे, यह research या compare करने का मौका नहीं मिला
- spatial partitioning या tree subdivision वगैरह maintain करने की complexity, खासकर जब moving objects बहुत ज़्यादा हों, बड़ा बोझ बन सकती है
  एक single entity list, या entities की lists रखने वाली 256x256 cells grid manage करना, ऐसी complex partition structure की तुलना में लिखना, debug करना और optimize करना कहीं आसान है जिसमें object हिलते ही सभी tree invariants maintain करने पड़ें
  DOOM या Quake के दौर में ऐसे foundational systems की performance आज के मुकाबले कहीं ज़्यादा महत्वपूर्ण थी, इसलिए engine authors के लिए बहुत complex partition systems बनाना ज़्यादा reasonable रहा होगा
  आज के CPUs sorted arrays scan करने में बहुत मजबूत हैं, और pipelining की वजह से linked lists या trees follow करना पहले की तुलना में relatively कम फायदेमंद है
  CPU time entity list management से ज़्यादा AI, rendering जैसी जगहों पर खर्च होने लगा है

सॉर्टिंग, स्विप, प्रूनिंग: collision detection algorithm (2023)

गेम collision detection की शुरुआत

सभी जोड़ों की जाँच करने वाला साधारण तरीका

O(n²) की सीमा

intersects() के अंदर दोहराया जाने वाला काम

inequalities की transitivity से candidates हटाना

x-axis के minimum value के आधार पर sorting

break सुरक्षित क्यों है

बेहतर time complexity

implementation effort और अगला चरण

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

1 टिप्पणियां

Hacker News की राय

`intersects()` के अंदर दोहराया जाने वाला काम

`break` सुरक्षित क्यों है