Doing the FizzleFade effect using a Feistel network
antirez.com
antirez.com
For example, with 320x200, you'd do something like (completely untested)
for (var i = 0; i < 8; i++) {
l = input / 320;
r = input % 320;
var nl = r;
var F = (r * 356357 + i * 1234567) % 200;
r = (l + F) % 200;
l = nl;
input = 200*l + r;
}
This would be true when using the built-in random number generator, modding the result to a pixel on the screen.
However, this is not how the "maximum-length" LFSR proposed in the original article works. It visits each pixel exactly once, and turns the screen completely red in a deterministic amount of time. (Just see the screenshot here: http://fabiensanglard.net/fizzlefade/die.gif)
This behavior is indicated from the stopping condition in the Wolf3D asm code alone -- the seed starts at 1. It terminates when the random number returns to 1, completing the cycle through the number space.
He was pointing out that the naive method is slow, not saying that that's how Wolfenstein 3D did it, and quite clearly stated that the original code used an LFSR
One thing:
> Doing this with a pseudo random generator, as noted in the blog post, is slow, but is also visually very unpleasant, since the more red pixels you have on the screen already, the less likely is that you hit a new yet-not-red pixel, so the final pixels take forever to turn red
I'm not sure if the author of this article was confused by the original article, or if the wording is just weird here, but...
The original article presents Wolfenstein's algorithm which _is_ fast and efficient, and which fills the screen lineraly. It visits each pixel on the screen, in random order, exactly once. And it does it using just a conditional and an XOR.
The technique scales to any resolution (we have maximum-length LFSR for any number of bits you'd need).
So there were no problems to be solved here. Wolfenstein already solved them.
Feistel networks are interesting, but ... they don't solve this problem any better than Wolfenstein's LFSR technique. Both can scale to any resolution in exactly the same way. But Feistel networks are terribly inefficient for this task. It's hard to beat a conditional + XOR per pixel.
Hello, yes probably I was not clear, I was trying to say why both the original article referred code, and my approach, was no just setPixel(rand(),rand()).
About my approach, what it solves is that you can do that for any resolution without finding a max length LFSR of the appropriate size. See the section of the original article where ports are mentioned.
https://en.wikipedia.org/wiki/Linear-feedback_shift_register...
We have LFSRs for ... well more than anyone could ever need.
EDIT: To be clear, I still think your article is really cool and useful for bringing up the topic of Feistel networks!
The context is related to these notes [1]:
> Note : Because the effect works by plotting pixels individually, it was hard to replicate when developers tried to port the game to hardware accelerated GPU. None of the ports managed to replicate the fizzlefade except Wolf4SDL, which found a LFSR taps configuration to reach resolution higher than 320x200.
> Note : The tap configuration on 17 bits generates 131,072 values before cycling. Since 320x200=64000, it could have been implemented with a 16 bits Maximum-length register with taps on 16,15,13 and 4 (in "Galois" notation.). My assumption is that LFSR literature was hard to come across in 1991/1992 and finding the correct tap for a 16 bit maximum length register was not worth the effort.
* pick number of frames (say, 24)
* for each pixel, (pseudo)randomly pick which frame it turns red on (0-23), gathering them into a list for that frame (0 -> [1, 1024, 1048576],...)
* paint the list for each frame in order
Still has the property that each pixel is drawn only once. Also has the property that you're guaranteed to terminate in a fixed amount of frames. Also works for any resolution.
Is it because there'll be a short pause as you calculate everything? (probably unnoticeable now, but noticeable then) Or is it because you essentially need to hold the whole thing in memory until the end?
It's probably the latter, I suppose, that's the problem, since if you have k pixels, you need log k bits to address each pixel so you need k log k memory. That's a whopping 15 million bits (2 megs about) for this op alone on a 1024x768. Okay, then.