2018 In Review

Another year gone. Over the past year Visions of Chaos has had many new features added, bugs fixed and loads of smaller enhancements. In this blog I managed to cover and experiment with a wide variety of topics over the last 12 months.

Post Summary

Here is a list of posts I added to this blog in 2018;


More Adventures With 3D Gravity
Updated simulation code for 3D gravity.


MergeLife Cellular Automata
Yet another CA explored this year.


Cellular Automata Explained Part 1
Trying to explain CAs from the ground up for newbies. Idea is to expand this into a series.

1D CA


Mandelbrot Foam
A new variety of fractal from Fractal Forums.


Clusters And Particles
Awesome emergence.


Extended Neighborhood 1D Cellular Automata
Inspired by a Reddit post this time.

Extended Neighborhood Cellular Automaton


3D Multiphase Smoothed-Particle Hydrodynamics
3D fluids.


Hybrid Fractals
Quick explanation for hybrid fractals. An area with huge potential for exploration and experimentation.


Multiple Rules Cellular Automata
From a YouTube comment idea.

Multiple Rules Cellular Automaton


Searching For Pleasing Looking Flame Fractals
My attempts at trying to make software smart enough to detect good looking flames.

Flame Fractal Mutator Dialog


Stochastic Cellular Automata
Introducing randomness into CAs.


Spring Pendulum
Extending double and triple pendulums but using springs for their segments.


More Explorations With Multiple Neighborhood Cellular Automata
More experiments with these awesome CA.

Multiple Neighborhoods Cellular Automaton


Rock Paper Scissors Cellular Automata
RPS and variations in CA form.

RPS Image Cellular Automaton


Multiple Neighborhoods Cellular Automata
Fantastic new CA.


Stacked Generations Display For 2D Cellular Automata
These turned out very nice.

History Dependent Cellular Automaton


History Dependant Cellular Automata
A new (old/rediscovered) CA method.


Alternating Neighborhoods Cellular Automata
A new CA from an idea I had one day.

Alternating Neighborhoods Cellular Automaton


Zhang Cellular Automata
A Twitter post inspires another new mode.

Zhang Cellular Automaton


Two Steps Back Cellular Automata
Another new CA (for me) from a Twitter post.

Two Steps Back Cellular Automaton


Indexed Totalistic Cellular Automata
A new CA thanks to a Twitter post.

Indexed Totalistic Cellular Automaton


Line Based 3D Strange Attractors
A group of strange attractors that are plotted from a series of joined points rather than a point cloud.


2D Accretor Cellular Automata
Experiments with a 2D version of the Accretor CAs.

2D Accretor Cellular Automaton


Variations of Ant Automata
Trying a new variation of Langton’s Ant. Nothing too spectacular.

Ant Automaton


Accretor Cellular Automata
Interesting structures from a new CA thanks to a Dutch artist.

Accretor Cellular Automaton


The Stepping Stone Cellular Automaton
An interesting CA from the C64 days of 1980.

Stepping Stone Cellular Automaton


Blog

I have tried to include more useful information as this blog has gone on over the years to hopefully help others, but mainly blogging is most helpful to me. There is an old adage saying that if you cannot explain something clearly then you do not understand it well enough. Writing blog posts has helped me clarify many topics in my mind.

Another big advantage of blogging is that you get contacted by like minded people. Many of the interests I have blogged about have been greatly enhanced by someone emailing me a new idea or fix for an issue I am having.

I really do recommend that everyone blog. Everyone has a “something” they are good at or knowledgeable about. Share that knowledge. You may be surprised how much you benefit from the process.

Looking Forward

I have no intentions of stopping development on Visions of Chaos any time soon. I still have loads of ideas for new features. That also means this blog will continue to grow for the foreseeable future. Onward to 2019 and beyond.

Jason.

More adventures with 3D Gravity simulations and OpenCL

History

3D Gravity simulations are something I have been interested in for many years now. Some worked, some didn’t, some were more realistic than others.

The first 3D Gravity simulation movie I still have on my YouTube channel is this one from way back in May of 2007. Low res with only a bunch of blurry objects.

Since then I have increased the details and object counts. I also started experimenting with OpenCL for big speedups that allowed many more objects to be simulated in a reasonable time frame.

Moving forward to now

For this latest post I went back and rewrote my code and the OpenCL kernel code to correctly compare every object to all other objects in the gravity calculations. The simulation is using Newton’s law of universal gravitation.

Newtonian Gravity

Every point mass attracts every single other point mass by a force acting along the line intersecting both points. The force is proportional to the product of the two masses and inversely proportional to the square of the distance between them.

How this simulation works

I am using software OpenGL on the CPU for all the rendering of the visuals and CPU and OpenCL for the gravity calculations. OpenCL code runs on your graphics card GPU and GPUs are great at running lots of small bits of code fast at the same time. The gravity formula maths is perfect for multi threading. Every objects velocity and acceleration can be calculated at the same time as the other objects.

