Turing Patterns

from Red Blob Games
11 Jan 2022

I last played with this in 2019 and wanted to revisit it now that I’m learning from Phillip Compeau’s online course[1]. Going through this course’s material helped me understand this topic much better than previous references I had read. I took some notes from the chapter on Turing Patterns. They probably won’t make sense unless you’re also following the course. For the next week, I used colors and patterns to make this into art.

 1  Random walks#

Let a particle move randomly each time tick. It will follow a random walk. Here’s an example:

Random walk of one particle

Each time the particle will trace out a different random path:

Random walk varies each time

If the particle moves distance 1 each step, after N steps the particle will be on average distance √N away from the origin. This is the Random Walk Theorem.

Random walk of many particles

See the course page[2] for more, and random-walk.js for my source code.

Related: Levy flight random walks[3] are a different distribution instead of each step being 1. See this tweet from Andrei Kashcha[4].

 2  Reaction-diffusion#

If there are two types of particles, “predator” and “prey”, we can set up some simulation rules:

This isn’t exactly the same as the Lotka-Volterra predator-prey model. I read the section but didn’t write a simulation. Watch the videos on the course page[5].

 3  Gray-Scott#

In fluid simulation there are both particle methods which simulate each amount of fluid in a variable amount of space and grid methods which simulate each amount of space with a variable amount of fluid. The previous section was a particle method but we can compute more efficiently by using a grid method, especially on a GPU where we can use 2d arrays (textures) to store the grid and shaders to calculate the simulation.

Instead of storing each particle and its exact location, we store the number of particles in each approximate location. Earlier versions of SimCity did this, storing traffic, pollution, etc. per location, whereas SimCity 5 and Cities Skylines use the particle approach, storing each individual car with exact location. The particle approach is “cooler” but slower and harder to understand at a high level.

My notes on this section of the course:

diffusion
this is a “smoothing” or “blurring” step that spreads out a value to neighboring cells. This corresponds to the random walk effect where particles are moving randomly to nearby locations. There is a parameter here to control how quickly the smoothing happens. If the parameter is too high we can get oscillation. Not covered in the course, but once you think about it as image blurring, you can move values further than just the immediate neighbors. Here are different diffusion speeds:
Different diffusion speeds
dt
I figured this was a standard “delta time” value, and initially set it to the change in timestamp. But Karl Sims’s page[6] always sets it to 1, the course implementation always sets it to 1, Ken Voskuil’s page[7] always sets it to 1, and Pablo Márquez-Neila’s page[8] always sets it to 1. So I’ll set it to 1 too.
colors
in previous projects I’ve visualized the A, B densities in separate color channels but that’s often hard to understand so in this course they’re visualizing A/(A+B) using a diverging colormap[9]. I think I’ll explore color schemes in my next reaction-diffusion project. In this one my priority is learning the math.
Different diffusion colorings
parameters
Gray-Scott is a “fine-tuned” model meaning its behavior is very sensitive to the value of the parameters. I’ve seen it change drastically between feed=0.062 and kill=0.063. See Robert Munafo’s page about a very interesting set of parameters[10], and his clickable map[11] of different parts of the parameter space. There are also “robust” models that are not very sensitive to the value of parameters.
Slightly different parameters, feed=0.026, kill=0.052 to 0.058
simulation
in Karl Sims’s formulas, he uses feed to increase A, and kill+feed to decrease B. Other pages do this too. But in the course notes, kill alone decreases B. I think it works either way but if you are using parameter values from the literature with the course source code you will need to set your kill value to the literature kill+feed value.

Here’s a version where you can change the feed and kill parameters. I decided to use the Karl Sims version (kill+feed) because I wanted to be able to put in numbers from other blog posts I read, so I needed to be consistent with what most people use.

feed=
kill=

See the course page[12] for more, and reaction-diffusion.js for my source code.

 4  Phase diagram#

One of the things I learned while studying predator-prey is that it’s sometimes useful to look at a phase diagram for 2d differential equations. Just as with predator-prey, there are two variables here, and some parameters. Unlike predator-prey, it’s unclear that there are closed loops. So instead I’m going to draw the vector field[13]. This diagram shows the reaction and ignores the diffusion:


feed=
kill=

It wasn’t what I expected. I was hoping to see loops in this phase space, like I did with predator-prey. Maybe I need to spend more time studying it, or maybe it’s not enough to look at reaction without diffusion.

It’s interesting to see that most every vector seems to point to a “critical region”. The lower left side pushes you up and right, and the upper right side pushes you down and left, so what’s going on with that boundary?

The two boundary lines are “nullclines”. I colored them based on whether they’re pointing up (red: increasing A concentration) or down (black: decreasing A concentration). It’s interesting that one boundary depends on feed but not on kill, but kill does affect whether it’s pointing up or down. The other boundary depends on feed+kill, but had I used Compeau’s versions of the equations it would only depend on feed. This makes me think Compeau’s version is more “pure” than the version Karl Sims used. If you separate the two lines by lowering kill you can see that the five areas produced by these boundary lines have different colors (angles for the vectors).

Reaction-diffusion is interesting in that it has dynamic behavior, and the boundary lines here don’t seem to match the behaviors I see, so I think it must be the wrong way to think about the problem.

I think I need to study https://itp.uni-frankfurt.de/~gros/StudentProjects/Applets_2014_GrayScott/[14] . The lines shown there match the “parameter map”.

 5  Next#

Next week I want to explore some things Karl Sims mentioned:

  1. A “parameter map” that shows all the different behaviors.
  2. Directionally biased diffusion.
  3. Kill, feed parameters varying across space or time.
  4. Diffusion rate varying across space or time.
  5. Output values feeding back into input parameters.

I also want to try out different coloring and contrast functions to turn this into an art project. See next week’s project page.

Email me , or tweet @redblobgames, or comment: