Below is an image of a color wheel on an HTML5 canvas:
This is code that produces that image:
Only 31 lines of JavaScript code, and yet the wheel is comprised of 130 unique colors. The same 130 unique colors each time too. Notice there's no loading data from external calls made to fetch data from other scripts or pages, no Math.random(), and no compressed data used. So how was this accomplished?
The answer to this puzzle is Rule 30, a cellular automaton introduced by Stephen Wolfram. As we'll see in a moment, the bits in the center column of Rule 30 are chaotic and complex and follow no easily discernible pattern. In this case, I collect those bits and concatenate them into integers that I use as RGB values in the wheel.
The rule set for Rule 30 is: Bitwise concatenate each group of 3 cells in a row. If the bitwise concatenation of the group is 1, 2, 3, or 4, then the resulting cell underneath will be 1 (represented by dark shaded cells). Otherwise, 0, 5, 6, or 7 will be 0 (represented by light color cells).
Even simpler: for every 3 bit group, the resulting bottom cell will be the value of the left cell, XOR’d by the the result of the center cell OR’d by the right cell (Bottom Cell = Left Cell XOR (Center Cell OR Right Cell).
The GIF below illustrates how the first 4 rows of the Rule 30 automata are built when the initial input seed is 1:
Similar to other cellular automata, the rows are built repeatedly one after the other. The interesting thing about Rule 30 is that, unlike other automata, the rule set here produces a center column that exhibits complex and seemingly random behavior for many seed inputs (the input of 1 is an example of a seed that produces a complex behavior).
There are pretty much 2 ways you can exploit the center column to implement a pseudo random number generator.
1.) At runtime populate Rule 30 data for n rows (i.e: 100). Then take some other runtime value that isn’t exactly random, but changes constantly and reliably — say the system current timestamp. Then mod this by the number of rows, and then start collecting the bits starting at that row in the center column for as many bits as you like (wrapping around if needed).
For instance, given a current timestamp of 1626103527, and 100 rows of generated Rule 30 data, and we want to build a 32 bit integer. We’d start at row 27 (1629103527 mod 100 = 27). Select bits from row 27 to 58 which yields the 32 bit number.
2.) Take the timestamp and convert it to a string of bits (1626103527 in base 2 = 1100001000110100010010110100111) and then use that as the start seed. Only 32 rows would have to be generated to get a random number. Beware that a downside to this is there’s no guarantee the current seed will produce a random output. For instance, no combination of XOR and ORs will produce 1s given all nonzero inputs, so a seed of 0 will produce a ‘0’ in every row of the center.
How you set up the data structures/arrays to accomplish either of the 2 methods is up to you.
In short: the first method requires generating more rows up front, but then we don’t need to generate any further rows after that. In the second scenario we plug in varying seed inputs each time and only need to generate the # of rows for the # of bits that we want our number to consist of, but it’s harder to guarantee that our dataset will be complex.
One more example with a visual:
We want to generate a random 8 bit value using the first method. We build 8 rows of the automata using an initial seed of 1.
Then we bitwise concatenate those 8 bits together, which makes 11011100 in binary, or 220 in decimal.
Questions, comments, feedback, or have your own code snippets that uses Rule 30 or other cellular automata in unique or fun ways? Please share below in the comments!
