MergeLife Cellular Automata

A new variety of cellular automata from Jeff Heaton. His original paper describing MergeLife is here, but he also made the following video that clearly explains how the rules work.

Jeff’s MergLife page also has more info and examples you can run online.

MergeLife is now included with Visions of Chaos. I haven’t added the genetic mutations yet, but you can repeatedly click the random and mutate buttons and see what new patterns emerge.

Jason.

Cellular Automata Explained – Part 1

My attempt at explaining cellular automata. Aimed at someone who has no real knowledge of how CAs work.

If you look at some online definitions of CAs you will see explanations like this and this. You can try and understand them, but probably be still left confused.

1D Cellular Automata

OK, let’s start at the simplest form of cellular automata, the one dimensional cellular automata.

1D CA

A one dimensional CA consists of a line of row of cells. Each cell can be alive (on) or dead (off).

The first row of the image above is how this cellular automaton begins. It has 1 single centered alive (black) cell surrounded by dead (white) cells.

1D CA Rules

Cellular automata change states and evolve based on simple rules. The rules apply to every cell in the CA at the same time each step.

For the above image, the rules are as follows;

1D CA

This shows the 8 possible rules for this CA. Each new cell state depends on itself and it’s 2 neighbors in the previous state.

The first rule (with the 3 black squares above a single white square) means that if the current cell and its two neighbors are black that cell will become a white cell the next step of the CA.

The second rule means that if a cell and its left neighbor are black but its right neighbor is white, the cell will be white in the next step.

The rest of the 6 rules are the same principal and cover all possible combinations of white and black cells.

You apply these rules to every cell in the CA each step. Here is a nice animation courtesy of Wikipedia showing how the rules are applied to a row of cells and the next step of the CA resulting from the rules.

1D CA

Once the rules have been applied to all the cells, that step is completed. For 1D CA the easiest way to display them is to show each of the steps under the last in a 2D grid. The first 15 steps are shown in the grid above.

1D CA Rule Numbers

Looking again at the rule for this CA

1D CA

you will notice that there are a series of 1’s and 0’s under the rules. 0 for if the rule creates a dead (white) cell and 1 if the rule creates an alive (black) cell. This series of 1’s and 0’s can be converted into a binary string that can then be converted into a number. For 8 digit binary numbers the numbers will range from 0 (for 00000000) to 255 (for 11111111).

These 1D CA’s have 256 possible combinations of rules. Rule 30 (shown above) is the conversion of 00011110 binary into digital 30. Being able to refer to each rule as a single number makes it easier to state which rule you are talking about.

More steps

If you follow the above rule repeatedly for more steps it evolves like this

1D CA

From such simple rules some interesting structures arise within in. This specific rule has been used to generate random numbers (you can keep track of the center pixel going down the image and use it to create random numbers). You can see more info about Rule 30 here.

So what about the other 255 1D CA rules?

You can see the results of all 256 rules here.

An interesting result is rule 22.

1D CA

Rule 22 results in a structure of triangles within triangles. This is a famous fractal pattern called the Sierpinski Triangle and it tends to pop up all over the place in cellular automata and fractals.

The End – for now

Hopefully by now you have a basic understanding of cellular automata. The main points to know are;

1. CAs are based on a grid of cells that are alive or dead.
2. The CA runs/updates/steps by running a set of rules on all the cells at the same time.
3. The same rules are then applied to the new cells and the process repeats itself.

The one dimensional cellular automata are kind of bland and once you seen the possible 256 rules there isn’t much excitement, but understanding 1D first makes the transition into higher dimensions and more complex rules easier to grasp.

If you want to experiment with these 1D CAs yourself, you can download Visions of Chaos. Open the 1D CA mode dialog and suddenly the options should be more clear to you now.

1D CA

There is even an option that takes the CA steps and maps them into music. You can also print a catalog of all the 256 rules with more details.

If any of the above is not clear, please comment and let me know.

