今日、Wolfenstein 3DがLinear Feedback Shift Register（LFSR）を使ってフェードエフェクトをどのように実装していたかについての興味深い記事を読みました。画面の各ピクセルが擬似ランダムに赤く塗られ、やがて画面全体が赤一色になります（ゲーム内のイベントによっては他の色になる場合もあります）。実装を解説したブログ記事はこちらで、とても面白い内容です。http://fabiensanglard.net/fizzlefade/index.php

なぜオリジナルのコードがLFSRを使っていたのか、あるいはなぜ私が単純にsetPixel(rand(), rand())とするのではなく別の手法を提案するのか、疑問に思われるかもしれません。ブログ記事でも指摘されているとおり、擬似乱数生成器でこれを行うと遅いだけでなく、見た目も非常に悪くなります。すでに赤く塗られたピクセルが増えるほど、まだ塗られていないピクセルに当たる確率が下がり、最後の数ピクセルが赤くなるまでに気の遠くなるような時間がかかってしまうからです（SpectrumやC64、あるいは後年のQBASICやGW-Basicで、*きっと*このブログの読者の多くが昔試したことがあるはずです）。ブログ記事の最後で、著者は次のように書いています。

このエフェクトはピクセルを1つずつ描画することで成り立っているため、ハードウェアアクセラレーションを備えたGPUへゲームを移植する際に再現するのが困難でした。Wolf4SDLを除き、どの移植版もfizzlefadeを再現できませんでした。Wolf4SDLだけが、320x200を超える解像度に対応するLFSRのタップ構成を見つけ出したのです。

ロケットサイエンスというわけではありませんが、他の解像度に適したLFSRを見つけるのは難しかったのかもしれません。しかし、他の解像度向けに適切なLFSRを見つけることが実際にどれほど複雑だったかはさておき、移植版の作者たちは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ビットの整数をLとRという2つの8ビット整数に分割し、Nラウンドにわたって変換を行い、再び1つの16ビット整数に合成して出力とします。

では、これがFizzleFadeの実装にどう役立つのでしょうか。2次元の画面をピクセルの一次元配列として考えてみてください。オリジナルのゲームのように解像度が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ビットの入出力に対応させるため、LとRの変数をそれぞれ10ビットに変更する必要がありますが、それ以外はほぼ同じです。ただし、停止条件（フレーム数をチェックしている部分）も変更することを忘れないでください。

実は、Feistelネットワークの1対1の擬似ランダムな写像という性質は、他の場面でも非常に役立ちます。たとえば、私はradix treeの実装テストでもこれを使いました（ご興味があればhttps://github.com/antirez/raxをご覧ください）。プログラマの道具箱に入れておくと便利なテクニックの一つです。