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
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
- 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 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
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
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.
Like what you're reading? Perhaps you like to buy us a coffee?
Files
Comments
The founder of Cyotek, Richard enjoys creating new blog content for the site. Much more though, he likes to develop programs, and can often found writing reams of code. A long term gamer, he has aspirations in one day creating an epic video game - but until that time comes, he is mostly content with adding new bugs to WebCopy and the other Cyotek products.