標籤：

遊戲編程裡面有哪些經典或者很酷的演算法？

11-25

年後就要去xx公司做遊戲開發惹。。有哪鎮得住場遊戲開發用得到的牛逼的演算法沒呢，比如A*尋路、指尖計算啥的~。~多多指教

==&>補充：：有米有paper或者book呢，高大上的最好
. .

`-"""-"/
} 6 6 {
=. Y ,=
/^^^ .
/ )
( )-( )/
"" ""

我挑一些有趣的演算法，希望盡量提及相關演算法在遊戲中的應用。

光柵化

  • Bresenham"s line algorithm [1]：經典的繪畫直線演算法，後來還可以稍作修改用於繪畫圓弧[2]，都不用三角函數或除數，只需用整數加法、減法和乘法。

  • Perspective-Correct Texture Mapping [3]：透視正確的光柵化紋理貼圖演算法是1980才出現的。第一代Quake引擎引入後，才開始支持不垂直的牆、不水平的地面天花。

（圖片來自維基百科）

  • Polygon Rasterization with Edge Function [4]：Bresenham演算法如果用來畫多邊形，兩個多邊形的共邊會被重繪。後來發明了使用簡單的edge function去解決這個問題，而且適合併行的硬體實現。現在的GPU都是使用這個演算法。

全局光照

  • Precomputed Radiance Transfer (PRT) with Spherical Harmonics（SH）[5]：儲存靜態環境對於各個方向光源的漫反射數據，可以實現動態低頻光源的全局光照效果。這種表示方式非常神奇。Halo 3也使用到這種技術[6]。

  • Screen-space Ambient Occlusion （SSAO）[7]：Crytek提出的首個屏幕空間環境光遮蔽演算法，之後引來大量的研究及改進演算法。也有用類似的概念去做近距離的反射，如SSDO[8]。

  • Light Propagation Volume （LPV）[9]：Crytek提出的首個動態全局光照演算法，不需要預計算。但要在體積數據中計算傳播，性能較慢，所以之後再優化成 Cascaded LPV [10]。

  • Voxel Cone Tracing [11]：也是不需要預計算的動態全局光照演算法。把場景動態生成層階式的體素數據（像mipmap那樣的pre-filtering），從光源視角計算直接光照，然後逐像素追蹤這組數據獲取非直接光照。結果比LPV精確，也可以做到光澤反射（glossy reflection）。

陰影

  • Shadow Volume [12]：陰影體積是1977年發表的陰影技術，在屏幕空間光柵化陰影體積，可準確判斷每個屏幕像素是否在陰影之內。可以處理平行光源和點光源的陰影。1991年[13]講述如何用stencil buffer來實現此演算法，適合在圖形加速硬體（當時還沒有所謂GPU）上使用。但很多人發現，如果攝像機在陰影體積內，就會出錯。在1998至2000年有多人發現一種解決方法，需要把John Carmack在2000年的電郵[14]中提及這個想法，後來成為2004年《毀滅戰士3（Doom 3）》引擎的重要特徵，因他把這項技術發揚光大，即使他非首個發明人，此項技術通常被稱為Carmack"s Reverse。

  • Parallel Split Shadow Map (PSSM) [15][16] / Cascaded Shadow Map（CSM）[17]：雖然Shadow Volume很吸引，但它需要大量的內存頻寬，而且通常不能實現軟陰影。後來大部分遊戲改為使用Shadow Map（陰影貼圖），這更適合GPU，並且可以通過多次採樣（Percentage Closer Filtering, PCF）來實現軟陰影。然而，陰影貼圖也有許多問題，例如遠近景物都採用同一張紋理，就會令到近景的精度不足，出現鋸齒。2006年香港中文大學的博士生Fan Zhang等人發表了一種 PSSM 演算法 [15]，為不同距離的場景渲染多張陰影貼圖，在採樣的時候按距離決定使用那一張。這個方法的變種CSM，在切割上和PSSM有點差異，被廣泛使用於現時大部分遊戲引擎中。

  • Variance Shadow Map（VSM）[18]：之前談到用PCF做軟陰影，它的壞處就是要做多次採樣。那麼可否把陰影貼圖直接模糊化來實現軟陰影？答案是否定的。但是在2006年有學者發表了VSM，它是一種用統計方式來逼近軟陰影的效果。 如何推導方差陰影貼圖（variance shadow map, VSM) ? - Milo Yip 的回答

場景管理

  • Binary Space Partitioning （BSP）
  • Portal rendering
  • Quadtree、Octree：遊戲場景管理的八叉樹演算法是怎樣的？ - Milo Yip 的回答
  • Potential Visibility Set （PVS）
  • Occlusion Culling by Software Rasterization

動畫／物理

  • Particle System
  • Smoothed Particle Hydrodynamics（SPH）
  • Curl Noise
  • Dual Quaternion Skinning

碰撞測試

  • Hyperplane separation theorem （或稱separating axis theorem/SAT）：凸形狀相交測試的基本原理。在怎樣判斷平面上一個矩形和一個圓形是否有重疊？ - Milo Yip 的回答中，其實背後也是使用了SAT。
  • Gilbert-Johnson-Keerthi distance algorithm (GJK距離演算法)：計算兩個凸形狀的距離（可用於相交測試）
  • Sweep and prune：用於broad phase碰撞檢測，找出物體AABB是否相交。對於時空上連續的物體運動，演算法最壞O(n^2)、最好O(n)。

人工智慧

  • Minimax
  • Alpha-Beta Pruning
  • A* path finding
  • Dijkstra"s algorithm
  • Finite-state machine
  • Behavior Tree

（中午吃飯時間寫不完，後補）

參考

[1] Bresenham, Jack E. "Algorithm for computer control of a digital plotter." IBM Systems journal 4.1 (1965): 25-30. http://www.cse.iitb.ac.in/~paragc/teaching/2011/cs475/papers/bresenham_line.pdf
[2] Bresenham, Jack. "A linear algorithm for incremental digital display of circular arcs." Communications of the ACM 20.2 (1977): 100-106. http://www.cse.iitb.ac.in/~paragc/teaching/2014/cs475/papers/bresenham_circle.pdf
[3] Catmull, Ed, and Alvy Ray Smith. "3-D transformations of images in scanline order." ACM SIGGRAPH Computer Graphics. Vol. 14. No. 3. ACM, 1980. http://alvyray.com/Papers/CG/2pass80.pdf
[4] Pineda, Juan. "A parallel algorithm for polygon rasterization." ACM SIGGRAPH Computer Graphics. Vol. 22. No. 4. ACM, 1988. http://people.csail.mit.edu/ericchan/bib/pdf/p17-pineda.pdf
[5] Sloan, Peter-Pike, Jan Kautz, and John Snyder. "Precomputed radiance transfer for real-time rendering in dynamic, low-frequency lighting environments." ACM Transactions on Graphics (TOG). Vol. 21. No. 3. ACM, 2002. http://www1.cs.columbia.edu/~ravir/6998/papers/p527-sloan.pdf
[6] Chen, Hao, and Xinguo Liu. "Lighting and material of Halo 3." ACM SIGGRAPH 2008 Games. ACM, 2008. http://developer.amd.com/wordpress/media/2012/10/S2008-Chen-Lighting_and_Material_of_Halo3.pdf
[7] Mittring, Martin. "Finding next gen: Cryengine 2." ACM SIGGRAPH 2007 courses. ACM, 2007. http://developer.amd.com/wordpress/media/2012/10/Chapter8-Mittring-Finding_NextGen_CryEngine2.pdf
[8] Ritschel, Tobias, Thorsten Grosch, and Hans-Peter Seidel. "Approximating dynamic global illumination in image space." Proceedings of the 2009 symposium on Interactive 3D graphics and games. ACM, 2009. https://people.mpi-inf.mpg.de/~ritschel/Papers/SSDO.pdf
[9] Kaplanyan, Anton. "Light propagation volumes in cryengine 3." ACM SIGGRAPH Courses 7 (2009): 2. http://www.crytek.com/download/Light_Propagation_Volumes.pdf
[10] Kaplanyan, Anton, and Carsten Dachsbacher. "Cascaded light propagation volumes for real-time indirect illumination." Proceedings of the 2010 ACM SIGGRAPH symposium on Interactive 3D Graphics and Games. ACM, 2010. http://www.vis.uni-stuttgart.de/~dachsbcn/download/lpv.pdf
[11] Crassin, Cyril, et al. "Interactive indirect illumination using voxel cone tracing."Computer Graphics Forum. Vol. 30. No. 7. Blackwell Publishing Ltd, 2011. https://research.nvidia.com/sites/default/files/publications/GIVoxels-pg2011-authors.pdf
[12] Crow, Franklin C. "Shadow algorithms for computer graphics." ACM SIGGRAPH Computer Graphics. Vol. 11. No. 2. ACM, 1977. http://excelsior.biosci.ohio-state.edu/~carlson/history/PDFs/crow-shadows.pdf
[13] Heidmann, Tim. "Real shadows, real time." Iris Universe 18 (1991): 28-31.
[14] Carmack, John, "e-mail to Mark Kilgard on Shadow Volume", 23 May 2000. http://web.archive.org/web/20090127020935/http://developer.nvidia.com/attach/6832
[15] Zhang, Fan, et al. "Parallel-split shadow maps for large-scale virtual environments." Proceedings of the 2006 ACM international conference on Virtual reality continuum and its applications. ACM, 2006.
[16] Zhang, Fan, Hanqiu Sun, and Oskari Nyman. "Parallel-split shadow maps on programmable gpus." GPU Gems 3 (2007): 203-237. GPU Gems 3 - Chapter 10. Parallel-Split Shadow Maps on Programmable GPUs
[17] Dimitrov, Rouslan. "Cascaded shadow maps." Developer Documentation, NVIDIA Corp (2007). http://www.cse.chalmers.se/edu/year/2011/course/TDA361/Advanced%20Computer%20Graphics/cascaded_shadow_maps.pdf
[18] Donnelly, William, and Andrew Lauritzen. "Variance shadow maps."Proceedings of the 2006 symposium on Interactive 3D graphics and games. ACM, 2006. http://www.punkuser.net/vsm/vsm_paper.pdf

過會就要有人把卡馬克大神的平方根倒數演算法放出來。。。

Monte Carlo Tree Search，隨機化博弈樹，用來做遊戲AI。

關於卡馬克大神平方根演算法並沒有那麼神秘，本質上這個超級Magic Number：0x5f3759df，是根據牛頓迭代，泰勒級數以及浮點數在計算機中的存儲使用機器運算而來的。詳情在卡馬克快速平方根---平方根倒數演算法 [轉]以及表述的很清楚了，原文未知出處，侵刪。
更多請看快速浮點開方運算

快速平方根（平方根倒數）演算法

日前在書上看到一段使用多項式逼近計算平方根的代碼，至今都沒搞明白作者是怎樣推算出那個公式的。但在嘗試解決問題的過程中，學到了不少東西，於是便有了這篇心得，寫出來和大家共享。其中有錯漏的地方，還請大家多多指教。

的確，正如許多人所說的那樣，現在有有FPU，有3DNow，有SIMD，討論軟體演算法好像不合時宜。關於sqrt的話題其實早在2003年便已在 http://GameDev.net上得到了廣泛的討論（可見我實在非常火星了，當然不排除還有其他尚在冥王星的人，嘿嘿）。而嘗試探究該話題則完全是出於本人的興趣和好奇心（換句話說就是無知）。

我只是個beginner，所以這種大是大非的問題我也說不清楚（在http://GameDev.net上也有很多類似的爭論）。但無論如何，Carmack在DOOM3中還是使用了軟體演算法，而多知道一點數學知識對3D編程來說也只有好處沒壞處。3D圖形編程其實就是數學，數學，還是數學。

=========================================================


約翰-卡馬克（John Carmack）是Quake-III Arena (雷神之錘3)的3D引擎的開發者。QUAKE的開發商ID SOFTWARE 遵守GPL協議，公開了QUAKE-III的原代碼，讓世人有幸目睹Carmack傳奇的3D引擎的原碼。這是QUAKE-III原代碼的下載地址： http://www.fileshack.com/file.x?fid=7547。


在3D圖形編程中，經常要求平方根或平方根的倒數，例如：求向量的長度或將向量歸一化。C數學函數庫中的sqrt具有理想的精度，但對於3D遊戲程式來說速度太慢。我們希望能夠在保證足夠的精度的同時，進一步提高速度。

Carmack在QUAKE3中使用了下面的演算法，它第一次在公眾場合出現的時候，幾乎震住了所有的人。據說該演算法其實並不是Carmack發明的，它真正的作者是Nvidia的Gary Tarolli（未經證實）。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
// 計算參數x的平方根的倒數
//
float InvSqrt (float x)
{
float xhalf = 0.5f*x;
int i = *(int*)x;
i = 0x5f3759df - (i &>&> 1); // 計算第一個近似根
x = *(float*)i;
x = x*(1.5f - xhalf*x*x); // 牛頓迭代法
return x;
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
該演算法的本質其實就是牛頓迭代法（Newton-Raphson Method，簡稱NR），而NR的基礎則是泰勒級數（Taylor Series）。NR是一種求方程的近似根的方法。首先要估計一個與方程的根比較靠近的數值，然後根據公式推算下一個更加近似的數值，不斷重複直到可以獲得滿意的精度。其公式如下：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
函數：y=f(x)
其一階導數為：y"=f"(x)
則方程：f(x)=0 的第n+1個近似根為
x[n+1] = x[n] - f(x[n]) / f"(x[n])
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
NR最關鍵的地方在於估計第一個近似根。如果該近似根與真根足夠靠近的話，那麼只需要少數幾次迭代，就可以得到滿意的解。

現在回過頭來看看如何利用牛頓法來解決我們的問題。求平方根的倒數，實際就是求方程1/(x^2)-a=0的解。將該方程按牛頓迭代法的公式展開為：
x[n+1]=1/2*x[n]*(3-a*x[n]*x[n])
將1/2放到括弧裡面，就得到了上面那個函數的倒數第二行。

接著，我們要設法估計第一個近似根。這也是上面的函數最神奇的地方。它通過某種方法算出了一個與真根非常接近的近似根，因此它只需要使用一次迭代過程就獲得了較滿意的解。它是怎樣做到的呢？所有的奧妙就在於這一行：
i = 0x5f3759df - (i &>&> 1); // 計算第一個近似根

超級莫名其妙的語句，不是嗎？但仔細想一下的話，還是可以理解的。我們知道，IEEE標準下，float類型的數據在32位系統上是這樣表示的（大體來說就是這樣，但省略了很多細節，有興趣可以GOOGLE）：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
bits：31 30 ... 0
31：符號位
30-23：共8位，保存指數（E）
22-0：共23位，保存尾數（M）
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
所以，32位的浮點數用十進位實數表示就是：M*2^E。開根然後倒數就是：M^(-1/2)*2^(-E/2)。現在就十分清晰了。語句i&> &>1其工作就是將指數除以2，實現2^(E/2)的部分。而前面用一個常數減去它，目的就是得到M^(1/2)同時反轉所有指數的符號。

至於那個0x5f3759df，呃，我只能說，的確是一個超級的Magic Number。

那個Magic Number是可以推導出來的，但我並不打算在這裡討論，因為實在太繁瑣了。簡單來說，其原理如下：因為IEEE的浮點數中，尾數M省略了最前面的1，所以實際的尾數是1+M。如果你在大學上數學課沒有打瞌睡的話，那麼當你看到(1+M)^(-1/2)這樣的形式時，應該會馬上聯想的到它的泰勒級數展開，而該展開式的第一項就是常數。下面給出簡單的推導過程：
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
對於實數R&>0，假設其在IEEE的浮點表示中，
指數為E，尾數為M，則：

R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)

將(1+M)^(-1/2)按泰勒級數展開，取第一項，得：

原式
= (1-M/2) * 2^(-E/2)
= 2^(-E/2) - (M/2) * 2^(-E/2)

如果不考慮指數的符號的話，
(M/2)*2^(E/2)正是(R&>&>1)，
而在IEEE表示中，指數的符號只需簡單地加上一個偏移即可，
而式子的前半部分剛好是個常數，所以原式可以轉化為：

原式 = C - (M/2)*2^(E/2) = C - (R&>&>1)，其中C為常數

所以只需要解方程：
R^(-1/2)
= (1+M)^(-1/2) * 2^(-E/2)
= C - (R&>&>1)
求出令到相對誤差最小的C值就可以了
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
上面的推導過程只是我個人的理解，並未得到證實。而Chris Lomont則在他的論文中詳細討論了最後那個方程的解法，並嘗試在實際的機器上尋找最佳的常數C。有興趣的朋友可以在文末找到他的論文的鏈接。

所以，所謂的Magic Number，並不是從N元宇宙的某個星系由於時空扭曲而掉到地球上的，而是幾百年前就有的數學理論。只要熟悉NR和泰勒級數，你我同樣有能力作出類似的優化。

在http://GameDev.net上有人做過測試，該函數的相對誤差約為0.177585%，速度比C標準庫的sqrt提高超過20%。如果增加一次迭代過程，相對誤差可以降低到e-004 的級數，但速度也會降到和sqrt差不多。據說在DOOM3中，Carmack通過查找表進一步優化了該演算法，精度近乎完美，而且速度也比原版提高了一截（正在努力弄源碼，誰有發我一份）。

值得注意的是，在Chris Lomont的演算中，理論上最優秀的常數（精度最高）是0x5f37642f，並且在實際測試中，如果只使用一次迭代的話，其效果也是最好的。但奇怪的是，經過兩次NR後，在該常數下解的精度將降低得非常厲害（天知道是怎麼回事！）。經過實際的測試，Chris Lomont認為，最優秀的常數是0x5f375a86。如果換成64位的double版本的話，演算法還是一樣的，而最優常數則為0x5fe6ec85e7de30da（又一個令人冒汗的Magic Number - -b）。

這個演算法依賴於浮點數的內部表示和位元組順序，所以是不具移植性的。如果放到Mac上跑就會掛掉。如果想具備可移植性，還是乖乖用sqrt好了。但演算法思想是通用的。大家可以嘗試推算一下相應的平方根演算法。

下面給出Carmack在QUAKE3中使用的平方根演算法。Carmack已經將QUAKE3的所有源代碼捐給開源了，所以大家可以放心使用，不用擔心會受到律師信。
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－
//
// Carmack在QUAKE3中使用的計算平方根的函數
//
float CarmSqrt(float x){
union{
int intPart;
float floatPart;
} convertor;
union{
int intPart;
float floatPart;
} convertor2;
convertor.floatPart = x;
convertor2.floatPart = x;
convertor.intPart = 0x1FBCF800 + (convertor.intPart &>&> 1);
convertor2.intPart = 0x5f3759df - (convertor2.intPart &>&> 1);
return 0.5f*(convertor.floatPart + (x * convertor2.floatPart));
}
－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－－

故事還沒完，普渡大學的數學家Chris Lomont看了以後也覺得很有趣，決定要研究一下卡馬克弄出來的這個猜測值有什麼奧秘。Lomont也是個牛人，在精心研究之後從理論上也推導出一個最佳猜測值，和卡馬克的數字非常接近, 0x5f37642f。Lomont計算出結果以後非常滿意，於是拿自己計算出的起始值和卡馬克的神秘數字做比賽，看看誰的數字能夠更快更精確的求得平方根。結果居然還是卡馬克贏了...

最後Lomont怒了，採用暴力方法一個數字一個數字試過來，終於找到一個比卡馬克數字要好上那麼一丁點的數字，雖然實際上這兩個數字所產生的結果非常近似，這個暴力得出的數字是0x5f375a86。

Lomont為此寫下一篇論文，"Fast Inverse Square Root"。論文詳見：http://www.matrix67.com/data/InvSqrt.pdf。


除此之外還有卡馬克捲軸演算法等，更多關於卡馬克的事迹可以在google上找到很多。


你們還可看看他兒子的主頁 : http://www.1k3c.com/，這稚嫩的筆觸，極高的顏值，和這編程技術讓人感慨大神就是不一樣。

Behavior Trees (Artificial Intelligence, Robotics and Control) 行為樹

你先搞清楚你是去做遊戲引擎還是做遊戲。。。
做遊戲引擎需要懂比較全面的圖形圖像學知識，熟悉opengl相關演算法，各種開源引擎中實現的演算法
做遊戲更多的是要懂的軟體工程學，某種引擎的熟練使用，引擎內部實現其實了解性的懂的就夠了
中國現在的自主引擎基本上都是在一些國外開源引擎基礎上修改得來（我只知道當年騰訊的引擎是ogre改的，其它公司就不太清楚了，現在騰訊不知道還在搞引擎開發不）
重點不抓住是干不好活的

Bin Packing

Trie樹，專業坑聊天30年

神經網路 遺傳演算法 帶你裝B帶你飛

雷神III卡馬克大神平方根演算法

float Q_rsqrt( float number )
{
long i;
float x2, y;
const float threehalfs = 1.5F;
x2 = number * 0.5F;
y = number;
i = * ( long * ) y; // evil floating point bit level hacking
i = 0x5f3759df - ( i &>&> 1 ); // what the fuck?
y = * ( float * ) i;
y = y * ( threehalfs - ( x2 * y * y ) ); // 1st iteration
// y = y * ( threehalfs - ( x2 * y * y ) ); // 2nd iteration, this can be removed
#ifndef Q3_VM
#ifdef __linux__
assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
return y;
}

放心吧,國內遊戲公司的水平,基本用不上抬高大上的演算法. 體力活居多.
寫遊戲主要靠工具.和時間.

float-&>int

狀態機啊

有限狀態機,模糊狀態機,遺傳演算法,BP網路,戰術A*,.........

平方根倒數演算法放出來。這也是我第一個想法. @matrix67 的博客曾經有精彩的介紹.

CTRLCCTRLV演算法

將depth 值存儲在texture的RGBA
分量中演算法

已出現卡馬克大深度的平方根演算法

借寶地問個問題，《3D遊戲編程大師》中在介紹計算兩點距離演算法時提到可以用泰勒公式來獲得一個多項式加法形式的近似演算法，但沒有給出任何推導過程。不知道有沒有達人給介紹一下是如何推導的？

這些玩意用的很少，不如先寫個快速排序，紋理打包演算法實惠

還有導航網格演算法

想太多了，國內的遊戲開發大多都是調用現成的api，用用現成的框架，有開源的用開源的，幾乎不會自己動手寫的，題主不用擔心，不過私下可以自己學習一下演算法。

平方根倒數演算法

推薦閱讀：

※為什麼很多人喜歡 Python？
※你最痛苦的一次找程序 bug 的經歷是哪次？
※怎麼將 Android 程序做成插件化的形式？
※30 歲才開始學習編程靠譜嗎？
※2013 年 7 月的 Struts2 漏洞實際帶來多大影響？

TAG:演算法 | 編程 | 計算機圖形學 | 遊戲編程 |