「IMPULSE衝力2D物理引擎」的探索過程與運作原理

在寫完前一篇「IMPULSE衝力2D物理引擎」的介紹後，感覺還少了些什麼？一個物理與數學的中輟生(我大三之後就沒再學物理了，且也快忘光了)，是如何從coding的角度來探索物理引擎的呢？物理引擎內，到底是什麼程式呢？請看這一篇的紀錄文章。




這篇文章大概分成兩個部分，前半是(艱苦的)探索過程，後半是運作原理。原理的部分很複雜，所以採簡要敘述與列出參考資料，不過要有心理準備，參考資料都是英文的。

這個主題，大大的超出了我的能力與預期，幾度想在中途放棄，但是想到能讓遊戲中的物體，有著真實世界的碰撞反應。諸如「憤怒鳥就是這樣做出來的」、「能做出來實在是太酷了」這樣的信念，讓我一直堅持到了最後。


【探索過程】
 
一開始不知道要從哪裡下手，於是試著從Scratch的作品說明中找一些線索。

https://scratch.mit.edu/projects/86958095/

在說明中有提到原作者所參考的文章，如下圖






















從關鍵字找到了Randy Gual所寫的一篇教學，教人用C++語言寫出一個簡單的物理引擎，
文章共有4篇。

https://gamedevelopment.tutsplus.com/series/how-to-create-a-custom-physics-engine--gamedev-12715

這4篇文章介紹了許多物理引擎的概念，與相關的物理數學公式，文章尾端都有作者的介紹，他是一個學習資訊科學的學生(原文寫於2013)，如下圖。(好厲害的學生啊)

以下是Randy Gaul最後寫出的物理引擎的示範程式影片，從影片中可以看到不同形狀物體之間的碰撞反應(有圓形、矩形與多邊形)

不過有再多的資料與影片還不夠，對我來說，最重要的是找到可以運行的code，這樣我才能依據文章來實際跑code(這是我的學習方式)，但是有個問題發生，Randy的C++程式，我一直沒有適當的環境來運行，有試了Visual Studio也不行，我對C++不熟，所以就卡住了。

怎麼辦呢？難道就放棄了嗎？再找看看吧，一定有方法的，果不其然，找到了Philip Diffenderfer用Java做出了這個引擎，而且也有程式放在Github，如下圖

https://github.com/ClickerMonkey/ImpulseEngine

經過了一番努力，終於在Eclipse的環境下，成功的運行Demo的Java程式，這樣我就可以來學習原理了，Oh，Yeah。

看了一些資料與程式後，覺得還是要自己來寫一次，會比較踏實，我比較熟的是python，所以就開始用python + pygame，來把這個學習用的簡易物理引擎來寫一次。因為想要接近原本的程式，所以連需要用到的2d向量與矩陣的部份，也自己寫一次，所以就慢慢的一邊用我破破的Java與C++來學原理，一邊用python寫，同時對照著教學文章，這樣的多次循環，到最後終於完成了python版的程式。

https://github.com/beardad1975/impulse_engine

自己剛用python寫完時，因為python的效能不好，而且我也不會最佳化，效果還好，所以並沒有覺得太高興。不過，神奇的是，後來再去看Scratch版本的物理引擎，發現作者是做原程式的移植，所以程式的流程與函數名稱，都跟原來的很接近，讀起Scratch程式，就容易多了，一下子就能捉到程式的概要，這才了解到，原來之前的努力沒有白費，是會有回報的，差點流下了興奮的眼淚。感謝這中間多位無私分享資料的外國網友，讓我有這種難以想像的學習機會。

由於大致了解了物理引擎的架構，所以把原本的遊戲改成彈珠遊戲也簡單多了。

https://scratch.mit.edu/projects/134193915/

嚴格來說是沒有什麼大不了的，但是遊戲改寫出的那天晚上，一直興奮的睡不著呢！
(想到遊戲背後的這一堆理論)

【運作原理】
由於自己的英文僅到尚可的程度，所以也不確定是否完全了解原本的理論，不過基於分享的精神，還是試著把「IMPULSE衝力2D物理引擎」的運作原理做一個說明。

首先是資料結構的部分，每個物件的資料，都放在一個Rigid body的清單中，Rigid body是物理所稱的剛體，剛體在受力的前、中、後都不會產生變形，這樣的假設可以大大簡化問題(柔體的公式一定更複雜)

