Re: [請益] 大學期間自學遊戲程式的方向與一些問題

[cjcat2266 (CJ Cat)]

繼續回昨天沒有寫到的
"繼續自學的話怎麼規畫學習路徑"

遊戲開發主題和領域五花八門
呈網狀分布，又互相關聯
我就以我所知
盡量把想得到的主題、關鍵字、和例子整理起來
中間推薦的學習資源也都是非教科書格式，能在家自行吸收的

從原文可以看出你的自主研究動力相當足夠
所以就依照你的興趣挑主題，逐步展開發展技能樹吧，加油

另外，原文有提出"是否該從0開始造輪子"這個問題
我認為，能夠有奢侈的閒暇時間從0開始造輪子練功打底，就只能趁還是學生的時候
有時間有幹勁，就衝一發吧，不會後悔的
當你開始工作的時候，就較難找到正當理由重造輪子，而失去打好紮實根基的機會


<軟體工程>

基礎一定要打穩
常用資料結構、常用演算法、軟體設計一定要熟
實作遊戲遊戲系統時，依照需求選對資料結構很重要
例如連結物件ID與物件參考，了解為何用hashtable會較有效率
軟體設計方面可以參考設計模式(design pattern)
推薦Head First Design Pattern這本書
但是切記不要掉入"凡事一定要套用pattern"這個思考陷阱裡
過度套用設計模式反而會造成不必要的設計阻力

較低階概念如virtual table實作、記憶體配置(memory layout)，快取(cache)也很重要
光是在除錯的時候有能力看裸記憶體(raw memory)數值，加以解析和操作
就能夠打趴一堆人了

組合語言(assembly)不用熟到能夠隨手寫出程式的地步
但是最好知道運作原理和幾個常用的命令(instruction)
如此一來便可以有能力開發和除錯遊戲腳本引擎(script engine)
而且有時候除錯時symbol file沒有對應到原始檔或者根本不存在
只能看組合語言來除錯時，有時候還能夠繼續除錯下去，相當有用
很多人遇到這個情況就直接放棄了，這個時候有辦法繼續除錯下去的人競爭力就大

了解compiler怎麼把高階語言轉換成組合語言也很有幫助
例如知道switch statement會被轉成jump table之後
便可以理解為什麼只有case數字連續的情況下分歧複雜度才會是O(1)
若case數字不連續則分歧複雜度與一連串if else一樣是O(n)
Compiler Exploerer是個很棒的學習工具
https://godbolt.org/

現在CPU都是multi-core了，去瞭解各種遊戲的平行化(parallelization)運算技巧
例如job system (Unity 2018開始也內建這個概念)
https://www.gdcvault.com/play/1022186/Parallelizing-the-Naughty-Dog-Engine
單執行序的遊戲系統，無法用於需要高運算效率的遊戲
盡早認知到如raycast這種詢問(query)
能夠在這個frame發出運算要求(kick request)，下個frame處理結果(gather results)
或是同個frame早點kick，同個frame晚點gahter
有助於與其他系統共用平行運算資源，對開發高效能遊戲很有幫助


<工程數學>

並不是要學到能夠考100分的程度(想當年我微積分也才6x剛好及格XD)
而是要學到理解每個數學工具的運作原理、幾何意義、和應用時機
(當年期末考好幾題刁鑽題其他人解出來，但我自己沒解出來，心情相當低落
 但同學安慰我說"反正以後老闆也不會因為你這幾題不會解，就不錄用或開除你"
 現在想想真是有道理，我的微積分是熟悉到能夠在遊戲開發方面解題應用自如
 為了增加"鑑別度"而設計的考題解不出來，對工作上一點影響也沒有)

就算平時遊戲開發不一定會用到，多學總是對理解能力有幫助
不然技術文章看不懂，就會落入只能套用人家的公式的境地
遊戲需求一有變化，就沒辦法融會貫通而自己解決稍微有些不同的問題

並且，工程數學底子打好，能夠增加自己的"數理膽量"與自信
不會在讀技術文章的時候看到數學算式就怕到放棄
我自認很討厭看過於學術的技術文章
但當必要的時候，因為不會怕複雜的數學算式，還是能咬牙讀下去

微積分和線性代數是兩個各種paper上都會用到的工具，學好絕對不吃虧
線性代數務必學到完全內化基底轉換(change of basis)、奇異值(eigen values)的意義
對於學好遊戲graphics有莫大助力
若是能夠掌握到矩陣相乘其實是在對行和列做線性組合的概念，會輕鬆很多
http://bit.ly/2DDFPCy


