6 ms·

Doing the FizzleFade effect using a Feistel network

82 points by darwhy 9y ago

deleted 9y ago
[deleted]
fpgaminer 9y ago
This is a great look into Feistel networks! 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.
- antirez 9y ago
  > 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... 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.
  - fpgaminer 9y ago
    > 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. https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Some_polynomials_for_maximal_LFSRs 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!
    - wyldfire 9y ago
      But I guess the point is that each of those LFSRs have a different polynomial and this is a general solution. 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. [1] http://fabiensanglard.net/fizzlefade/index.php http://fabiensanglard.net/fizzlefade/index.php
pbsd 9y ago
(Generalized) Feistel networks have to be neither balanced nor over bits (see, e.g., [1]), so you could conceivably devise a 'perfect' permutation for any particular resolution. 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; } which is not exactly fast or anything, but covers your domain perfectly. [1] https://eprint.iacr.org/2010/301 https://eprint.iacr.org/2010/301
- deleted 9y ago
  [deleted]
- Scaevolus 9y ago
  Yes, this works well! http://jsbin.com/xepefubuyu/2/edit?js,output http://jsbin.com/xepefubuyu/2/edit?js,output
- antirez 9y ago
  This is great! Thanks.
- antirez 9y ago
  Off topic: @pbsd your comment history is amazing for quality, topics covered and so forth, it's a shame you have no "about" section in the HN account, I bet many people would be glad to be able to follow your Blog / Twitter / whatever. I also respect people that don't want exposure, so take this just as an appreciation comment in case you don't like the suggestion.
sevensor 9y ago
This could be quite useful for a project I'm working on. Sampling an n-dimensional grid -- currently I switch over to exhaustive sampling from random sampling after I bounce off already-sampled points enough times. But a sampling technique that's both exhaustive and random-ish is the best of both worlds.
arjie 9y ago
Out of curiosity, why not the idea of: * 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.
- deleted 9y ago
  [deleted]
- tinus_hn 9y ago
  Needs a 'lot' (which is relative, of course) of memory, slow (because you have to precalculate and also read all that memory every frame) and there is a more lightweight solution.
  - arjie 9y ago
    Not all the memory each frame, right? You only read once to calculate and then read the entire memory once again to write.
    - tinus_hn 9y ago
      No, you have to calculate once and then read and compare the value for each pixel every frame to decide if it's time to turn it on. It can probably be done because the system doesn't really have anything else to do on a game over screen but it's still a waste.
      - arjie 9y ago
psyklic 9y ago
> 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 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 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.
- Vendan 9y ago
  > You may wonder why the original code used a LFSR or why I'm proposing a different approach, instead of the vanilla setPixel(rand(),rand()): doing this with a pseudo random generator, as noted in the blog post, is slow 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

82 points by darwhy 9y ago

deleted 9y ago

[deleted]

This is a great look into Feistel networks! 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.

antirez 9y ago
> 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... 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.
- fpgaminer 9y ago
  > 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. https://en.wikipedia.org/wiki/Linear-feedback_shift_register#Some_polynomials_for_maximal_LFSRs 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!
  - wyldfire 9y ago
    But I guess the point is that each of those LFSRs have a different polynomial and this is a general solution. 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. [1] http://fabiensanglard.net/fizzlefade/index.php http://fabiensanglard.net/fizzlefade/index.php

pbsd 9y ago

(Generalized) Feistel networks have to be neither balanced nor over bits (see, e.g., [1]), so you could conceivably devise a 'perfect' permutation for any particular resolution. 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; } which is not exactly fast or anything, but covers your domain perfectly. [1] https://eprint.iacr.org/2010/301 https://eprint.iacr.org/2010/301

deleted 9y ago
[deleted]
Scaevolus 9y ago
Yes, this works well! http://jsbin.com/xepefubuyu/2/edit?js,output http://jsbin.com/xepefubuyu/2/edit?js,output
antirez 9y ago
This is great! Thanks.
antirez 9y ago
Off topic: @pbsd your comment history is amazing for quality, topics covered and so forth, it's a shame you have no "about" section in the HN account, I bet many people would be glad to be able to follow your Blog / Twitter / whatever. I also respect people that don't want exposure, so take this just as an appreciation comment in case you don't like the suggestion.

sevensor 9y ago

This could be quite useful for a project I'm working on. Sampling an n-dimensional grid -- currently I switch over to exhaustive sampling from random sampling after I bounce off already-sampled points enough times. But a sampling technique that's both exhaustive and random-ish is the best of both worlds.

arjie 9y ago

Out of curiosity, why not the idea of: * 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.

deleted 9y ago
[deleted]
tinus_hn 9y ago
Needs a 'lot' (which is relative, of course) of memory, slow (because you have to precalculate and also read all that memory every frame) and there is a more lightweight solution.
- arjie 9y ago
  Not all the memory each frame, right? You only read once to calculate and then read the entire memory once again to write.
  - tinus_hn 9y ago
    No, you have to calculate once and then read and compare the value for each pixel every frame to decide if it's time to turn it on. It can probably be done because the system doesn't really have anything else to do on a game over screen but it's still a waste.
    - arjie 9y ago

psyklic 9y ago

> 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 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 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.

Vendan 9y ago
> You may wonder why the original code used a LFSR or why I'm proposing a different approach, instead of the vanilla setPixel(rand(),rand()): doing this with a pseudo random generator, as noted in the blog post, is slow 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