Hexagonal Cellular Automata

Cellular automata using hexagons have been a requested feature in Visions of Chaos for some time now.

If you are ever in need of programming hexagonal based code, I highly recommend this excellent page that seems to cover every possible question you would ever have about hexagons.

2D Hexagonal CAs

Hexagonal CAs work very similar to square grid CAs. The only difference is that each cell has 6 possible neighbors rather than 8.

Here is a selection of a few 2D Hexagonal cellular automata. Rules shown before each part are in the survival/birth/states format.

2D Hexagonal CA was my top performing twitter post so far. It even got a like from Dan Shiffman which is a real honor as Dan has been an inspiration to me for years now.

3D Hexagonal CAs

This is the one that got most requests. Many people seemed to think that moving from cube grids to hexagonal grids would give better more interesting results, so it was finally time to experiment with 3D hexagonal grids.

3D Hexagonal Cellular Automaton

I adopted the usual Von Neumann and Moore neighborhoods. For 3D hexagonal CA Von Neumann means 8 neighbors per cell (the neighbor cells sharing a face with the current cell, 6 in the XZ plane and 1 above and 1 below). For Moore it is 20 total neighbors (for all face sharing and “edge sharing” neighbor cells).

Rendering

As with other cellular automata in Visions of Chaos, by default I render the CA cells using software OpenGL. This is fast, but no real support for shadows or ambient occlusion so the resulting images are more difficult to read like the following.

3D Hexagonal Cellular Automaton

For better rendering results I have been using the Mitsuba Renderer for years now. Mitsuba has no native support for hexagonal prisms though. First I tried creating a ply file for a hexagonal prism and rendering that in Mitsuba. I hit a similar bug as described here with the edges rendering black. In the end I ended up using 3 rotated stretched cubes to create each hexagonal prism. Not the fastest solution but I do get nicely rendered 3D grids of hexagonal prisms as the following image shows.

3D Hexagonal Cellular Automaton

Then I also reached what seems to be an object limit in Mitsuba. For a while I would get occasional complaints from people reporting Visions of Chaos would not render using Mitsuba resulting in black frames. I now have code that checks the Mitsuba log at the end of renders looking for “exception” errors. If a Mitsuba exception is detected I now notify the user that Mitsuba had a problem. The limit seems to be around 4.5 million cubes from my tests.

The following image is rendered using just the ambient occlusion integrator in Mitsuba.

3D Hexagonal Cellular Automaton

3D Results

This first example movie of the 3D variant is a generations type. Generations cellular automata base cell updates on the count of each cell’s neighbors.

The rules are in survival/birth/states format. All use the Moore neighborhood so each cell has 20 total neighbor cells.

Help Me

Seeing as these hexagonal CAs are relatively new features of Visions of Chaos I don’t have a large number of sample rules to show them off. If you download Visons of Chaos and experiment with the 2D and/or 3D Hexagonal CA modes please send me any interesting new rules you discover.

Jason.

NVIDIA OptiX Denoiser now included with Visions of Chaos

When you render Flame Fractals the pixels accumulate over time. As this process happens different areas accumulate at different rates. Areas that have high hit counts render smoothly while other areas that have lower hit counts render more noisy/speckled.

While I was recently revisiting the Fractal Flame mode in Visions of Chaos I experimented with some ideas I had to make a “smart blur” function. This was going to supposedly blur pixels by different amounts depending on their neighbors. So areas with more noise would be blurred more than areas with little difference between pixels. After some experimenting with various convolution kernels etc I gave up. My results were either too blurry, too dark or other issues.

Searching for other methods got me to “denoising”.

Note: all of the example images in this post need to be seen full 4K size to notice the differences.

NVIDIA OptiX

NVIDIA OptiX is a raytracing engine. Part of what it can do is denoising.

Denoising is a big deal in ray tracing areas. When raytracing images (depending on the method used) you need to make many passes of the image before the details are smoothed out.

Here is an example from Visions of Chaos (the “Pathtracing Global Illumination” example shader) after running for a few seconds.

Denoiser

You can see a lot of noise visible as the rendering was stopped way before the pathtracing converged to a smooth image.

Running the image through the OptiX denoiser gives the following result.