Rigid body的資料清單如下，放的都是一些如位置、速度、加速度、質量…等相關的物理量，一個物件的資料就有28項，作者griffpatch把Scratch的清單，當成2維陣列來使用，這樣是一種處理複雜的資料的方法。這個清單是動態的，當使用者加入一個新的物件，就會再增加28個項目資料到這個清單中。(Scratch的資料結構只有一維陣列，這個程式能移植，真是要給griffpatch一個大大的讚，我光用python就寫得很頭大了)

   還有另一個重要的清單，叫做 Manifolds(切觸流形)，這個字我之前在學習3D列印時，曾經在一些軟體看過，但不知道是什麼意思。找了半天資料後，我的理解是物體與物體之間碰撞時的接觸面，如下圖：

來源：https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/

如果是兩個3D物體的碰撞，Manifold接觸可能是一個面、一條線或是一個點。而以本文討論的2D物體，Manifold接觸會是一條線或是一個點。這個Manifold的清單，紀錄著兩兩物件碰撞時的碰撞方向、碰撞點、彈性係數、摩擦力…等資訊。

再來看一下物理引擎的主迴圈，由於這是一個示範引擎的程式，了解主迴圈後，就可以知道下手修改的方向。迴圈如下圖(黃色矩形處)

其中最重要的是一些自定義的積木(深藍色)，作者的自定積木實作了很多，以下只說明一些重要的自定義積木。


跟使用者操作相關的有Fire!與Spawn Stuff，這兩個積木讓我們可以用滑鼠發射憤怒鳥，或是用1-6數字鍵，新增一些物件。

跟繪圖有關的積木是draw bodies，會畫出所有在Rigid Body清單中的物體。
有使用到 Scratch的畫筆與分身功能。

再來是step這個自定義積木。可別小看這個積木，它可是物理運算的核心。
積木如下圖。

這個step會計算出短暫時間內(如1/50秒)，所有物體的移動變化、轉動變化與碰撞反應。 由於所有的物理運算都在step內。以下再針對step內的主要自定義積木做說明。

New Manifold積木主要在做碰撞偵測，看看兩個物體是否有碰撞，如果有的話，把相關的碰撞資訊放在Manifolds清單中，這邊使用到的演算法是SAT(Separating Axis Theorem)，可以用來判斷兩個多邊形是否有碰撞

SAT參考資料：https://gamedevelopment.tutsplus.com/tutorials/collision-detection-using-the-separating-axis-theorem--gamedev-169

概念圖如下(簡單來說是，如果能在兩個多邊形之間找到一條分隔的線，則兩者沒有碰撞)

當兩物件有碰撞時，要找出碰撞的接觸點，使用的演算法是Sutherland-Hodgman的clipping，
參考資料：https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics5collisionmanifolds/

    再來是Integrate Forces與Integrate Velocities，這兩個積木會把外力轉成加速度，加速度改變速度，速度產生新的位移，當然也有計算轉動的力矩、角加速度、角速度與角位移。相關的概念與牛頓的第1、2 、3運動定律有關。

參考資料：https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics1introductiontonewtoniandynamics/
       

在做計算時，是以積分的數值方法，一步步算出位移，雖然用到微積分看起來很嚇人，但是使用尤拉法計算，意外的簡單(缺點是誤差較大)。

有些資料中提到一件有趣的事，說物理引擎能做出一個影片(一個畫面一個畫面step)，只是畫面之間的變化，是由物理公式來與使用者的變因來決定的。

參考資料：https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics2numericalintegrationmethods/

     Initialize Manifold這個積木主要是決定出兩碰撞物體的彈性碰撞係數，與摩擦係數。


    再來也是很重要的Apply Impulse，Impulse在物理是衝量，代表是短時間內，一股很大的撞擊力量，造成兩碰撞物體立即改變速度。Randy Gual在他的教學文章列出的衝量公式，如下圖：

參考資料：https://research.ncl.ac.uk/game/mastersdegree/gametechnologies/physics6collisionresponse/
 

    Correct Positions這個積木會修正碰撞物體的位置，讓兩物體儘量不重疊


    Clear Force會把積木轉換過的力與力矩歸零


    主要的程式大致解說至此，這個遊戲可以拿來重覆利用(像library)，雖然因scratch的限制麻煩點，但是從主迴圈下手，大致就可以了，再注意一些小細節，其他的物理引擎就照原本運作就可以了。

【結語】

   物理引擎很酷，但是深入了解之後也相當複雜，且牽連到的領域多，有資訊、物理、數學，相關的資料都需要英文的閱讀。但是反過來想，本文所提到的這些知識，都是從網路上獲得，也算是公開的資料，且資料也算很多，也很多外國網友在學習與討論，但是幾乎找不到中文資料，也許這就是外國與我們的差距吧！

另外，自己從小到大的學習中，曾經學到一些相關基礎知識，但最後卻學不下去，如果在學習數學、物理的成長過程中，能有這麼有趣的例子，我一定會認真學習這些基礎學科的。以上是一點小小的感想。