1. 27

  2. 5

    In the Hacker News comments for this article, antirez linked an alternative approach using a Feistel network that works for any resolution: http://antirez.com/news/113

    1. 5

      Like the original code, Antirez’s approach uses power-of-two width and height and discards values that are out-of-range, but you can even build a Feistel-like function with non-power-of-two range and domain (e.g., input and output are points on a 1920x1080 screen) using modular addition instead of XOR. In pseudocode, it’s

        for 1..rounds:
          x += f(y) mod maxX
          y += f(x) mod maxY

      and for the inverse, you swap the steps and subtract instead of adding (with wraparound for negative results)

        for 1..rounds:
          y -= f(x) mod maxY
          x -= f(y) mod maxX

      Since it’s invertible, it’ll cover every output in its range if you give it every input. (If you want, you can use different functions at each step and throw in other kinds of invertible step entirely, like x *= n mod maxX where n and maxX share no prime factors.)

      It’s slow. Besides doing more work than Wolf3D’s LFSR, all the divisions to keep the results in range are more expensive than just throwing away out-of-range results like Antirez’s code. Still a fun trick. Here’s a concrete example of a function like this in JavaScript:

        function f(x, y) {
          for (var i = 0; i < 4; i++) {
              y += (x * 0x555) >> 3;
              y %= maxY;
              x += (y * 0x555) >> 3;
              x %= maxX;
          return [x, y]
        function inverseF(x, y) {
          for (var i = 0; i < 4; i++) {
              x -= (y * 0x555) >> 3;
              x %= maxX;
              if (x<0) x+=maxX; // % operator doesn't wrap negative values for us
              y -= (x * 0x555) >> 3;
              y %= maxY;
              if (y<0) y+=maxY;
          return [x, y]
        >> f(3, 3)
        [1370, 207]
        >> inverseF(1370,207)
        [3, 3]

      I might’ve messed some overflow case or something up, and you can probably make a permutation look fine with a lot less, but there’s the idea.

    2. 2

      This would be a great animation for use in switching between screens on Android.

      You know, the screen transition effect that happens as you swipe, so that if you hold your swipe in the middle, the animation pauses in the middle, and if you abort the swipe or go backwards, the animation plays backwards?

      Though, I think I’d “tile” it so that it’s hitting multiple pixels across the screen at once. Let me know if I should draw a picture to describe that… A naive implementation would hit the same (relative) pixel in each tile, which might look cool. A fancy implementation might “rotate” the pixel offset for each tile so that each target pixel is in a different location in each tile. Playing with the tile size (which maps to “number of pixels being written in parallel”) would be necessary to keep the animation duration within appropriate bounds for the screen transition effect.

      1. 3

        I think you could implement something fast in a shader by just having a single channel noise texture with values from 0-1, and over time you bring up the minimum values that are faded, ie. at the start t=0 so all values are above the threshold and we see 100% scene, then when t=1 all values are below the threshold and the screen is 100% faded. The noise texture could be 64x64 repeating or anything up to the full screen size, though you would get diminishing returns after a bit.