Denoiser

A much smoother result.

The alternative is to allow the pathtracer to run for much much longer until it smooths itself out. The next image took around 10 minutes to accumulate the smoothness that OptiX took a second to smooth. If you look closely the details are better in this image compared to the denoised image.

Denoiser

In some cases the noise may be desirable. If like me you prefer the film grain of a good 70’s movie to the smooth digital look of a modern film then a bit of noise may be more aesthetically pleasing to you, but in general less noise is desirable in rendered images.

Accumulation Fractals

For Visions of Chaos my interest in denoising was for modes like Buddhabrots, Flame Fractals, Iterated Function Systems, and Strange Attractor images. All the modes that have images that are built up by the accumulation of points. A side effect of this accumulation is that areas of the image less hit show up noisier than areas hit more frequently.

Denoising to the rescue!

When It Works

Here are some examples of how the denoiser can help. It seems to work best (at least from my initial experiments) with images that have whispy details.

Iterated Function System with noisy areas.

Denoiser

The same image processed with OptiX.

Denoiser

Flame Fractal with noisy areas.

Denoiser

The same image processed with OptiX.

Denoiser

Strange Attractor with noisy areas.

Denoiser

The same image processed with OptiX.

Denoiser

When It Doesn’t Work

Denoising is not a magic bullet to fix any pixelated image. It was specifically trained to denoise noisy images.

Here are a few example images that it did not help. When the denoising “fails” it tends to smear areas of the image rather than enhancing them.

Buddhabrot Fractal. Surprisingly Buddhabrots do not seem to be a good candidate for OptiX denoising. The noisy areas do get denoised, but areas with details tend to get smeared more.

Buddhabrot before.

Denoiser

Buddhabrot after OptiX denoising.

Denoiser

Multi-Scale Turing Pattern before.

Denoiser

Multi-Scale Turing Pattern after.

Denoiser

Magnetic Pendulum before. This is a good example of how denoising needs noise to work. This image has a lot of fine detail, but nothing that could be classified as noise.

Denoiser

Magnetic Pendulum after.

Denoiser

Availability

Denoising is now included with Visions of Chaos. I am including the excellent command line version from Declan Russell. Denoising any image created in Visions of Chaos is now just a click away. If you want to denoise other images outside Visions of Chaos I highly recommend Declan’s implementation.

Jason.

Totalistic Cellular Automata

Totalistic Cellular Automaton

A new (old) CA based on this twitter post. The original reference is from the December 1986 issue of BYTE magazine which can be read online here.

Totalistic Cellular Automaton

A fairly simple 1D cellular automaton but one I had not implemented or explored before.

Totalistic Cellular Automaton

The original BYTE article uses 4 states per cell (dead and 3 live states).

Cells are updated by totaling the state values for each cell and its left and right neighbors of the previous step, and then using that value as an index into a rule string to get the new cell state.

For example, as Jeremy explains in his tweet, if the rule string is 0010332321, then updates each step would be as follows.

00002120000
00010301000
00003030000
00000200000

Rule 0010332321 gives the following result when starting from a random row of cells.

Four State Cellular Automaton

Totalistic CAs can use any number of states. They can also extend to a range of neighbors beyond just the immediate left and right neighbor cells. The current center cell can be ignored and not included in the totaling.

1D and 2D Totalistic Cellular Automata are now included with the latest version of Visions of Chaos.

Totalistic Cellular Automaton

Jason.

Dendritic Crystal Growth

Dendrites are the multi-branched fractal like patterns that can grow in crystals or metals. Snowflakes are also a good example dendritic growth.

Snowflake

After seeing this post on r/Simulations that linked to the paper Numerical Simulation of Dendritic crystal growth using phase field method and investigating the effects of different physical parameter on the growth of the dendrite (great name) which includes some Matlab code I was able to add Dendritic Crystal Growth as a new mode in Visions of Chaos.

Also see the original paper referenced which is Ryo Kobayashi’s “Modeling and numerical simulations of dendritic crystal growth“.

Results

Here are some results from the new mode. I have also added an option to give the growths a 3D embossed look.

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Dendritic Crystal Growth

Here is a sample movie

Bug fix for code