<遊戲應用數學>

高中幾何、三角函數、和向量非常有用
能夠解決如"兩角色過度靠近要如何推開"、"追跡導彈到底是要往左還是往右轉"這種問題
進一步能夠應用到碰撞偵測(collision detection)
你已經會分離軸定律(separating axis theorem, SAT)了
有興趣的話可以進一步研究GJK(Gilbert-Johnson-Keerthi)
http://allenchou.net/2013/12/game-physics-collision-detection-gjk/
碰種偵測只是用來回答"兩個物體是否在空間中有重疊"這個是非題
如果要進一步將互相碰撞的物體分開，會需要生成碰撞點(contact generation)
GJK搭配EPA(Expanding Polytope Algorithm)可以做到
http://allenchou.net/2013/12/game-physics-contact-generation-epa/
有了碰撞點，碰撞點解析(contact resolution)是真正將物體分開的步驟
做法有很多種，Eric Catto (Box2D作者)倡導的做法是sequential impulse
可以參考他各GDC講座錄影和投影片
理解到sequential impulse其實是在12D平面上反覆做平面投影，是內化的關鍵
http://allenchou.net/2013/12/game-physics-constraints-sequential-impulse/

碰撞偵測又可透過broad phase利用空間資料結構(spacial data structure)進行優化
你已經接觸quad tree了
其他值得研究的還有
explicit grid, implicit grid, spatial hash, KD tree, dynamic AABB tree
就算沒時間一一實作，研究並了解他們之間的特性與使用時機，也非常有用
常常並非遊戲物理直接相關的次系統(subsystem)也會需要用空間資料結構加速
若是輕量級需求，有辦法直接inline植入一個空間資料結構是很有用的技能

tween和easing equations也是個不錯的主題
這是用內插(interpolation)讓各種數值遊戲資料圓滑漸變的工具
參考現成open source tweening engine並自己試著實作tween，是個很好的練習

你有提到動畫這個主題，這也相當有趣且值得研究
寫個能解析並將3D工具輸出的動畫格式轉換成自己引擎能高效能利用的格式
也是個很有趣且有用的練習
途中可以順便學習四元數(quaternion)其特性與各種內插比較(如lerp, slerp, nlerp)
http://allenchou.net/2014/04/game-math-quaternion-basics
又可以研究疊加式動畫混和(additive animatoin blending)
這是能透過組合少量動畫素材而生出多樣結果的技術，現在大部分工作室都已採用
另一值得研究的主題是locomotion
這個主題要解決的問題是
"給定移動路線，怎麼組合動畫來讓角色跟著路線走，並且要看起來順暢"
能夠讓玩家角色和NPC走得好看是門很大的學問
直到幾年前，所有工作是都還是用狀態機(state machine)實作
從Ubisoft的For Honor開始，越來越多團隊開始研究一個叫做motion matching的新技術
其與機器學習又融合出一個新的技術叫phase-functioned neural network
網路上都有影片和文章可以學習

還有個有趣的主題是反向動力(inverse kinematics, IK)
是能夠以直接給定骨架肢體末端的目標位置，而反推剩餘骨骼該如何旋轉的工具
主要的做法有CCD(cyclic coordinate descent)和Jacobian
其中Jacobian結果較準確，但也因為需要用到偏微分的概念，較少人選擇使用
讀懂Jacobian原理是3D幾何與偏微分結合應用的良好練習

利用程式而動態產生動畫的技術，統稱程序動畫(procedural animation)
用這個關鍵字可以搜尋到很多有趣的主題
再丟一些跟procedural animation有關的關鍵字
perlin noise / simplex noise (with & without octaves)
numerical springing


<遊戲AI>

這領域太廣了
所以我就稍微偷懶一下只寫現在能想到、感覺有趣且值得研究的關鍵字吧
behavior tree
steering behavior (pursue, avoid, flock, etc.)
pathfinding
navigation mesh
environmental analysis (heat map, influence map, exposure map, etc.)
audio spatial occlusion
group/squad behavior


<遊戲圖像(game graphics)>

我推薦看看Real-Time Render這本書
這本像是高階百科全書，把遊戲圖像的原理、硬體、數學、各種常見現代技術都介紹一遍
繪圖流程(render pipeline)和GPU擅長與不擅長的運算，要了解
遇到有興趣的主題，可以再自行找資料深究

