Simple start. Chaotic end.
Let's go 2016.
Today we're going to make something called a cellular automaton.
“A cellular automaton is a collection of “colored” cells on a grid of specified shape that evolves through a number of discrete time steps according to a set of rules based on the states of neighboring cells.”
That sums it up quite well, but if it's not obvious to you what that means, don't worry, it'll make sense as we go. And if not just enjoy the pictures.
There are many types of cellular automata, but what we'll look at today is the simplest form. The idea involves traversing a row of bits and looking at groups of 3 bits to determine what the next level in the grid looks like, i.e. shaded or not shaded. This approach is then applied iteratively for as long as you want. In the end, we get a lovely structure like so:
Rule 30 - example of chaos!
But before we get ahead of ourselves, we start with the fundamental building block of all data - a bit.
A bit is the simplest form of information, taking on values of 0 or 1. It's like an on/off switch. When we put a bunch of bits together we can form numbers. We call this number system binary. See if you can follow the pattern of binary to integer relationships for the following:
0 - 0
1 - 1
10 - 2
11 - 3
100 - 4
101 - 5
A few things to note:
- 001 is the same as 01 is the same as 1. That is, leading 0's don't change the number.
- As we increase the number, we append bits to the left. So we're reading right to left.
- 2 bits can represent up to 4 numbers. 3 bits can represent up to 8. 4 bits? 2^4 = 16 numbers.
Every integer number has a binary representation. We won't go over how to convert numbers to binary, but it's really not that difficult. For now, just know that you can. For example, the 8 bit representation of the number 30 is 00011110. The number 204 can be written as 11001100.
With that out of the way, let's make some patterns. The idea behind cellular automata is that the next generation of cells is related to the previous generation by some rule. "But Dataman, how does it all work?" Here's the procedure:
- Pick some starting pattern of bits - this is the first level of the grid. This could be anything, but to make the triangular shape above, we put a 1 (shaded square) in the middle surrounded by a bunch of 0s.
- Then pick a rule, which is a number between 0 and 256. Notice how 2^8 = 256.
- Find the 8-bit representation of that rule number.
- Traverse the first level of the grid and look at groups of 3 consecutive bits. Here is an example of what I mean:
We only care about groups of 3 bits because thats how this version of the algorithm works. Recall that you can write 3 bits in 8 different ways.
- Find the integer representation of the 3 bits. For example:
- Use the value from above to index the binary number. We have to count from right to left when we index, because that's how binary is read.
Notice how the result is the reverse of the original 30 in binary: 00011110. Because bits are read right to left. Like Greek.
- Visually, here are the first two iterations of the example above:
- Repeat in this fashion until you fill the entire level of the grid for the next generation. Note that for edge cases, the same logic applies except we "wrap around" the bit.
- Then do it again for many generations.
Now let's create our grid! We represent 1's as shaded squares and 0's and white squares. Starting from some initial generation, we can propagate it down the line as many generations as we want. And voila!
* FYI - the rules, in order are: 18, 30, 90, 105, 110, 150, 182, 210 and 214.
Notice a resemblance?
To summarize:
- We started with the simplest representation possible - a bit
- We followed a deterministic set of rules - there's no uncertainty here, we know exactly what the next generation will be because of the rules
- Even though we started off from humble beginnings, some of these shapes can get very complex. Some form a fractal. This phenomenon is known as the butterfly effect.
- There are many applications of this type of process, including generating random numbers and modeling complex systems.
* source code
