2D कठोर पिंड collision को resolve करने का तरीका

 (sassnow.ski)
3 पॉइंट द्वारा GN⁺ 2024-05-25 | 1 टिप्पणियां | WhatsApp पर शेयर करें
  • 2D game physics में rigid body collision resolution उस समस्या को हल करता है जिसमें पहले से छू रहे या overlap कर रहे objects के लिए velocity changes निकाले जाते हैं, ताकि अगले frame में वे एक-दूसरे में penetrate न करें
  • game loop हर frame में velocity और Δt से position update करता है, इसलिए अगर नई position पर geometry overlap हो जाए, तो अलग handling न होने पर objects एक-दूसरे के आर-पार निकल जाते हैं
  • collision केवल contact है या नहीं का मामला नहीं है; यह भी देखना पड़ता है कि contact में आए objects अपनी current velocities के अनुसार अब भी एक-दूसरे की ओर बढ़ रहे हैं या नहीं
  • surface से दूर जा रहे हैं या नहीं, यह normal और velocity के dot product के sign से तय किया जा सकता है; positive हो तो same-direction component, negative हो तो opposite-direction component मौजूद होता है
  • दो objects के मामले में individual velocities से ज़्यादा relative velocity और collision normal महत्वपूर्ण होते हैं; contact state में relative normal velocity negative हो तो इसे collision माना जा सकता है

Rigid body physics और collision resolution का scope

  • विषय rigid body physics है, जो ऐसे objects से जुड़ा है जो force लगने पर deform नहीं होते
    • वास्तविकता में सभी objects molecular level पर deform होते हैं, इसलिए perfectly rigid body मौजूद नहीं होता
    • ज़्यादातर physics simulations में ऐसे detailed deformations तक calculate करना बहुत कठिन या महंगा होता है
    • अगर object पर्याप्त realistic दिखे, तो उसे rigid body की तरह simplify करना practical तरीका है
  • game engine में collision handling आम तौर पर दो चरणों में बंटी होती है
    • collision detection: scene में कौन से objects collision में हैं, यह तय करना
    • collision resolution: collision में मौजूद objects की movement direction, velocity, material आदि के आधार पर आगे की state तय करना
  • यहां focus geometric intersection ढूंढने वाले चरण पर नहीं, बल्कि collision के बाद movement तय करने वाले collision resolution पर है

Game loop में collision कैसे बनता है

  • ज़्यादातर games एक बड़े loop के अंदर scene में मौजूद objects की positions को बार-बार recalculate करते हैं
  • हर iteration में object की position current velocity के आधार पर update होती है
    • velocity एक vector quantity है जिसमें magnitude और direction दोनों होते हैं
    • arrow की length speed दिखाती है, और arrow जिस दिशा में point करता है वह movement direction दिखाती है
  • fixed time interval Δt के दौरान position change को displacement कहा जाता है
    • displacement भी magnitude और direction वाली vector quantity है
    • अगर game loop प्रति second 60 बार चलता है, तो Δt 1/60 second होता है
  • नई position current velocity से निकाले गए displacement को पुरानी position में जोड़कर मिलती है
  • अगर दो objects की नई positions उनकी geometry को overlap करा दें, तो अलग handling न होने पर objects penetrate करके पार निकल जाते हैं

Collision resolution कौन-सी value ढूंढता है

  • collision resolution का goal यह तय करना है कि simulation आगे बढ़ने पर objects एक-दूसरे में और penetrate न करें, इसके लिए हर object की velocity change क्या हो
  • collision से पहले और बाद की velocities को इन symbols से दर्शाया जाता है
    • v_a,i, v_b,i: objects a, b की collision से पहले की velocities
    • v_a,f, v_b,f: objects a, b की collision के बाद की velocities
    • Δv_a, Δv_b: collision के कारण हर object में आया velocity change
  • अंततः collision resolution Δv_a और Δv_b values खोजने की समस्या है
  • realistic दिखने वाला collision बनाने के लिए चुना गया velocity change संबंधित physics laws को satisfy करना चाहिए

