Re: [閒聊] 老遊戲的變態程式碼

[RockZelda (洛克薩爾達)]

※ 引述 《Senkanseiki》 之銘言：
: 標題：[閒聊] 老遊戲的變態程式碼
: 時間: Tue Jul 22 16:45:40 2025
: 
: https://www.youtube.com/watch?v=n2Q1Sp7iew4
: https://en.wikipedia.org/wiki/Fast_inverse_square_root
: 
: 1999年製作的一款遊戲：Quake III Arena
: 在遊戲開發者之間，這款遊戲的程式碼成為了熱門話題
: 因為下面這個求1/√x的程式碼實在太變態了而讓大家頗為驚訝
: 
: 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
: 
:         return y;
: }

這個東西很有名的，是雷神之鎚3的「反平方根快速演算法」
https://bit.ly/4f6pYx0
其實目的就是要計算1/ √x的數值

比方說，如果x=9，因為√9=3，1/√x就等於1/3，大約是0.3333…
所以9的反平方根就是0.3333…

看起來很簡單吧？
但反平方根這個東西，最大用途是計算遊戲內部的光影變化
——————
太複雜的內容就不說太細，簡單說一個概念
「光的漫射」
舉現實的例子來說，用手電筒照牆壁
>你光源直接照牆壁，會很亮
>稍微斜著照，牆就沒那麼亮
>照牆的背後，當然完全不會亮
https://i.imgur.com/8aMtyTK.jpeg
以前國中物理還記得的話，上面的虛線就是光的法線
實際物理計算上，需要知道入射光的方向角度和法線夾角、才能知道反射光的方向，以及整
體漫射後光影強度

那怎麼用數學計算呢？
就是高中數學的「向量」還有「內積」
忘記的可以去翻翻以前的課本或教科書w

總之，計算漫射光強度公式大概這樣
https://i.imgur.com/siNXtY8.jpeg
可以把公式看成是遊戲內的「亮度計」

為了讓計算準確，牆的朝向和光線方向都需要要「標準化」
換言之，需要計算單位向量（向量座標除於向量本身的長度）
https://i.imgur.com/uh46f3v.jpeg
然後很自然的，就需要用到平方根的值
https://i.imgur.com/cBozOny.jpeg
這就是反平方根的角色——幫忙快速把向量縮到標準長度

而且這樣計算可以直接算出光線與牆的「對齊程度」，不用真的去量角度，或是更複雜的三
角函數計算
省去了計算的時間
——————
不過以上說的是物理和數學概念
這個程式碼厲害的地方是，在當時那個年代之中，用最少的計算成本來算出需要的平方根

這部分我就不太清楚，只簡單說一下
當x的值輸入後，程式碼不是直接帶入數字，而是「駭入」到位元層級
:         i  = * ( long * ) &y;                       // evil floating point bit
: level hacking

然後以魔術數字「0x5f3759df」為起點
這是16進位的數字，對應十進制的1597463007
套用公式直接找出平方根的初始值
:         i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
:         y  = * ( float * ) &i;

當然，這樣可能還有誤差，於是還有兩次校正，用到的就是牛頓法
提高y的精準值，提升平方根的準確度
:         y  = * ( float * ) &i;
:         y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
: //      y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can
: be removed

整個計算法神秘的是，當初是怎麼找到
魔術數字「0x5f3759df」的？
雖然有人說是作者卡馬克寫的，但實際情況是…

約翰.卡馬克：我他媽的怎麼知道！

對，沒有人知道是哪個天才寫的程式嗎
但因為很好用所以就留著了,只有後來工程師看到內容後，留下很有名的註解
//what the fuck ?
https://i.imgur.com/U8vUDEP.jpeg
——————
有錯誤的就麻煩指正一下w

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.219.68.127 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/C_Chat/M.1753179889.A.236.html
推 dyhard: 嗯嗯  跟我想的差不多
推 AirForce00: 嗯嗯 我完全明白了
推 sukicolo: 嗯嗯嗯~數學就是這麼實用的存在你我的身邊，我懂了
推 nineflower: 以前遊戲容量小都出現一堆鬼神函式
推 doremon1293: 世界上只有數學不會騙你 不會就是不會
→ kaj1983: 懂了，藝術就是看不懂的東西
推 pponywong: 不只這個 還有 fast sin, fast cos
推 fff417: 跟我想得差不多 就WTF嘛
推 ymsc30102: 我逐漸理解一切了
推 orze04: 0x5f3759df - ( i >> 1 ) 這個就已經很近了，不然你要多
→ orze04: 迭代好幾次
推 jokerjuju: 嗯嗯 和我理解的差不多
推 orze04: 所以才會說，程式能用、會動就不要改他
推 jay920314: 傳說中的WTF代碼
→ cc9i: cool喔 沒想到還有維基百科
推 LunaDance: 其實那個魔術數字應該用浮點數解釋 大約是3/2*（2^23
→ LunaDance: ）*（127-0.0450466） 最後那個很醜的小數才是調整用
→ LunaDance: 的魔術數字 前面其他都是在補正浮點數硬轉的類對數運
→ LunaDance: 算的乘數與常數
推 knight90496: 嗯嗯 沒錯（實際上完全沒聽懂
推 iampig951753: evil floating point haha
推 b1izzard2000: 嗯嗯 和我想的差不多（空白
推 Qorqios: 嗯嗯 餐斤巾寫不下
推 NJI: 都看得懂但又看不懂推
推 bbo6uis122: 太酷了吧
→ bbo6uis122: 以後誰說學數學沒用就打斷他的腿
推 joy3252355: 雷神之槌這個例子非常有名 但很少看到淺顯易懂的解說