vilva.es 🧠

Sketch #4: Playing with graphs and cellular automata

| 4 min read

TL;DR: I implemented a variation on Conways Game of Life using a graph as the main data structure to represent the grid. Animated it using requestAnimationFrame()

🎨 Try it yourself here!
🐙 Code can be found here

I've always been fascinated by Cellular Automata, the idea of generating complex systems from a series of principles or rules seems like magic! Recently I've been acquainted with the use of Graphs and I thought that it would be pretty cool experiment to combine both.

My goal was mainly to create a little playground where I could experiment with CA, hopefully making it easier by using graphs. So I replicated Conway's Game of Life with some little variations to test the easiness of using a different rule set.

So let's see what I learnt:

What is a Graph?

A graph is a data structure that represents entities (Nodes) and the relationship between them (Edges).

Graph theory is a whole field of maths whose surface I have barely scratched, but the more I learn about it the more fascinating it seems.

They are very useful to model tons of systems: Hydraulic networks, like we do in my job at Qatium; neural networks or like in this case, a virtual ecosystem composed of cells living in community.

What are cellular automata?

Cellular Automata are systems composed of entities (cellular automaton a.k.a cells) that have an specific state. Each cell has a series of rules engraved into their little ADN that dictate how their state mutates according to their environment. Their environment is composed of a cells neighborhood this means the cells close to them.

This is a great over simplification, this again is another field of maths and shit gets serious pretty fast, so head to Wikipedia for a full explanation.

You can play around with any number of states, the way rules dictate how states transition, different neighborhood configurations etc. the possibilities are endless as you can see here:

The amazing thing of this kinds of systems is the huge complexity you can achieve when individuals work "together" under simple rules.

Why combine them?

To learn! Both topics interest me very much as they seem very powerful basic concepts that you can use in many places. I'm specially interested in their application to visual stuff.

A graph seemed like the perfect data structure to represent a grid of entities that you have to iterate over to check relationships among them.It proved to be very easy to work, modify and experiment with to test different configurations, although I fear I might have sacrificed performance on the way.

The structure

I used the same environment as in my last sketch

This are some key pieces to note (⚠️ I will be using pseudocode! you can see the full code here.):

  • Setup: A Grid class is abstracted over the main Graph structure to be able to setup the desired configuration of NxN cells easily.
const graph = new Grid(GRID_SIZE, svg).graph
  • The size of the grid can be defined just by changing the GRID_SIZE config variable.
  • The grid positions each cell on it's given place of the canvas at regular distances.
  • The grid also connects each cell to it's neighborhood ( in this case 8 adjacent cells, horizontal, vertical and diagonals).

Main loop: requestAnimationFrame executes the main animation loop each time it is ready to repaint the screen. This makes the animation very smooth and performant and gets out of the way those pesky iterations and loops that might make the animation clunky.

function mainLoop() {
    // 1. iterate all nodes
    // 2. evolve each node
    requestAnimationFrame(mainLoop)
}
  • I added some wobbliness to the animation to give it a more organic look. This shows little variations on the cell updating can reflect in huge changes in the result.

The recursive loop runs at the desired FPS thanks to this neat little StackOverflow trick

Evolution & update: Inside the main loop I had to iterate over each node to compute their new state and AFTER THAT iterate all of them again to update them to the new state.

I had to do this in two consecutive steps, otherwise I was updating each node "on the fly" modifying it's state before the whole board changed, which led to pretty weird and unexpected results.

I suspect this could be optimized, but performance was acceptable and didn't want to dedicate more time to that.

The cell: The cell pretty much contains this:

class Cell {
    // rendering stuff
    // rules
    // state
    // next state
    evolve(neighbourhood){
        // apply rules
    }
}

The rules: The rules dictate what the next state will be according to it's neighborhood. They are injected, so it makes for a very flexible and extensible system. Inject a different ruleset and get an entirely different system!

export class CustomRules {
    apply(cell, neighbourhood) {
        const aliveCells = neighbourhood.aliveCount()

        if (cell.isDead() && aliveCells == 3) return STATES.ALIVE
        if (cell.isAlive() && aliveCells == 2) return STATES.ALIVE
        if (cell.isAlive() && aliveCells == 3) return STATES.ALIVE

        if(aliveCells) return STATES.WARM; // My custom state and rule. This creates a "border" around live cells

        return STATES.DEAD
    }
}

I had my doubts where providing the full cell, just the state or the computed neighborhood state I wanted to check. I opted for this approach since it was pretty easy to play around with, but I don't discard simplifying it in the future.

Animating stuff without P5.js

If you have seen any of my sketches you might now that I love to use P5.js to paint stuff on the screen. But recently I came across this post by George Francis and wanted to try that approach to animating.

Using requestAnimationFrame() had me change my mindset from: "Repainting the whole screen on each step" which I do with P5.js to "Mutate the entities on the screen to their new state". The change of paradigm is very interesting although not sure what do I prefer and when to use each one.

At the end it produced a similar result to a typical P5.js you might encounter and swapped the use of this library for SVG.js so I guess it is a matter of tastes.

Learned

  • How to implement a graph
  • Try to achieve a very extensible design to play with different rulesets and graph configurations. Very happy with the result!
  • Animate stuff without using P5.js

Things to push further

Overall I feel a lot of potential to do cool stuff by combining CA and graphs, but I have yet to learn a lot on both fronts.

  • I would love to scale this to hundreds / thousands of cells, but performance suffers after 1000s cells. Not sure if having the graph in the mixture is killing the performance.
  • Breaking the grid. Can I make a more "organic" system with cells moving around in free space? cooler representations than a circle? the possibilities on viz seem endless!

Resources I found useful

Vilva.