केवल contact से collision पता नहीं चलता

  • दो objects छू रहे हों, इसका मतलब हमेशा यह नहीं कि वे collision में हैं
  • collision वह situation है जिसमें current velocities के साथ आगे बढ़ने पर objects एक-दूसरे में penetrate कर जाएंगे
  • एक ही contact scene भी दो objects की velocity directions के अनुसार collision हो सकता है या नहीं भी हो सकता
  • इसलिए collision condition में दो बातें साथ चाहिए
    • objects की geometries छू रही हों या overlap कर रही हों
    • objects अब भी collision direction में move कर रहे हों

Surface normal और दूर जाने की दिशा

  • कोई object किसी surface से दूर जा रहा है या नहीं, यह surface के normal direction से तय किया जा सकता है
  • normal direction surface के perpendicular होता है और surface से सीधे दूर जाने वाली दिशा दिखाता है
    • flat surface पर हर point का normal direction समान होता है
    • curved surface पर हर point का normal direction अलग होता है
    • circle की circumference पर center से उस circumference point की ओर जाने वाली direction normal direction होती है
  • normal direction को length 1 वाले normalized vector से represent किया जाता है
    • length 1 वाले vector को unit vector भी कहते हैं
    • vector normalized है, यह दिखाने के लिए variable के ऊपर ^ sign लगाया जा सकता है
  • किसी point पर normal direction उस point पर surface के tangent के perpendicular होता है

Dot product से direction component तय करना

  • एक vector दूसरे vector की दिशा में कितना point कर रहा है, यह calculate करने के लिए dot product इस्तेमाल किया जा सकता है
  • 2D vector में dot product corresponding components के products का sum होता है, और result vector नहीं बल्कि scalar होता है
  • geometrically, dot product को एक vector को दूसरे vector की direction में project करने पर मिलने वाली scalar projection length को projection target vector की length से multiply किए गए value के रूप में देखा जा सकता है
  • dot product का sign दो vectors के direction relationship बताता है
    • अगर दो vectors के बीच angle 90° से कम है, तो dot product positive होता है और वे broadly same direction में point करते हैं
    • अगर angle 90° से अधिक है, तो dot product negative होता है और वे broadly opposite direction में point करते हैं
    • अगर angle ठीक 90° है, तो dot product 0 होता है
  • object के velocity vector और surface normal का dot product positive हो, तो object उस surface से दूर जा रहा है

इसे दो objects के collision पर apply करना

  • अगर दो boxes जैसे दो objects हों, तो हर object का अपना velocity vector होता है
  • इस case में individual velocities के बजाय दो objects की relative velocity इस्तेमाल की जाती है
    • relative velocity दो objects की velocities का difference है
    • geometrically, यह v_b के endpoint से v_a के endpoint की ओर जाने वाला vector है
    • उदाहरण के लिए, दो cars अगर 50km/h की speed से head-on collision कर रही हों, तो conditions समान होने पर यह वैसा ही है जैसे एक car 100km/h से stationary car से टकरा रही हो
  • surface से संबंधित direction को collision normal से represent किया जाता है
    • collision normal calculate करने का तरीका colliding objects के shape या geometry पर depend करता है
    • यहां का example vertex-edge collision है, जिसमें एक object का point या vertex दूसरे object के edge से collide करता है
    • vertex-edge collision में collision normal उस edge के perpendicular होता है
  • convention के अनुसार objects को a, b से denote करें, तो collision normal object a की ओर होता है
    • किस object को a या b कहा जाए, यह पूरी calculation में consistent रहे, बस इतना ज़रूरी है