At first my translation of the Matlab code in the paper did not result in anything but boring smooth edged blobs. I don’t own a copy of Matlab to verify the code, but I assumed (as any programmer does when their code doesn’t work) that it must be something I am doing wrong. But after some time checking and double-checking I did find some problems with the code in the paper.

Firstly this line near the end


tnew(i,j) =t(i,j) + lap _t(i,j)*dt + k*(phi(i,j) -phiold);

needs to be changed to


tnew(i,j) =t(i,j) + lap _t(i,j)*dt + k*(phinew(i,j) -phiold);

otherwise the phi-phiold cancels out and k is multiplied by zero.

Secondly the calculations for grad_epsilon_x and grad_epsilon_y


grad_epsilon2_x = (epsilon(ip,j)^2 -epsilon(im,j)^2)/dx;
grad_epsilon2_y = (epsilon(i,jp)^2 -epsilon(i,jm)^2)/dy;

should be moved to the second loop before the term1 calculation.

With those two simple fixes my code was generating the correct dendritic structures and created the images in this post.

Availability

Dendritic Crystal Growth and two Snowflake modes are now included under the new Dendritic Growth mode menu in Visions of Chaos.

Jason.

Pandemic Simulations

COVID-19

Due to COVID-19 I have seen some infection simulations going around the Internet. Most popular (or what I have seen linked to the most) seems to be this simulation from the Washington Post.

I have been wanting to experiment with virus infection simulations for a while now, so now is the time.

Before going further I want to make it clear that this is in no way specific to COVID-19 and I have no professional training in viruses or infections. This is Softology, not Virology.

Simulation Version 1

This version is a blatant ripoff the Washington Post simulation but allows more settings to be tweaked and larger population sizes to be experimented with. People (shown as circles) move around in random directions bouncing off each other.

The simulation starts with all the people healthy (not infected) and a single person set as infected in the middle of the world. These are the settings for the simulation that can be tweaked.

Pandemic Settings

The above default parameters result in the following run. The virus spreads quickly to the entire population. The 50% recovery probability results in roughly half the population dying with the other half recovering from infection.

Now let’s take a look at modifying some parameters.

The next run had increased population density so people are much closer together. The virus now spreads much faster and ends the same as the previous run with a 50/50 dead/recovered ratio.

Now with the density lowered so people are not as packed together. This time the virus does not infect all healthy people. This is a good example of “social distancing” helping.

Lowering the speed at which people move. If infected and healthy people move slower then the virus has less chances to spread. In the end about a third of al people never get infected and another third recover from infection.

Lowering the probability that people will move each step of the simulation to 10%. This could represent the majority of the population staying home and people only going out for essentials. With this change the virus dies out and the impact on the population is minimal.

If the probability of movement is 0 then the initial virus cannot spread and it dies out.

Simulation Version 2

This time I used an even simpler model. People live on a square grid and only move randomly in a north, south, east or west direction.

Here are the default settings this time

Pandemic Settings

Using those parameters gives the following result

Again a higher density population allows the virus to spread much faster

Social distancing can be simulated by lowering the population density to 10%. People are still freely moving around but keeping their distance from each other due to lower density. The virus spreads much more slowly and not all people get infected.

The original settings are run again, but this time there is only a 5% chance people move around each step of the simulation. This models people who are isolating themselves at home. The fewer people who do move around can be thought of as the people who have to go out for food or medicine. This results in the virus barely spreads at all before dying out.

Conclusion

Both of these very simplistic models show clearly that the best way to stop or severely limit a virus spreading is social distancing and self isolation.

If you want to play with these simulations yourself and try tweaking other parameters they are now included in Visions of Chaos.

Another Example

Grant Sanderson aka 3Blue1Brown made the following video about his simulation tests. Much more detailed than my simple tests and as with all his videos highly recommended.

Jason.

Ant Colony Simulations

Introduction

This is a simple example of an agent-based model that tries to emulate behavior of ants as they forage for food.

The basic principals of the simulation are;
1. Ants leave the nest moving randomly.
2. If an ant finds some food it picks it up and takes it back to the nest.
3. Ants carrying food leave a pheromone trail on their way back to the nest.
4. Ants looking for food will follow pheromone trails to have a better chance at finding food.