The basics of using OpenCL is you fill arrays with the information you want the OpenCL code to use (for 3D gravity I am passing position, velocity, acceleration and mass of the objects), pass it to OpenCL, run the code on the GPU, and then read back the results from the GPU when it is done.

This is the current OpenCL code I am using for these latest simulations. Each of the arrays passed (posx, posy, etc) contain all the current objects, ie for a 1 million object simulation the posx array has 1,000,000 floating point values to cover every object’s X position in 3D space.


__kernel void Gravity3DKernel( __global float * posx,
		               __global float * posy
		               __global float * posz, 
		               __global float * velx, 
		               __global float * vely, 
		               __global float * velz, 
		               __global float * accx, 
		               __global float * accy, 
		               __global float * accz, 
		               __global float * mass, 
		               __global float * mingravdist)
{	
	int index=get_global_id(0);
	float dx,dy,dz,distance,force;
	float positionx=posx[index];
	float positiony=posy[index];
	float positionz=posz[index];
	float mingravdistsqr=mingravdist[index]*mingravdist[index];
	float accelerationx=0;
	float accelerationy=0;
	float accelerationz=0;
	float thismass=mass[index];
	for(int a=0; a<get_local_size(0); a++) {
		if (a!=index) {
			dx=posx[a]-positionx;
			dy=posy[a]-positiony;
			dz=posz[a]-positionz;
			distance=sqrt(dx*dx+dy*dy+dz*dz);
			dx=dx/distance;
			dy=dy/distance;
			dz=dz/distance;
			//old method - all objects are assumed to have the same mass
			//force=1/(distance*distance+mingravdistsqr);
			//new method - allows objects to have different masses
			force=(thismass*mass[a])/(distance*distance+mingravdistsqr);
			accelerationx+=dx*force;
			accelerationy+=dy*force;
			accelerationz+=dz*force;
		}
	}
	velx[index]+=accelerationx;
	vely[index]+=accelerationy;
	velz[index]+=accelerationz;
	accx[index]=accelerationx;
	accy[index]=accelerationy;
	accz[index]=accelerationz;
}

The kernel code loops through every object and calculates the forces against every other object. This is the naive unoptimized O(n2) version of the algorithm. Once all the loops are finished the new object velocity and acceleration values are read back from the GPU memory into local memory and then the CPU can access the results. All of the object positions are then updated using the new velocity and acceleration values and then displayed. For displaying the objects I am using the old software only OpenGL billboard quads. A billboard quad is a texture on a quad (rectangle) that always faces the “camera” in OpenGL. If you put a nicely shaded and transparent “blob” as the texture it looks like a simple star and blends in with other stars.

Calculation Times

Using the above code allows me to process millions of objects in a reasonable time frame. For these simulations the slowest part is always the display and CPU calculations. The OpenCL is always the fastest part of the simulations.

Here are a few stats for how quick (slow) these simulations are on a PC with an i7 CPU and GTX 1080 GPU rendering 4K resolution frames;

250,000 objects – 856 ms per frame – 31 ms OpenCL time
500,000 objects – 1606 ms per frame – 57 ms OpenCL time
1,000,000 objects – 3124 ms per frame – 91 ms OpenCL time
5,000,000 objects – 15336 ms per frame – 430 ms OpenCL time
10,000,000 objects – 30638 ms per frame – 864 ms OpenCL time

The reason the per frame time is so much longer than the OpenCL is that I am still using software OpenGL to render all the particles. Software OpenGL falls back to the older v1.1 OpenGL DLLs provided by Microsoft in Windows and has no benefits of hardware acceleration. On my to do list is getting the OpenGL code up to date to use hardware acceleration, then the above times should come way down. Rendering the objects as pixels rather than billboard quads is roughly 1/3 the time, but the billboard quads give a much nicer blended display.

Results

Here is a new sample 4K resolution 3D Gravity movie.

After the last movie I went back and improved the color shading code and added the option for a “black hole”, which in this case is only a single object with a larger mass than the others. The black hole has a mass of around 100 to 500 times the other stars. Any higher and all the stars are flung out of the simulation area too quickly. Here are are some of the latest results.

The spiral galaxy like results are mostly a fluke. I started the simulation with a disk or oblate spheroid (squished sphere) of particles rotating around the origin (Y axis) with a central black hole and let it run.

After a bit more tweaking of the code and coloring algorithms the next movie was ready.

Try It Yourself

The latest 3D Gravity code is now updated and included in Visions of Chaos. For now I am finally happy that at least the basic Newtonian gravity is working and using all objects for the calculations. Future changes will be converting the “old” OpenGL v1.1 display into “modern” OpenGL v3.3+ so the display time can be reduced and get closer to realtime.

Jason.

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.