Relative normal velocity से collision define करना

  • relative velocity v_ab और collision normal n^ का dot product calculate करके पता लगाया जा सकता है कि दो objects collision direction में move कर रहे हैं या नहीं
  • इस value को relative normal velocity कहा जाता है
    • यह relative velocity का collision normal direction वाला component है
    • यहां sign महत्वपूर्ण है, लेकिन आगे collision के दौरान लगने वाले forces calculate करते समय भी यह अहम role निभाता है
  • relative normal velocity का sign collision state को अलग करता है
    • value positive हो तो दो objects पहले से ही एक-दूसरे से दूर जा रहे हैं
    • value negative हो तो दो objects अब भी एक-दूसरे से टकरा रहे हैं
  • अंततः, जब किसी object का point दूसरे object को छू रहा हो और relative normal velocity negative हो, तब collision होता है

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

1 टिप्पणियां

 
GN⁺ 2024-05-25
Hacker News की रायें
  • नमस्ते, मैं ही लेखक हूँ! थोड़ा बैकग्राउंड जोड़ूँ तो, यह लेख उस rigid body physics ब्लॉग सीरीज़ का सिर्फ़ पहला भाग है जिसे मैं लिखना चाहता हूँ
    यह लेख मेरे जैसे लोगों के लिए था, जो game developer नहीं हैं और जिनका math background भी बहुत मजबूत नहीं है। इसलिए मैंने ऐसे concepts भी काफ़ी देर तक समझाए हैं जो इस क्षेत्र के अनुभवी लोगों को लगभग obvious लग सकते हैं। अगर सवाल हों तो खुशी से जवाब दूँगा
    • feedback के तौर पर कहूँ तो, intro में “Mario का Goomba के ऊपर से उछलना…” वाला उदाहरण थोड़ा गलतफहमी पैदा कर सकता है। NES और SNES के classic Super Mario जैसे अधिकतर games में ऐसी calculations की ज़्यादातर ज़रूरत नहीं थी और उनका उपयोग भी नहीं हुआ था
      game development शुरू करने वाले लोग अक्सर यह गलत समझ लेते हैं कि collision handling के लिए rigid body collision calculations या Box2D जैसे 2D physics engine की ज़रूरत होती है। अगर आप billiards game या Angry Birds जैसा game बनाना चाहते हैं जहाँ boxes गिरते-बिखरते हैं, तो यह सही है; लेकिन 2D platformer के लिए axis-aligned rectangles की तुलना करके collision detect करना, और overlap undo करने के लिए character के X/Y coordinates बदलना या jump/landing के बाद Y velocity सेट करना काफ़ी होता है। इससे character controls का feel भी ज़्यादा बारीकी से tune करना आसान होता है, और inertia भी शामिल हो सकती है, लेकिन आम तौर पर वह physically realistic inertia नहीं होती। beginners जब realistic physics इस्तेमाल करने की कोशिश करते हैं, तो movement अक्सर तैरती-सी और unsatisfactory लगने लगती है
      इस सरल, physics engine के बिना वाले approach से शुरू करने के लिए tutorial example: https://www.love2d.org/wiki/Tutorial:Baseline_2D_Platformer
    • बहुत बढ़िया था। “A word about math” section वाकई महत्वपूर्ण है। मैं भी math में बहुत अच्छा नहीं हूँ, लेकिन पहले मैंने math concepts को बेहद सरल बनाकर बहुत basic physics simulation बनाई थी
      points, lines जैसे components को बार-बार stack किया, और छोटे steps व visual debugging lines बहुत डालीं, तो result बहुत चरमराता और slow था, लेकिन फिर भी किसी हद तक काम करता था
    • लेख शानदार है और पढ़ने में मज़ेदार था। मेरा भी math background मजबूत नहीं है, इसलिए ऐसे “obvious” concepts समझाने के लिए धन्यवाद :)
      क्या आगे XPBD(Extended Position Based Dynamics - http://mmacklin.com/xpbd.pdf) भी पढ़कर समझाने की योजना है? लगता है यह concept धीरे-धीरे ज़्यादा ध्यान खींच रहा है, और मैंने Bevy में https://github.com/Jondolf/bevy_xpbd के ज़रिए इसे काफ़ी सफलता से इस्तेमाल किया है। यह सामान्य approach से ज़्यादा stable दिखता है
    • लेख पढ़कर सचमुच मज़ा आया :) school में similar चीज़ों से जूझने वाले व्यक्ति के तौर पर भी इसे समझना आसान था
      आगे follow कर सकूँ, इसके लिए अगर आप RSS feed जोड़ दें तो बहुत अच्छा होगा
    • explanation वाकई अच्छी है!
      curiosity में पूछ रहा हूँ, वह page बनाने के लिए आपने कौन सा tool इस्तेमाल किया?
  • ओह! अच्छी research, गहरी explanation, और interactive भी—ऐसा लेख है
    सच कहूँ तो शुरुआत में domain name देखकर जब पता चला कि top-level domain “.ski” है, तो मुझे लगा यह Mechanical Watch [1] और दूसरे शानदार लेख लिखने वाले व्यक्ति की site है। पता चला कि यह पूरी तरह अलग व्यक्ति है, लेकिन quality वैसी ही है। इस “.ski” top-level domain में आखिर कौन-सा secret sauce है :)
    1. https://news.ycombinator.com/item?id=31261533
    • वजह बहुत simple है। “ski” Polish surnames में सबसे common suffix है, और इसका सबसे मशहूर example Kowalski है। Polish लोग या Polish मूल के लोग काफ़ी हैं
      यहाँ हमें पसंद आने वाले https://ciechanow.ski के लेखक भी Apple में काम करने वाले Polish programmer हैं
  • अभी मैं अपने बेटे के साथ side project के तौर पर एक 2D space shooting game बना रहा हूँ। top-down view है, और concept यह है कि हर player कोई ship control करेगा और space debris से भरे एक बंद area में उड़ते हुए opponent पर shoot करेगा
    इस game का अहम element यह है कि space debris को arena के अंदर move किया जा सकता है, और उसे creatively इस्तेमाल करके opponent को trap करना या objective हासिल करने से रोकना जैसे काम किए जा सकते हैं। project के हिस्से के रूप में हम game engine को पूरी तरह skip करना चाहते थे। मैं बेटे को application structure थोड़ा और सिखाना चाहता था, और भले ही बाद में ready-made game engine इस्तेमाल करें, कम से कम एक बार सब कुछ implement करने की process से गुज़रना चाहता था। collision detection और handling तक पहुँचने से पहले तक सब ठीक था। उसके बाद हालात तेज़ी से बिगड़ गए। theoretical math background होने के बावजूद मैं boundary cases की भारी संख्या से जल्दी ही overwhelm हो गया, और आखिरकार हार मानकर Box2D इस्तेमाल करने का फैसला किया। मैं professional game developer नहीं हूँ, लेकिन 20+ साल का development experience और math background है, फिर भी मैंने इस problem को underestimate करने की गलती की। बोलने में यह आसान लगता है, लेकिन details में जाते ही complexity exponential तरीके से बढ़ती लगती है
    • क्या उस game में realistic physics collisions सच में ज़रूरी थे? अगर नहीं, तो यह बेवजह की complexity हो सकती है। 2000 से पहले के लगभग सारे 2D shooting games, और उसके बाद के games में भी सिर्फ़ बहुत थोड़े ही, ऐसा approach इस्तेमाल करते हैं
      बहुत simple rectangle comparison से shooting game बनाने का आम तरीका यहाँ है: https://kidscancode.org/blog/2016/08/pygame_shmup_part_3/
      हालाँकि अगर space debris objects को realistic तरीके से collide और clump होना है, और आप चाहते हैं कि player ship के लिए भारी objects के झुंड को धकेलना मुश्किल हो, तो physics library इस्तेमाल करना reasonable है
    • क्या आपने Verlet integration [1] देखा है? कई uses के लिए यह काफ़ी convincing और practical है, और असल में काफ़ी simple भी है। इस बेहतरीन tutorial [2] को देखकर मैं कुछ ही घंटों में basic physics system बना पाया, जिससे मैं खुद हैरान था
      [1]https://m.youtube.com/watch?v=lS_qeBy3aQI&pp=ygUSVmVybGV0IGl...