Once an ant finds food, it turns around 180 degrees and then heads towards the nest (with some random turns thrown in so their paths are not always straight lines). In reality ants seem to be able to use the sun position and landmarks to find their way back to the nest.

Using those very simple principals shows how a colony of ants with no other means of communication can coordinate to locate and retrieve food in the surrounding areas.

Programming the ants

For these simulations each ant has some simple properties that control its behavior like position, direction, maximum angle it can turn, move speed, sense angle and sense direction.

Position is the X,Y coordinates of the ant. Direction is the angle the ant is facing. Maximum angle determines how far an ant can turn left or right each step of the simulation. Move speed is how far the ant moves forward each simulation step.

For the process of how an ant looks for pheromones I based this on a similar way to how the Physarum Simulation particles work. An ant looks a certain distance and angle to the left, front and right ahead of itself and senses how many pheromones are in these three locations. The ant then turns towards the spot with the highest pheromone count. If an ant is moving randomly and gets near a pheromone trail it will turn towards the trail and hopefully follow the trail to find food.

The pheromones can be slightly blurred out each frame to simulate diffusion.

If an ant hits the edge of the world it turns 90 degrees and keeps moving.

I had an early attempt at ants simulation for many years that kept the ants on a fixed integer coordinate 2D grid. The change here to using floating point values for ant positions and angles really helped give more natural looking movement as shown in the animated gifs in this post.

Obstacles

Obstacles turned out to be a problem. If there is an obstacle between the food and nest and ant who finds the food will then head towards the nest and get stuck on the obstacle wall. They do eventually bump along the edge of the obstacle and make it around, but they should be smarter and follow a known “good trail”.

If an ant hit an obstacle I got it to only move randomly for the next 100 simulation steps and not leave any pheromones (as we don’t want a trail heading to an obstacle). Still doesn’t really help. Ants still get stuck at the obstacle. More thought and testing required.

Then I got a twitter reply from @psychobiotic suggesting having a foraging pheromone trail left by ants as they look for food. When an ant finds food it can then use the foraging trail to get back to the nest.

That works much better than my previous method above.

Results

This new version of the ant simulation is now available in Visions of Chaos.

Jason.

A New Kind of Science

A New Kind of Science

A New Kind of Science cover

A New Kind of Science (referred to as ANKOS from now on) is an immense tome written by Stephen Wolfram in virtual isolation over a ten year period.

Like most cellular automata enthusiasts I was interested in seeing the book once I first heard about it and I grabbed a copy when it was first available in the local book shop. When I first purchased ANKOS I was hoping to get some ideas for new cellular automata from the book to add to Visions of Chaos. What really happened is that after skimming through it a few times it went on the bookshelf and was never referred to again.

For many more detailed reviews of the book you can refer to the Amazon reviews and this collection. I am not qualified to judge if there is a “new kind of science” contained within the many pages, but the general consensus seems to be that the book does not contain a new kind of science and that someone should never ever write a book of that size without an editor and without peer review. If anything, ANKOS is a good lesson on how not to write about something you have done or discovered.

The other day I took the book off the shelf again and cracked it open, still in pristine condition other than the layer of dust that had gathered over the past 18 years. This time I am looking specifically for ideas that I can program and add to Visions of Chaos. ANKOS is a high quality book in terms of physical production value but some of the diagrams and font sizes (especially in the notes section) can be a strain for my not so perfect eyes. Luckily Wolfram provides the entire book online so I can read (and zoom) that version much more easily. Having the book online is appreciated as I can easily link to specific sections of the book directly. Physical ANKOS went back on the shelf again. Maybe forever this time.

Over the past three days I implemented the following nine cellular automata types from ANKOS that I had not previously included with Visions of Chaos.

1D Cellular Automata

Page 60 – Three Color Totalistic Automata.

ANKOS CA

ANKOS CA

ANKOS CA

ANKOS CA

ANKOS CA

Page 71 – Mobile Automata.

ANKOS CA

ANKOS CA

ANKOS CA

Page 73 – Extended Mobile Automata.

ANKOS CA

ANKOS CA

ANKOS CA

Page 76 – Generalized Mobile Automata.

