Its been a while since I coded one of those two hours web-experiment.
For today, I decided to code the most famous cellular automaton in a web, but using the GPU to compute every step, so I could reach high speed with big worlds.
For those who doesnt know what a cellular automaton is, wikipedia describes it as:
A cellular automaton consists of a regular grid of cells, each in one of a finite number of states, such as on and off. For each cell, a set of cells called its neighborhood (hte ones around the cell) is defined relative to the specified cell. An initial state (time t=0) is selected by assigning a state for each cell. A new generation is created (advancing t by 1), according to some fixed rule (generally, a mathematical function) that determines the new state of each cell in terms of the current state of the cell and the states of the cells in its neighborhood.
Or in other words, you start with a grid where every cell is in a state (let’s assume there are only two states, alife or dead). And then you use a set of rules that define the state of the cell in the next round. The rules could be as simple as “if you have three cells alife around you, then you stay alife, otherwise the cell dies”. And then you keep computing the simulation to see how the grid changes.
Conway Game of Life
The most famous cellular authomaton is called Conway Game of Life, it has a very simple set of rules, and it has been explored in big depth by lots of scientist and mathematicians.
The only problem with Conway Game of Life it is that unless you start the grid with a discovered state with a known behaviour, the results will be boring. If you fill the grid with random values, the grid will reach an static state pretty fast.
I’ve been searching for interesting patterns but I haven’t found a good database.
Some of them on my app are captured from screenshots I found in google images.
Conway in the GPU
Coding celular authomatas using the GPU is very easy, you only need to create two texture buffers and a shader that reads from one and draws to the other the result of applying the rules to every cell. Once you have computed the full grid, you can write the result on the screen. It is similar to coding a PostProcessing effect. The only important steps are to disable the use of mipmaps and to start the first buffer with some data.
Executing Conway in the GPU allows to execute huge grids really fast. Using WebGL the texture max size is 4096×4096 and in my test I could execute more than 60 steps per second.
But because Conway only has two states, I could easily codify four cells per pixel using the four color values (RGBA), so I could reach without effort a grid of 8192×8192 cells. And I could even try to store more states per color value using the 8 bits per channel, but that would make the shader source a little bit ugly.
I think I will make another try with cellular authomatas but instead of conway I will use another set of rules, like reactive textures, they are more artistic to play with.