[2]https://m.youtube.com/watch?v=3HjO_RGIjCU&pp=ygUSdmVybGV0IGl...

  • फिर भी, लगता है यह आपके बेटे के लिए अच्छा सबक होगा। किसी project के हर हिस्से को पूरी तरह खुद बनाने के सपने का पीछा करना हमेशा worthwhile नहीं होता
  • अभी नहीं तो बाद में, यह काम का reference material होगा। http://www.jeffreythompson.org/collision-detection/table_of_... points, circles, rectangles, lines, polygons और triangles के बीच collision detection को कवर करता है
  • मुझे N game की explanation हमेशा पसंद रही है: https://www.metanetsoftware.com/technique/tutorialA.html
    वह दौर था जब Flash हर जगह था
  • इस विषय पर उछलती और टकराती balls वाला TypeScript demo बनाकर मज़ा आया। बहुत कुछ सीखा
    Code: https://github.com/vandrieu/canvas-bouncing-ball
    collision logic src/collision.ts में है
    Result/demo: https://vandrieu.github.io/canvas-bouncing-ball/
    • सच में शानदार demo है, बढ़िया बनाया! अगर आपको ठीक लगे तो मैं इसे एक छोटे multiplayer game में बदलकर देखना चाहूंगा
      क्या आप संभव हो तो license जोड़ सकते हैं?
  • अगर आप rigid body dynamics और constraints तक और गहराई में जाना चाहते हैं, तो blog posts की यह series बहुत उपयोगी रही: https://www.toptal.com/game/video-game-physics-part-i-an-int...
  • Collision, objects के बीच pairwise non-intersection constraint का violation है। Collision force इस constraint का Lagrange multiplier है। Collision normal किसी object के configuration के संबंध में constraint function का normalized partial derivative है
    • यह तरीका तब ठीक बैठेगा जब आप physics को 1kHz से ऊपर calculate करें और energy conservation का सम्मान करने वाले numerically stable integration algorithm इस्तेमाल करें
      लेकिन games में अक्सर physics updates 30Hz तक नीचे चले जाते हैं और मनमाना Euler-Cromer तरीका इस्तेमाल होता है, इसलिए काफी अलग approach चाहिए
    • दिलचस्प! क्या कोई resources हैं जो इस perspective को और समझाते हों?
  • सच में कमाल है! Explanation, interaction, और खासकर article का friendly tone अच्छा लगा। अगले articles का इंतज़ार रहेगा
  • 2D rigid body physics engine बनाना सच में बहुत मज़ेदार project है। Linear algebra सीखने से पहले मैंने JavaScript में एक बनाया था, और उसे चलाने के लिए maths में गहराई तक गया
    कई महीने लगाए, लेकिन widely known basics से थोड़ा आगे ही मुश्किल से सतह छू पाया। ऐसा stable engine बनाना जिसमें objects एक-दूसरे में धंसें या कांपें नहीं, एक bottomless rabbit hole है, और जो maths-heavy articles मुझे मिले वे भी इसे लगभग cover नहीं करते थे। मैंने maths समझने के लिए Christ Hecker की पुरानी article series का सहारा लिया
    http://www.chrishecker.com/Rigid_Body_Dynamics
    • बिल्कुल! “Part 3: Collision Response” असल में वही content है जिसे ये articles reference के रूप में इस्तेमाल कर रहे हैं
  • JavaScript सीखने के लिए canvas से शुरुआत की, और game development experience के बिना कुछ cute छोटे browser games बनाए। उनमें से एक Galaga clone है, जो कुल मिलाकर अच्छी तरह काम करता है
    मुश्किल हिस्सा projectile collision है। Bullet की current position और अगले time step की position लेकर, enemy के hitbox को भी उसी तरह देखकर intersection check करना था, लेकिन मैंने सिर्फ current time step ही check किया। इसलिए bullets जादू की तरह enemies को चकमा देकर निकल सकती हैं! बेवकूफी भरी बात है। शायद कभी वापस जाकर इसे ठीक करूं