ANKOS CA

ANKOS CA

ANKOS CA

Page 125.

ANKOS CA

ANKOS CA

Page 156 – Continuous Automata.

ANKOS CA

ANKOS CA

ANKOS CA

Page 460 – Two State Block Cellular Automata.

ANKOS CA

ANKOS CA

ANKOS CA

Page 461 – Three State Block Cellular Automata.

ANKOS CA

ANKOS CA

ANKOS CA

2D Cellular Automata

Page 173.

ANKOS CA

ANKOS CA

ANKOS CA

846 pages later I am done.

See my ANKOS album on Flickr for more images from ANKOS.

Final Summary

I had a bunch of other complaints about the book here that I deleted. Everything I wanted to say has been covered in other reviews. Besides that I do try and keep to the “if you don’t have anything nice to say, then don’t say anything at all” adage in this blog.

Was I glad I went back and opened ANKOS again? Yes, overall I did find some interesting new cellular automata to play with. I have experimented with cellular automata of many types over the years and while I do find them very interesting I doubt that they will be the answer to everything, but hey, what do I know?

I do know that if anyone shows any interest in my copy of the physical book it will be thrust into their eager hands with my insistence that they take it as a gift and not a loan.

Jason.

Huegene

I first heard about Huegene after watching the following video from Dave Ackley.

Similarities to Wa-Tor

Huegene is similar to Wa-Tor with the following differences;

1. Plants and herbivores rather than fish and sharks.

2. Plants cannot move like fish can. They spread through self propagation.

3. Herbivores have a probability chance of eating plants based on how close in color the herbivores and plants are.

Color Genes

Both the plants and herbivores have genes that determine their color.

When a new plant or herbivore is created it has a slightly mutated color from the parent. This results in plants growing in clumps of similar colors.

Plant Consumption Probability

This is the main difference between Huegene and Wa-Tor. In Wa-Tor the sharks happily gobble up any fish they land on. In Huegene the herbivores have a probability of eating a plant based on how close in color they are to the plant. So a blue herbivore will have a greater chance of eating a light blue plant than a yellow plant.

Herbivores eat the plants around them with the most similar color, which leads to the less similar plants in the area being able to thrive which then have more resistance to the herbivores in the area. The herbivores also mutate and can adapt to eating the new plant colors. This feedback cycle continues as the plants and herbivores adapt to the changes in each other.

Gene Color Methods

For the gene colors I use the following 3 options;

1. Hue. Hue is a floating point value between 0 and 1. For display the HSL(hue,1.0,0.5) value is converted to RGB.

2. RGB. Each plant or herbivore has 3 color genes for red, green and blue.

3. Hue and Saturation. Hue is between 0 and 1. Saturation is between 0.5 and 1. For display the HSL(hue,saturation,1) value is converted to RGB.

The following three sections explain how these different gene methods are used to determine a probability of a herbivore eating a plant next to it.

Hue Genes

Hue is a floating point value between 0 and 1. It is converted to RGB values for display.

The following code is used to determine if a herbivore eats a plant near it.


//difference between hue values
difference=max(herbivorehue,planthue)-min(herbivorehue,planthue);
//wraparound difference - make sure difference is between 0 and 0.5
if difference>0.5 then difference:=1-difference;
//scale difference to between 0 and 1
difference=difference*2;
//test probability
if random*probabilityfactor<(1.0-difference) then EatPlant

The difference takes into account the fact that the Hue values wrap around from 1 back to 0 on the hue color wheel. For example, if you have a plant hue at 0.1 and a herbivore hue at 0.9 you want their difference to be calculated as 0.2 and not 0.8.

I also added a “probability factor” in. If this is greater than 1 it lessens the chance of the herbivore eating the plant. If you get a simulation that the herbivores are too plentiful increasing this factor will help keep them under control.

RGB Genes

Each plant and herbivore now has 3 red green and blue values that are used for display and the probability of the plants being eaten by herbivores.


//difference between RGB values
difference=sqrt(sqr(herbivorer-plantr)+sqr(herbivoreg-plantg)+sqr(herbivoreb-plantb))/255;
//test probability
if random*probabilityfactor<(1.0-difference) then EatPlant