跟之前一樣，我偷個懶只寫當下能想到的一些關鍵字供參考
principle component analysis (PCA) & oriented bounding box (OBB)
hald-edge adjacency structure (這在collision detection也用得上)
triangle/polygon clipping
camera frustum culling
vertex & fragment/pixel shaders
shadow maps
normal maps
forward shading / deferred shading
GPU particles
compute shaders
smooth particle hydrodynamics (SPF)
global illumination (ambient occlusion, reflection, light bounce, etc.)
ray tracing
ray marching
marching boxes / marching cubes / metaballs
visual occlusion
transparency sorting
dithered transparency
order-independent transparency (OIT)
spherical harmonics
light baking / texture baking
imposter
physically-based rendering (PBR)
bidirectional reflectance distribution function (BRDF)


以上，先寫到這邊
這個量應該夠研究好一陣子了
說實在的，若能在畢業以前把上述這些主題都了解一遍(不一定要實作)
畢業即戰力與競爭力應屬上級
還不去直接申請頂尖的遊戲工作室就是浪費才能了
(後60%的主題，我大四畢業的時候還幾乎聽都沒聽過咧)

我認為你做得到，加油


[補充]

補推薦Shadertoy
這是個很多高手分享頂尖shader技術與實驗的遊樂場
https://www.shadertoy.com/

有問題要去哪裡問?
想吸收新知要去哪裡找?
https://www.reddit.com/r/gamedev/
https://www.gamedev.net/
https://gamedev.stackexchange.com/
https://forums.tigsource.com/
https://www.gdcvault.com/

--

Web       http://AllenChou.net
Twitter   http://twitter.com/TheAllenChou
LinkedIn  http://linkedin.com/in/MingLunChou

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 23.242.26.50
※ 文章網址: https://www.ptt.cc/bbs/GameDesign/M.1556422552.A.4CE.html
※ 編輯: cjcat2266 (23.242.26.50), 04/28/2019 11:39:30
推 BeStronger: 佛心來的
※ 編輯: cjcat2266 (23.242.26.50), 04/28/2019 12:00:24
推 md9830415: 以前寫分離軸+向量的程式時候寫了3個禮拜，
→ md9830415: 一直在想是不是不夠聰明之類的，
→ md9830415: 但看完第一篇回覆讓我覺得，真的先做就對了，
→ md9830415: 做了才知道哪邊有問題，把遇到的問題銘記在心，
→ md9830415: 只要持續學習的話總會找到解法
→ md9830415: 第二篇這些關鍵字跟技術很多都是之前從沒聽說過的，
→ md9830415: 越看覺得還有好多要學。
→ md9830415: 真的真的非常感謝，第一次收到這麼認真的回復，
→ md9830415: 我已經不知道該怎麼回應才能表達感謝了。
→ md9830415: 我一定會好好學習，希望有朝一日能追上cjcat的腳步
補充一些graphics關鍵字
和非常粗略地從入門到進階排序
※ 編輯: cjcat2266 (23.242.26.50), 04/28/2019 13:50:13
再加一些線上學習與問答資源連結
※ 編輯: cjcat2266 (23.242.26.50), 04/28/2019 14:07:32
補充遊戲平行運算資源與範例
※ 編輯: cjcat2266 (23.242.26.50), 04/28/2019 15:37:29
推 BeStronger: Real-Time Rendering會建議看第4版的嗎？
→ cjcat2266: 我不知道新版有什麼不同，不過有新版就看新版吧
推 willier15987: 跪了
推 coolrobin: 如果早個十年看到這篇有多好 QAQ
推 BeStronger: 真希望我現在才大一XD
推 wix3000: 看不懂推
推 jackyT: CJ貓大大太神 先存一波
推 kindamark: 推，獲益良多
推 art1: 上次看了一本講遊戲破解的書，後面提到Bz在這方面很強
→ art1: 應該說bz在偵測破解技術的能力很強，但市面上有這能力的公司
→ art1: 好像很少？
推 eric6300: 推
推 NCTU87: 推推
推 newhandfun: 厲害。推個。
推 lanpadick: 這篇有夠營養((嚼嚼
推 riveranb: 朝聖
推 superweak: 推
推 dale:
推 stucode: 推
推 RoastSaury: 真希望我大一能看到這篇XD
推 levelC: 太神了
推 nickchu35: 推神解析跟推薦，早個幾年看到該有多好哈哈
推 zseineo: 推
推 mabinogi805: 26 才看到這篇（歎
推 Petrichor: 推
推 FukadaKyoko: 到進墳墓都無法理解這麼多XD
→ FukadaKyoko: 不過推~~
推 greenick: 羨慕大一就能看到這神回文 營養滿滿
推 doomleika:
推 alibuda174: 推 神...