I became curious of cellular automata years ago when reading about a personal hero of mine John von Neumann (below). I literally jump at any chance to namedrop him; John was the definition of true face-melting genius and an utter fly boy, try not to feel like a complete imbecile reading his list of achievements, abilities and most importantly his contributions to mathematics and science. His contemporaries joked he was possibly the next stage of human evolution.
Anyway, he was thinking so far off into the future he proposed the concept of the cellular automaton as a theoretical solution to large scale mining operations in outer space where presumably it would be impractical to build and maintain machinery on asteroids and distant moons. Thus self-replicating robots and machines would be necessary for work to continue without human intervention — so the CA concept was born. Which turned out to have applications and far reaching implications everywhere.
What. Is. It.
Fortunately for idiots like moi, really simple.
- Define an elementary cell that has a number of states, in the simplest case binary e.g.; ALIVE or DEAD.
- Evolve that cell by applying a set of rules
- Create a next generation with the cell’s next state and apply the process again
The most fascinating aspect of this idea is that, even if the cells and the rules are unremarkably simple, they can give birth to incredible complexity.
So the classic example is a grid, like a chess board. Almost like a board game in a way, indeed you can play out the generations of cellular automata with pen and paper tediously enough.
You initialise the grid with a bunch of cells, some dead some alive. You then process the cells one by one applying the rules, usually according to the cell’s adjacent neighbours, and write each cell’s new state into a second grid. This becomes the second generation. You can now discard the first grid and start again.
The idea is that each iteration or generation builds on the previous, growing, adapting and evolving into something new.
Cellular Automata have applications in computer science such as random number generation, cryptography, image processing (it’s trivial to implement a’blur’ effect with CA) and others. But mostly I like it because of the questions it raises about the modus operandi of life itself.
When evolution was kick-started on planet Earth and the simplest organisms began to form and adapt and evolve, it stands to reason that many — most — of these ended up being evolutionary dead ends. But a few of them had juuust the right combination of properties to thrive and spawn improved versions of themselves and their genealogy. I think the cleanest example of this is shown through Stephen Wolfram’s work on one-dimensional CA in the early 1980s.
Stephen demonstrated the fascinating complexity generated by even the simplest set of properties and rules.
So let’s use a one-dimensional grid, i.e. a line of cells of any length, and a binary cell state of 0 or 1. Initialise the grid to all empty apart from the middle cell;
We then iterate to a next generation by visiting each cell in turn, examining its immediate neighbours on the left and right. And producing a new state on the next line according to a simple rule.
If below we consider a cell B which has a binary state, and its two neighbours also binary, then, for each cell we process, we always have a 3-bit number between 0 and 7 in decimal. Now, if we interpret that resulting number between 0 and 7 as a binary digit position in another number (The Rule) we can generate a new state for cell B on the next line/generation. A bit like a hash.
Above we can see the evolution of cell B from one generation to the next. It just so happens the the rule we’ve chosen to apply instructs cell B to switch from a dead (0) state to an alive (1) state according to the rule and its neighbours.
You’ll note the rule itself is a simple 8-bit number, and interpreting that (0 1 0 1 1 0 1 0) as a decimal is 90. So we call this “Rule 90”. In Stephen Wolfram’s one-dimensional take on cellular automata there are, naturally, 256 rules to choose from.
You can see Rule 90 in action in the first of my cellular automata implementations here:
Try a few other rules out. All 256 if you’ve really got too much time on your hands. You’ll note that only a few of them produce pleasing results, this is what I was getting at earlier about evolutionary dead-ends. C’est interesting non?
Game Of Life
Another dude John Conway around the same time as Stephen Wolfram offered us a two-dimensional take on von Neumann’s cellular automata. Which works in much the same way but uses a 2D grid and examines the eight neighbours surrounding a given cell. Again, the three rules are super simple;
This just looks at our
subject cell and compares its current state with the number of
ALIVE neighbours surrounding it and generates a
newState. Iterating each generation gives us results like these:
You can see why it’s called Game of Life, they move like weird little binary bacteria or something. Here’s my implementation demo:
Pretty engaging to watch, innit.
In 3D…. sort of?
I had a plan to extend Game of Life to three dimensions using voxels a bit like Minecraft. But after experimenting with Three JS it turned out to be a lot more difficult than I expected.
The first problem is the rules, the proportion of neighbours to check don’t exactly translate directly to 3D as perfect integers so it needed to be tweaked and I never managed to get it working exactly like it did in 2D.
The second problem was exponential data-set size. For a visually striking demo in 2D I used a 100x100 grid of cells. In 3d this would be 100x100x100 = 1,000,000 cells… a helluva lot of memory and data to iterate through.
The third problem was 3D rendering, specifically occlusion culling. I can’t possibly expect to evolve and render one million cubes at 60fps in a browser without some serious trickery; I’d need to determine which cells were visible for a given 3D camera position and then draw those efficiently.
After some research I found Minecraft does something pretty cool, it merges similar neighbouring cubes into a single solid geometry (a bit like a flood filling algorithm — and, interestingly, a bit like cellular automata itself) and sends that to be rendered as one big lump. This works well for ordered structures but for mine which was almost completely random and noncontiguous… it wouldn’t perform so well.
Secondly how do I determine which cubes to draw in the first place? I considered solutions like intersecting viewpoint rays with each cube etc etc….but, by now, I was going way off base and losing sight of the original objective.
This was pretty bloody annoying, I really wanted to round off this research with something super cool in 3D. That’s when I came across Craig Reynold’s “Boids” algorithm. It’s not “cellular automata” in the strictest sense but close enough for me.
It was developed in the 1980s to simulate a natural flock of birds in flight or a school of fish in the sea and it works by following three very simple rules;
- Cohesion: birds gravitate towards groups of other birds nearby
- Separation: birds make sure to maintain a small distance between themselves and others
- Alignment: birds match the flight direction of neighbouring birds
So it’s a simple organism with three simple rules, pretty bloody close to CA in my book.
The implementation was fairly different to my existing CA process. I wanted to create free movement and not restrict the birds to discrete cell positions. So I did away with cells entirely and gave each bird an XYZ coordinate in 3D space.
The algorithm proceeds thusly;
- Iterate through each bird
- Find its local neighbours in a given radius
- Apply the three rules Cohesion, Separation, Alignment using vector maths and according to the neighbours
- Sum the vectors to produce an adjustment vector (
accelerate) for the bird's current 'velocity'
I included just one of the rules
separation in the above listing for brevity.
It all works great! The only issue is that I still have a data-set problem. Even with only, say, 500 birds in the worst case of O(N²) time that’s going to slow things down horribly.
So given my experience of spatial indexes I considered the Quadtree, R-tree, Octree etc to locate the nearest neighbours for each bird. But because each entity in the world was 100% fully dynamic (i.e. everything is moving all the time) these data structures would potentially need rebuilding every frame. Which would make for a garbage collection nightmare, complexity, and hideous performance.
Again, after more research it transpires that the best solution is also the simplest; just use a uniform grid:
To illustrate I’ve coloured each bird according to the grid cell they’re currently in. Red are in cell A0, Green are in cell B1 etc. All we need to do for each cell is keep a list of the birds that it contains.
When we need to find a bird’s neighbours, we see which cell it is in and then just iterate through the list of birds contained within that cell.
In practice, it’s a little more involved because we need to consider edge cases and query surrounding cells too. Thus, there’s a little bit of tweaking to discover the optimal number of cells to split the world into. Pretty easy though.
Every time a bird moves, I call the above method to see if we need to update the cell it resides in. Which involves
pushing to an array, slow-ish, but in most cases the bird hasn't left its cell so we can just
return and everything's cool.
Performance, suitability and the final demo
What happens if every bird is in the same cell at once?
Yeah, it’s slow. But that probably won’t happen because the nature of our algorithm, especially if we tune it right, will generally have an even distribution of birds in our world. So while it might feel Computer Science Cool to use some exotic, adaptive balanced PK-tree to manage our scene, in practice the novice approach is a better fit for our particular use-case.
Picking the right tool for the job, I suppose, means understanding the nature of the software you’re building, keeping your objective in focus and not being afraid to compromise.
So, here’s the demo of 3d “Boids”:
Polish-wise, I stole the idea of flapping wings from another demo I saw.
Well that covered a fair bit, code for everything is in my github repo here. All in all, took a few weeks on and off to put all of the code together and I learned quite a lot, really enjoyable diversion, I’d like to touch on some of this stuff again in the future.
- Computing a theory of everything https://www.youtube.com/watch?v=60P7717-XOQ ↩
- Nature of Code: Autonomous Agents http://natureofcode.com/book/chapter-6-autonomous-agents/ ↩
Originally published at blog.alanmacleod.eu on May 28, 2017.