Hue and Saturation

Now takes into account hue and saturation values. Hue is between 0 and 1. Saturation is between 0.5 and 1.


//difference between hue values
difference=max(herbivorehue,planthue)-min(herbivorehue,planthue);
//wraparound difference - make sure difference is between 0 and 0.5
if difference>0.5 then difference:=1-difference;
//saturation contributes 50% of difference value
difference=difference+(max(herbivoresat,aPlant.sat)-min(herbivoresat,aPlant.sat));
//test probability
if random*probabilityfactor<(1.0-difference) then EatPlant

Other Examples

Plants actively look for empty neighbor locations to spread into. Herbivores move at random rather than actively looking for plant neighbors.

Plants actively looking for empty neighbors. Herbivores hunting for available plant neighbors.

Plants spread randomly. Herbivores hunt for available plant neighbors.

Sample Movie

Extension Into Three Dimensions

This next movie extends 2D into 3D. Same logic and parameters as the 2D movie, just adding the third Z dimension into the calculations.

The next movie averages the colors of the cells for display. The simulation genes themselves are not averaged/blurred, just the display colors. This cuts down the color noise and allows the more general waves of plant types to be seen. Or maybe it doesn’t? Anyway, it is another option to experiment with.

Availability

Huegene is now included in Visions of Chaos.

Jason.

Wa-Tor

Wa-Tor is a simulation of fish vs sharks in a toroidal wraparound world. It was devised by AK Dewdney in 1984 and published in Scientific American under the name “Sharks and fish wage an ecological war on the toroidal planet Wa-Tor

The original Wa-Tor simulations took place on a VAX system with a display 80×23 characters in size. Each step of the simulation took a while to run (no exact time specs given). It is interesting to read in Dewdney’s article that to test a theory he had about the system he let a setup run overnight to see what happened in the morning. Now with a decent computer you can run these over thousands of cells in almost real time.

Setup

The world consists of a 2D array that wraps around at the edges. When you have the wrapped edges the world becomes a donut (or toroid) shape.

A number of sharks and fish are randomly distributed into the world.

Fish look for empty cells directly next to themselves (using a von Neumann neighborhood of neighbor cells directly north, south, east and west) and randomly move into one of them. If they are older than a specified breed age they will leave a child fish behind in their current location.

Sharks look for fish next to themselves and randomly eat one of them if found. When they move they will leave a child shark in their old spot if they are older than a specified breed age. If no fish are found they will randomly move into an available empty space. If they do not eat their starvation level increases. If they starve for too many steps of the simulation they die and are removed from the world.

Here is an example movie Wa-Tor. Green pixels are fish, red pixels are feeding sharks, gray pixels are sharks.

If you balance the settings right this sort of simulation will continue to cycle indefinitely.

Wa-Tor Parameters

Wa-Tor is controlled by the following parameters the user can play with;

Fish breed age – how many simulation steps does a fish need to survive for before it can give birth to baby fish. For these simulations I used 3 cycles.

Shark breed age – how many simulation steps does a shark need to survive for before it can give birth to baby fish. 15 cycles.

Shark starve time – how many simulation steps it takes for a shark to starve to death if it does not eat. 10 cycles.

Random Movement

An alternative method is to allow fish and sharks to only move randomly.

Fish pick one of the 4 directions at random. If it is empty they move into it and potentially have a child. If it is occupied they do nothing.

Sharks also pick a random direction. If a fish is there the shark eats it. If the spot it empty the shark moves into it. If it is occupied by another shark the shark does nothing.

Here is an animated gif showing fish and sharks both moving randomly.

Color Fish

This was a quick idea I had. Each fish has a color assigned to it. When it has a child fish, the child fish has the same color with slightly different RGB values. This way you can see how a “family” of similar fish spreads.

3D

Wa-Tor can also be extended to 3D. In the following movie the simulation takes place in a 3D cube of cells, but cells outside a centered sphere are hidden to see the inner structures more clearly.

In this next movie only the fish are visible and they are colored to show how fish and their offspring spread.

Availability

Wa-Tor is available in Visions of Chaos.

Jason.

Combinations Cellular Automata

Combinations Cellular Automaton

