Simulating Bacterial Chemotaxis

A screenshot of the default simulation
A screenshot of the default simulation

Some months ago I was reading an article that described the behaviour of E. coli bacteria and comparing that to working patterns. An odd comparison, but what struck me was the fact that the bacteria behaves in such a simple fashion with basic rules.

This got me thinking that this could be good behaviour to model for enemy AI given basic rules can lead to complex looking behaviour as ably demonstrated decades ago with Boulder Dash, and which I myself wrote about in 2010.

The article didn't mention it but some searching later I found the name of the behaviour is Chemotaxis and it is essentially the movement of an organism either toward or away from chemicals, depending on if the detected chemical is positive (a food source) or negative (a poison).

Although Wikipedia has a complicated page devoted to it, I found a page by the Parkinson Lab at the University of Utah which describes it in a simpler fashion that I could understand.

In isotropic chemical environments, E. coli swims in a random walk pattern produced by alternating episodes of counter-clockwise (CCW) and clockwise (CW) flagellar rotation (Fig. 3, left panel). In an attractant or repellent gradient, the cells monitor chemoeffector concentration changes as they move about and use that information to modulate the probability of the next tumbling event (Fig. 3, right panel. These locomotor responses extend runs that take the cells in favorable directions (toward attractants and away from repellents), resulting in net movement toward preferred environments. Brownian motion and spontaneous tumbling episodes frequently knock the cells off course, so they must constantly assess their direction of travel with respect to the chemical gradient.
Source: An overview of E. coli chemotaxis, Parkinson Lab, Department of Biology, University of Utah

I say a simpler fashion, but when I looked up Brownian motion my brain promptly had a meltdown and I decided that as this wasn't a scientific simulation I could skip some steps!

Before we begin

The default simulation after 100 moves
The default simulation after 100 moves

As usual, take this code with a pinch of salt. It's a basic simulation, not a proper model. If you somehow came to this page expecting hard science then you should go read an article written by someone who knows what they are talking about.

I'm also not going to describe the code. This is probably the most complicated sample project I've written for this blog and while a lot of it is unrelated directly to the simulation core, there's still too much to cover in a single post. However, I did write an article on adding scripting to .NET applications derived from this example, and another on collision detection using quadtrees, which, while not used by this project, was inspired by the terrible performance of the simulation!

Finally, please remember this is a basic simulation. I already noted I had a brain freeze the moment I saw the equations for Brownian motion and I've also dumbed down or skipped other aspects, for example E. coli have multiple flagellar which are used for momentum and direction; I'm not trying to model this either.

To simply this simulation even further, all strands move at the same speed and instead of using vectors everything is based on simple compass headings.

The Rules

The default simulation after 1000 moves
The default simulation after 1000 moves
  • Each "turn", there is a chance a strand will change its heading clockwise or anti-clockwise, as my nod to Brownian motion collisions and flagellar propulsion
  • At the start of the turn, each bacterial strand will sample its location to see if it is closer to a food source (attractor) or poison (repellant)
  • The stand will then move according to its current heading
  • After moving it will sample the new location to see if it is now closer or further away than the previous sample.
  • If the closest chemoeffector is a food source and it is now further away, or is a poison source to which it is now closer, it will turn left or right to try and get closer or further away
  • Colliding directly with a poison source will kill the strand
  • Colliding directly with a food source will consume the source

Although this doesn't sound like a particular complex rule-set, seeing it in action is quite something!

Scenario Setup

The following options are used to configure a scenario. Changing these requires the simulation to be restarted.

Option Description
Environment Seed Specifies the seed used for the environment random number generator
Movement Seed Specifies the seed used for the movement random number generator
Size The size of the playing field
Strands Initial number of bacteria strands
Attractors Initial number of attractor chemoeffectors
Attractor Action The action that occurs when a bacteria strand collides with an attractor
Repellants Initial number of repellant chemoeffectors
Repellant Action The action that occurs when a bacteria strand collides with a repellant
Attractor Strength A range that defines the starting strength of an attractor
Repellant Strength A range that defines the starting strength of a repellant

Scenario Options

The following options are available and can be toggled while the scenario is running.

Option Description
Wrap Boundaries Allows entities to wrap from one side of the playing field to the other. If disabled, entities will change direction when hitting the boundary
Respawn Attractors If set, consumed food sources will respawn at a new location
Allow Binary Fission If set, bacteria will occasionally undergo binary fission and split into a pair
Allow Strand Collisions Specifies if bacteria can collide with each other. Will slow down the simulation significantly
Allow Attrition Specifies if bacteria can loose strength. Unless the strand finds a food source, it will die. I just added this out of curiosity, it has no basis that I'm aware
Mobile Repellents If set, repellants will move across the playing field via a fixed heading

JavaScript Support

A not-very realistic scenario created via JavaScript
A not-very realistic scenario created via JavaScript

A simulation can also be set up via JavaScript, useful when you want something that the randomised setup can't handle. I extracted the JavaScript support into a improved demonstration project and wrote adding scripting to .NET applications to describe it.

Performance implications

Viewing the trails where a strand has been
Viewing the trails where a strand has been

The simulation code is pretty slow as I made no effort to optimise it, e.g. by using a quadtree to break down collision detection. Also, Windows Forms does not make for a great simulation environment - I think next time I might try using OpenGL to host the simulation instead.

There are a number of UI options for controlling the appearance, e.g. for using simplified shapes, or disabling gradients - it is very interesting to note just how exceedingly slow .NET is at drawing a circle. You can also switch on trails to see the last 128 positions a strand has visited.

Closing Thoughts

An animation of an earlier version of the application
An animation of an earlier version of the application

This was another fun project. It was both fascinating and yet quite creepy watching them mill around, then suddenly swarm on a source, consume it completely and then move on. Will this be useful in any future game I write? Who knows.

This wasn't the usual type of example program I write for this blog so comments welcome!

The source, as it was at the time this article was published, is available from the links on this page. Any updates will be published to our GitHub repository.

Files


Comments

We'll never share your email with anyone else Styling with Markdown is supported