今天我讀到一篇有趣的文章，講的是《Wolfenstein 3D》如何利用線性回饋移位暫存器（Linear Feedback Shift Register）來實作淡出效果。畫面上的每個像素會以偽隨機的方式被設為紅色，直到整個螢幕都變成紅色（或依遊戲中發生的事件變成其他顏色）。介紹這個實作的部落格文章在這裡，值得一讀：http://fabiensanglard.net/fizzlefade/index.php

你可能會好奇，為什麼原始程式碼要用 LFSR，又為什麼我要提出另一種做法，而不是直接用最單純的 setPixel(rand(),rand())：如該篇文章所指出的，用偽隨機產生器來做這件事不只慢，視覺上也非常糟糕，因為畫面上已經變紅的像素越多，就越難隨機命中還沒變紅的像素，導致最後幾個像素要花很久才會變紅（我*敢打賭*很多讀過這篇文章的人，以前在 Spectrum、C64 的時代，或後來用 QBASIC、GWBasic 時都試過這種做法）。在文章的最後，作者寫道：

「由於這個效果是靠逐一繪製像素來實現的，當開發者嘗試將遊戲移植到硬體加速的 GPU 上時，很難重現這個效果。除了 Wolf4SDL 找到一組能支援高於 320x200 解析度的 LFSR 分接頭（taps）設定之外，沒有任何移植版本成功重現 fizzlefade。」

雖然這不是什麼高深的學問，但要為其他解析度找到合適的 LFSR，可能確實有點麻煩。不過，無論為其他解析度尋找合適 LFSR 的實際難度如何，移植版本的作者其實可以用另一種叫做 Feistel 網路（Feistel Network）的技術，用極其簡單的方式達到完全相同的效果。

什麼是 Feistel 網路？

它是密碼學中常用的一種基本結構：它能在一段位元序列與另一段位元序列之間建立轉換，而且無論你在 Feistel 網路內部用了什麼樣的非線性轉換，這個轉換永遠是可逆的。白話來說，Feistel 網路例如可以把一個 32 位元的數字 A，依照某個函式 F() 轉換成另一個 32 位元的數字 B，之後你永遠可以再從 B 還原回 A。因為這個函式是可逆的，也就意味著對於每一個輸入值，Feistel 網路都會產生*不同*的輸出值。

這是一個用虛擬碼表示的簡單 Feistel 網路：

Split the input into L and R halves (Example: L = INPUT & 0xFF, R = INPUT >> 8)
REPEAT for N rounds:
    next_L = R
    R = L XOR F(R)
    L = next_L
END
RETURN the value composing L and R again into a single sequence of bits: R<<8 | L

所以基本上，我們把一個（例如）16 位元的整數拆成兩個 8 位元的整數 L 和 R，進行 N 輪轉換後，再把它們重新組合成一個 16 位元的整數，也就是我們的輸出。

但這對我們實作 FizzleFade 的問題有什麼幫助呢？ 你可以把 2D 螢幕想像成一個線性的像素陣列。如果解析度像原版遊戲一樣是 320x200，你就有從像素 0 到像素 63999。所以對於從 0 到 63999 的每一個整數，我們只要依序計數，並把 Feistel 網路回傳的位置上的像素設為指定顏色，就能產生一個看起來隨機的像素位置。問題在於 Feistel 網路是以位元為單位運作的，所以我們無法剛好得到 0 到 63999 的範圍，必須選一個夠大的 2 的次方數。在這個例子中最接近的是 16：用 16 位元我們就有 65536 種整數對整數的轉換，雖然會有少數幾個週期不會對應到實際的像素，但浪費並不大。

所以，我們用 JavaScript 寫出來的 Feistel 網路長這樣：

/* Transforms the 16 bit input into another seemingly psenduo random number
 * in the same range. Every input 16 bit input will generate a different
 * 16 bit output. This is called a Feistel network. */
function feistelNet(input) {
    var l = input & 0xff;
    var r = input >> 8;
    for (var i = 0; i < 8; i++) {
        var nl = r;
        var F = (((r * 11) + (r >> 5) + 7 * 127) ^ r) & 0xff;
        r = l ^ F;
        l = nl;
    }
    return ((r<<8)|l)&0xffff;
}

我使用的非線性轉換「F」其實只是幾個隨意挑選的乘法與位移運算，大致上是隨便選的。我用了 8 輪，雖然如果 F 函式設計得更好，應該不需要這麼多輪，但我希望效果看起來夠隨機（順帶一提，隨機地繪製像素其實是個不錯的方法，可以直觀地看出分布是否太過糟糕）。

要用 JavaScript 的 canvas 來實作這個效果，我們還需要幾個額外的函式來取得 2D 繪圖環境並設定像素。

最終的完整程式碼放在這個 Gist：https://gist.github.com/antirez/6d58860b221a6ae5622ced8ccdddbe47

你可以在這裡看到執行結果：http://antirez.com/misc/fizzlefade.html

這篇文章原本想探討的問題，是如何在不同解析度下實作這個效果，所以即使這只是 320x200 情況的簡單延伸，為了舉例，假設你想在 1024*768 的解析度下實作同樣的效果。總共有 786432 個像素，所以 2^20 的 1048576 種可能整數就相當合適。我們只要把 Feistel 網路改成處理 20 位元的輸入／輸出，也就是使用各 10 位元的 L 和 R 變數，其他部分大致上都一樣，不過別忘了也要修改停止條件（用來檢查已執行的影格數）。

其實，Feistel 網路這種一對一偽隨機對應的特性在其他場合也非常有用。舉例來說，我在自己的 radix tree 實作測試中就用過它（有興趣的話可以在這裡看到：https://github.com/antirez/rax）。這是個值得放進程式設計師工具箱的好工具。