This is a new idea for a 1D cellular automata that came from Asher (blog YouTube).

Combinations Cellular Automaton

Trying to explain this clearly is harder work than programming it.

Combinations Cellular Automaton

Rule string

Combinations CAs can have between 2 and 10 maximum states per rule. 2 states means the cells can be either on or off. 3 states mean cells have 1 dead state and 2 living states.

The CAs are governed by a rule string.

The rule string needs to be states^2 characters in length. For 2 state rules the rule string will need 4 characters, for 4 states the rule string needs 16 characters, for 10 states the rule string needs 100 characters.

For 2 states the rule string characters are in base 2, so binary values of either 1 or 0. For 3 states the rule string is base 3, so the characters are all between 0 and 2. For 10 states the rule string is base 10, so the characters are all between 0 and 9.

An example 2 state rule is 0110 which creates the following;

An example 3 state rule could be 012120200 that creates the following result;

An example 10 state rule could be

50391696401156117866581414266160495600057647563383
52633979845117861158665940485681011955680007489199

which gives this result;

Number of possible rules

When you have a maximum of 2 states, the rule string has 4 digits of either 0 or 1. The maximum rule string is 1111, which converts to 15 in binary. That gives you 16 possible rules (0000 is also counted) for state 2.

Increasing to 3 states has a 9 digit rule string with base 3 digits. 222222222 is the maximum base 3 number which translates to 19682, so there are 19683 possible 3 state CA rules.

4 states is 16 characters. 3333333333333333 is 4,294,967,295 in decimal, so 4,294,967,296 possible 4 state rules.

10 states is 100 characters. No need for decimal conversion as base 10 is decimal. So 1 with 100 zeros after it possible rules. That may as well be an infinite space to look for rules within.

Combinations Cellular Automaton

How the cells are updated

Each cell in the CA is updated by taking into account 2 cells from the previous step. These 2 cells are converted into a decimal value that is used as an index in a rule string to give the new cell state. I bet that makes loads of sense! Let me try and explain.

An example with a 2 state CA using rule 0110, so cells can only be either state 0 or state 1.

If the first step is a single center cell, then the values would look like;


00000100000
?

Cell at ? looks at the cell above it and the cell next to it. These are 00. 00 converted to decimal is 0. So we look at the 0th entry in the rule string, so the cell value becomes 0.


00000100000
0

Same for the next 3 cells


00000100000
0000

Then we get to the next ? cell


00000100000
0000?

This cell has the cell above it and next to it as 01. 01 converts to decimal 1, so we look at the 1th (second) digit in the rule string. The second digit in the rule is a 1, so the new cell becomes a 1.


00000100000
00001?

The next ? cell now has 10 above it. This converts to a 2 in decimal, so we look at the third rule digit. Again it is a 1.


00000100000
000011

The rest of the row has 00 above them, so they get set to 0.


00000100000
00001100000

If you continue this process, you get the following result;

Brick wall neighborhood

This CA also uses the brick wall neighborhood idea for selecting neighborhoods. See here for an animation of brick wall. Basically you shift the neighbor locations being checked every other line.

For the Combinations Cellular Automata in this post this means the location of the 2 neighbor cells changes every line.

For even lines you use the cell directly above and to the right. For example, in this next diagram the ? cell would use the 3 and 4 locations.


12345
  ?

For odd lines you use the cell to the left and the cell above. This would be the 2 and 3 neighbor cells.

Combinations Cellular Automaton

Interesting Rules

Rule 002200121 behaves similar to Wolfram’s Rule 30. During bulk runs of rules I have seen other results that also look like this one.

Combinations Cellular Automaton

Another result that has been observed to occur are these “counting triangles” rules. These show similar behavior to Wolfram’s “Rule 225“. The splitting of bifurcation like structure on the right hand side is like a binary counter. This is rule 010221200.

Combinations Cellular Automaton

Rule 200122011 also gives a binary counter structure.

Combinations Cellular Automaton

More example images

See my flickr gallery for more example results.

Combinations Cellular Automaton

Availability

Combinations Cellular Automata are now included in Visions of Chaos.

Jason.

Comments Off on Combinations Cellular Automata Posted in Uncategorized