[gxmkhjal] random walk to every pixel

do a random walk on a toroidal grid until every cell is visited.  color the cells according to when last visited.  inspired by the "wander" xscreensaver hack.

the resulting images straddle the border between order and disorder.  there are patches of similar color but large scale randomness.  the images also tell a linear "story", the long random walk of a single particle.  old history gets forgotten, overwritten.  all of these are similar to the human experience.

small attempt first: 480x360 toroidal universe, color palette cycling around the saturated RGB colors.  (previously: perhaps saturated colors are not the best idea.)  let N = 480 * 360 = 172800 = number of pixels.  in the images below, the color palette cycles over 0.01N, 0.02N, 0.05N, 0.1N, 0.2N, 0.5N, N, 2N, 5N, 10N, and 20N steps.  the rate of color cycling determines typical color patch size.  it took 8038402 steps, about 46.5N, until every pixel was visited.

0.01N

0.02N

0.05N

0.1N

0.2N

0.5N

N

2N

5N

10N

20N

here is a grayscale image with no color palette cycling.  brightness is proportional to step count when last visited.

here are just last 2N steps.  color palette inspired by black body radiation.

large attempt: 60480x45360 toroidal universe.  it took 405307726447 steps, or 147.7N to visit every pixel.  many hours of computation and a lot of RAM.  intermediate text data file after before and after compression with plzip --best: 31670040878 and 4541602801 bytes respectively.  dimensions chosen to have many factors, allowing reduction by many possible integer factors.  we reduced by 126 to yield 480x360 images, same size as above.

incidentally, JPEG compression, even at quality 95, results in very noticeable image degradation (not shown).  this is probably because of chroma downscaling, and maybe because JPEG cannot represent all colors.  we chose Webp in the images below because it losslessly compresses somewhat better than PNG.  useful were graphicsmagick, cwebp and dwebp from the webp Debian package, and gimp's support of exporting Webp.

0.01N

0.02N

0.05N

0.1N

0.2N

0.5N

N

2N

5N

10N

20N

50N

100N

grayscale of no color palatte cycling.  brightness is proportional to 405307726447.

just last 2N steps:

slightly larger 72960x41040, downscaled by 38 to HD (1920x1080), suitable for a desktop background.  random seed was 1.  just the last 2N steps:

link to images with correct MIME type.

because universes were toroidal, all images can be tiled.  note that the program is very inefficient (future work) for producing images of just a small number of steps, because it runs until all pixels have been visited.

C++ source code.

we discovered that printf is much faster than cout.

a downscaled random walk resembles (and in the limit, is) a Wiener process or Brownian motion because a normal distribution applied independently to two or more orthogonal dimensions magically becomes circularly symmetric.

consider rendering 3D random walks.  the Polya recurrence theorem does not apply because we have a finite toroidal universe.