in c#, shader, tutorial, Unity3D

How to Simulate Cellular Automata with Shaders

Share Button

This post will show how to simulate cellular automata using shaders. The popular cellular automaton developed by John Conway, Game of Life, will be used as an example for this tutorial. To learn how to set up your project, check out the first two parts of this tutorial: How to Use Shaders For Simulations and How to Simulate Smoke with Shaders.

life

Introduction

If you have seen the tutorial on How to Simulate Smoke with Shaders, you are probably familiar with the limitations that using shaders introduce in the context of simulations. The first of most obvious is the fact that you cannot alter any other pixel but the one you’re currently iterating onto. Working with shaders is a little bit like having a for loop that allows you to only edit the current item. This forces to write all the equations of our simulation in an explicit form, which might not always be feasible or effective.

texture5

If we want to use shaders for simulation, it is imperative to find a problem that lend itself perfectly to these limitations. Luckily enough, there is a very interesting class of problems that fit this definition. The term cellular automaton refers to a specific class of simulations which are loosely inspired by biological processes. Cellular automata are grid-based techniques which can be described very well with textures. The concept behind them is that the state of each pixel (or cell) only depends on the state of the neighbour pixels. Something similar happens to cell and bacteria, which change their behaviours according to their surrounding, which they cannot usually alter.

Part 1. Conway’s Game of Life

The most famous cellular automaton is Game of Life, developed by John Conway in 1970. It is based on a grid, with each cell either “dead” or “alive”. Time flows at discrete intervals, according to these simple rules:

  • Under population. Any live cell with fewer than two live neighbours dies.
  • Over population. Any live cell with more than three live neighbours dies.
  • Reproduction. Any dead cell with exactly three live neighbours becomes a live cell.
  • Sustainability. Any live cell with two or three live neighbours lives on to the next generation.

These four simple rules were designed to simulate a living colony, introducing intuitive concept of over and under population. Game of Life fails to reproduce the behaviours of a living colony; however, it has incredibly complex properties. First of all, it has been proved to be Turing-complete. This means that they can run any program or algorithm of your choice, if properly encoded in its grid. Game of life is so powerful that yes, you can simulate Game of Life within Game of Life.

Part 2. Implementation

If we want to replicate Game of Life in a shader, we first need a way to create a grid-like representation on a texture. This has been discussed already in the second part of this series, How to Simulate Smoke with Shaders. That technique is applied within a fragment shader to sample the state of the neighbour cells, encoded in the red channel.

The second part is the actual implementations of the four rules:

White and black are used to indicate live and dead cells, respectively.

The Game of Life is often implemented on a toroidal grid. What this means is that the both the left-right and the top-down sides are connected. If you want this to be the case, make sure the render texture you are using is imported with Wrap Mode set to Repeat. Conceptually, the geometry of the world can be represented as a single, continuous 3D object like in the following video:

To avoid any issue, is also important that Filter Mode is set to Point.

Part 3. Optimisation

The technique described in the previous paragraph has two main disadvantages. The first one is that changing the rule requires to actually change the code of the shader. The second is that if statements are notoriously slow when used within a shader. In this particular case, it is possible to use an alternative way to express the rule. Since each cell can have any number of living neighbours ranging from zero to eight, we can use an array of nine items to indicate the next state:

Each item has two components. The first one indicates if the current cell survives to the next stage or not. The second whether a new cell should be created. The rules can now be expressed as:

It is important to notice that in order for the rule array to keep its value, the keyword static is necessary.

Part 4. Improvements

One interesting graphical improvements can be achieved by changing the colours of the cells depending on how long they have been living for. This is possible because we are only using the red channel of our texture for the calculations. The other channels can filled with other colours. In the example shown at the beginning of this tutorial, cells are getting progressively more red the longer they have lived.

Conclusion & Download

Cellular automaton are incredible tools, which have many real applications in game development. Sebastian Lague is using a similar technique to procedurally generate cave-like structure.

Cellular automata can simulate many natural behaviours, including the way water flows. This will be covered in the next part of this series.

You can download the full Unity project of this tutorial here.

Other resources

📧 Stay updated

A new tutorial is released every week.

💖 Support this blog

This websites exists thanks to the contribution of patrons on Patreon. If you think these posts have either helped or inspired you, please consider supporting this blog.

Paypal
Twitter_logo

Write a Comment

Comment

Webmentions

  • How to Use Shaders for Simulations - Alan Zucconi

    […] Part 3. How to Simulate Cellular Automata with Shaders […]

  • How to Simulate Smoke with Shaders - Alan Zucconi

    […] Part 3. How to Simulate Cellular Automata with Shaders […]