今天我读到一篇有趣的文章，介绍 Wolfenstein 3D 游戏如何使用 Linear Feedback Shift Register(线性反馈移位寄存器，LFSR)实现淡出效果。屏幕上的每个像素都会以伪随机的方式变成红色，直到整个屏幕都变红（或者根据游戏中发生的事件变成其他颜色）。介绍这一实现的博文链接如下，值得一读：http://fabiensanglard.net/fizzlefade/index.php

你可能会好奇，为什么原始代码使用 LFSR，或者为什么我要提出另一种方法，而不是直接使用普通的 setPixel(rand(),rand())：正如那篇博文中所指出的，使用伪随机生成器实现这一效果速度很慢，而且视觉效果也非常糟糕，因为屏幕上已经有越多红色像素，就越不容易命中新出现的、尚未变红的像素，所以最后那些像素要花很长时间才能变红（我敢打赌，那篇博文的许多读者在 Spectum、C64 的旧时代，或者后来使用 QBASIC 或 GWBasic 时都尝试过这种做法）。在博文的最后一部分，作者写道：

“由于这一效果是通过逐个绘制像素实现的，所以开发者尝试将游戏移植到硬件加速 GPU 时，很难复现它。所有移植版本中，只有 Wolf4SDL 成功复现了 fizzlefade；它找到了一个 LFSR 抽头配置，使其能够达到高于 320x200 的分辨率。”

这虽然算不上什么高深的技术，但对于其他分辨率来说，找到合适的 LFSR 可能确实很困难。不过，无论为其他分辨率寻找合适的 LFSR 到底有多复杂，移植版本的作者都可以使用另一种称为 Feistel Network(Feistel 网络)的技术，以一种非常简单的方式得到完全相同的结果。

什么是 Feistel Network？

它是密码学中通常使用的一种构件：它在一组比特序列与另一组比特序列之间建立变换，因此即使在 Feistel 网络内部使用各种非线性变换，这种变换也始终可逆。实际来说，Feistel 网络可以例如根据某个函数 F()，将一个 32 位数 A 转换为另一个 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 的问题有什么用呢？你可以把二维屏幕想象成一个像素线性数组。如果分辨率像原始游戏一样是 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”只是一些随机的乘法和移位，大多是随手选的。即使使用更好的 F 函数可能不需要这么多轮，我仍然使用 8 轮，因为我希望效果看起来是随机的（巧合的是，绘制随机像素是直观发现简单分布缺陷的一种不错的方法）。

使用 Javascript canvas 实现时，我们还需要几个函数，以获取二维上下文并设置像素。

最终代码位于这个 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）。这是程序员脑海中的工具箱里值得拥有的一个好工具。