Jason.

Clusters and Particle Life

This is another great example of emergence. Complex behavior results from many individual particles following simple rules.

Jeffrey Ventrella explains his Clusters here.

Here is another particle based life model

I learned about Clusters when Code Parade posted the following video explaining his version of Clusters he calls Particle Life.

The source code to Particle Life was generously shared here so I had a go at converting the code and playing with these myself.

Results

Here are some of my results.

Extension Into 3D

Once I had the 2D version working, extending into 3D was the next step. These movie parts use the same settings as in the 2D movie above.

Availability

Both the 2D and 3D Particle Life are now included with Visions of Chaos.

Jason.

Extended Neighborhood 1D Cellular Automata

Extended Neighborhood Cellular Automaton

When I first saw this type of cellular automata described by Gugubo on Reddit I was sure I must have implemented it and included it in Visions of Chaos before, but a quick check showed it wasn’t a CA I had covered. There is enough info in the Reddit thread for me to code it up and put it into Visions of Chaos.

Extended Neighborhood Cellular Automaton

This is a 1D Cellular Automaton that uses 5 cells from the previous generation (2 either side and the central cell) to update the new cell state. The larger neighborhood with 2 cells either side is why I called these “Extended Neighborhood” in Visions of Chaos.

Extended Neighborhood Cellular Automaton

There are 4,294,967,296 (2^32) possible “rules” or types in this CA. Each of the rule numbers can be converted into a 32 digit binary number. For example, rule 260 becomes;
00000000000000000000000100000100

Extended Neighborhood Cellular Automaton

To update a cell, use the following steps;
1. Convert the previous step’s left 2 cells, current cell, and right 2 cells into a binary value.
i.e LLCRR may have states 11010 which can be converted into decimal 26
2. Counting from right to left on the binary representation of the rule above, the 26th digit is a 0, so the new cell state is a 0.

Extended Neighborhood Cellular Automaton

The process is repeated for all cells and then repeated for all rows as long as the CA runs.

Extended Neighborhood Cellular Automaton

I also added the option for more than 2 states (alive or dead) per cell. This way, when a cell dies it does not turn instantly into a dead cell, but has a delayed dying period. If there are 4 states per cell then a living cell (state 1) that dies will first go to state 2, then state 3, then finally die (state 0). Only newly born state 1 cells are used in the rule. All other non state 1 cells are considered state 0 when updating the cell based on the binary string rule.

Extended Neighborhood Cellular Automaton

Jason.

3D Multiphase Smoothed-Particle Hydrodynamics

I have wanted to implement a 3D version of a fluid simulation in Visions of Chaos for years (3D was a planned feature since I first got 2D SPH working back in 2013). It took a lot longer than expected.

For the 3D code I extended the 2D SPH code I had into the third dimension. In the end it wasn’t too difficult (everything seems simple once you work out how to do it). After a week or so of hacking away I had multiphase fluids flowing in 3D space.

The code is based on Tom Madam’s SPH Code in this blog post. For 3D you just need to add in a Z dimension for particle positions etc.

3D is slower than 2D with the extra dimension and even with a decent multi-core CPU the simulation starts to crawl as the particle count increases. Using the awesome Mitsuba to render some nicely lit spheres got me the following movie.

Jason.

Hybrid Fractals

Hybrid fractals occur when you alternate between fractal formulas during the inside iteration loop of generating a fractal. The idea came from posts on the old Fractal Forums site.

For example, rather than the usual Mandelbrot Fractal iteration, you can modify the inside loop to alternate between the Mandelbrot, then the Burning Ship, then the Mandelbrot, and the Mandelbrot again. You then repeat the sequence for as many iterations as that pixel needs.

This gives a result like the following

The code to create this (and other hybrid formulas) is included with Visions of Chaos, but you can also see the OpenGL shader code for it here.

I have also used the same hybrid technique for 3D Mandelbulb Fractals as shown here.

Jason.