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

你可能會好奇，為什麼原始程式碼要使用 LFSR，或為什麼我要提出另一種做法，而不是直接使用最基本的 setPixel(rand(),rand())：如該部落格文章所指出的，用偽隨機產生器來做這件事不僅速度慢，在視覺上也非常不討喜，因為螢幕上已經變紅的像素越多，就越不容易隨機命中一個尚未變紅的像素，所以最後幾個像素要花很久才會變紅（我*敢打賭*這篇部落格文章的許多讀者在早年使用 Spectrum、C64，或後來使用 QBASIC 或 GWBasic 時都曾嘗試過這種做法）。在該部落格文章的最後一部分，作者寫道：

「由於這個效果是透過逐一繪製像素來運作，當開發者嘗試將遊戲移植到硬體加速的 GPU 時，很難重現這個效果。除了 Wolf4SDL 之外，沒有任何移植版本成功重現 fizzlefade，Wolf4SDL 找到了一組 LFSR 抽頭配置，得以支援高於 320x200 的解析度。」

雖然這並非什麼高深的學問，但要為其他解析度找到合適的 LFSR 可能確實不容易。不過，無論為其他解析度尋找合適 LFSR 的實際複雜度如何，移植版的作者們其實可以用另一種稱為 Feistel Network(費斯托網路) 的技術，以極其簡單的方式獲得完全相同的結果。

什麼是 Feistel Network？

它是密碼學中常用的基本組成結構：它能在一個位元序列與另一個位元序列之間建立轉換，而且即使你在 Feistel network 內部使用各種非線性轉換，這個轉換始終是可逆的。用實務上的說法來舉例，Feistel network 可以根據某個函式 F()，將一個 32 位元的數字 A 轉換成另一個 32 位元的數字 B，讓你之後總能從 B 回推到 A。由於這個函式是可逆的，這意味著對於每一個輸入值，Feistel network 都會產生*不同*的輸出值。

以下是一個簡單的 Feistel network 虛擬碼：

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 network 回傳的位置上，就能產生看起來隨機的像素位置。問題在於 Feistel network 是以位元為單位運作的，所以我們無法剛好得到 0 到 63999 的範圍，必須選擇一個夠大的 2 的次方。這個例子中最接近的是 16：使用 16 個位元，我們就有 65536 種整數對整數的轉換，會有少數幾個週期不會用來設定實際的像素，但並不算太大的浪費。

那麼，我們的 Feistel network 用 JavaScript 寫起來會像這樣：

/* 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」只是幾個隨機挑選的乘法與位移運算，大多是隨意選的。即使搭配更好的 F 函式，或許不需要用到 8 輪，我還是用了 8 輪，因為我希望效果看起來夠隨機（順帶一提，繪製隨機像素剛好是直觀地發現明顯分布不均問題的不錯方法）。

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

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

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

本文原本想探討的問題，是要找到一種能在不同解析度下實現此效果的方法，所以即使這只是 320x200 情況的簡單延伸，舉例來說，假設你想在 1024*768 的解析度下實現同樣的效果。這會有 786432 個像素，因此 2^20 的 1048576 種可能的整數會相當合適。我們必須將 Feistel network 修改為 20 位元的輸入／輸出，也就是使用 10 位元的 L 和 R 變數，其他部分則大致相同，但記得也要修改停止條件（用來檢查影格數量的那個條件）。

其實，Feistel network 一對一的偽隨機對映特性在其他情境中也非常有用。舉例來說，我在自己的 radix tree(基數樹) 實作測試中就用到了它（如果你好奇的話，專案在 https://github.com/antirez/rax）。這是程式設計師工具箱中值得擁有的一項好工具。