Run and Tumble AI Prototype


#1

This morning, while reading a book about the evolution of intelligent life, I came across a concept called ‘run and tumble’. It’s a method of microbial movement, some of the simplest intelligence possible.

In essence, a simple microbe has two actions: it can move forward or it can rotate. Switching randomly between these is fine but doesn’t get you many resources. Instead, some microbes compare the level of nutrients at the present moment to the level a few moments ago (a kind of crude gradient approximation). If the level has increased, they move forward towards a potential compound cloud. If not, they turn randomly and hope for more nutrients elsewhere.

This got me thinking. With all the talk of bacteria on Slack (which should probably be put on the dev forums at some point for people like me who didn’t manage to read much of it) I wondered whether we could use such a system for bacteria in-game. They don’t need very complex AI, and I thought a run and tumble system could create quite interesting swarming behaviour.

Part of my maths degree involves learning MATLAB, so I decided to put it to some good use and write a prototype. This is the result:

The function microbe(n,a,b) runs the simulation with n microbes with linear velocity a and angular velocity b, with the compound density determined by a function compounds(x,y). Yellow areas correspond to higher compound density, blue to lower.

The video above is me testing some combinations of parameters and compound densities. It’s hard to find a good compound function that works in this context as the simulation world wraps around in both directions, so the best choice is a function that’s periodic with period 100 in both directions. Obviously this is of little concern in the actual game.

It turns out that fast microbes are pretty terrible at collecting resources with this system. What really gives you an advantage is quick turning. I’d love to see what would happen in a more complex environment with moving compound densities, but my coding skills aren’t quite up to that.

The footage you’re seeing was shot in real-time on a remote connection to a university computer. Clearly performance isn’t great - at 50 bacteria it takes several minutes for the allotted 1000 frames of animation to pass - but I hope it would be better on a more powerful system. Plus there are likely many ways of optimising my code, I didn’t give it much thought.

Hopefully this can be at least somewhat useful. How would I go about adding the code to the thrive-prototypes repository?

For the moment, here’s the pasted code. I doubt anyone here actually uses MATLAB but ¯\__(ツ)_/¯. Also I apologise for any programming faux pas. I’m not a programmer.

It should be noted that the change in orientation comes from a normal distribution with standard deviation determined by the user. I tried a uniform but the resulting movement wasn’t as pleasant or natural.

microbe.m
function [  ] = microbe(n,a,b)
%Simulates "run and tumble" method of unicellular movement.
%   Plots n microbes with linear speed a and angular speed b moving into
%   higher compound densities. Uses an approximated gradient ascent system
%   found in biology.

set(gcf,'Units','normalized','OuterPosition',[0.25,0.25,0.75,0.75]);

[X,Y]=meshgrid(0:1:100,0:1:100);
Z = compounds(X,Y);

x = zeros(1000,n);
y = zeros(1000,n);
density = zeros(1000,n);
orient = randn(1,n);

x(1,:) = 100*rand(1,n);
y(1,:) = 100*rand(1,n);
density(1,:) = compounds(x(1,:),y(1,:));
for i = 2:1000
    density(i,:) = compounds(x(i-1,:),y(i-1,:));
    for j = 1:n
        if density(i,j) >= density(i-1,j)
            x(i,j) = mod(x(i-1,j)+a*cos(orient(j)),100);
            y(i,j) = mod(y(i-1,j)+a*sin(orient(j)),100);
        else
            orient(j) = orient(j) + normrnd(0,b);
            x(i,j) = x(i-1,j);
            y(i,j) = y(i-1,j);
        end
    end
    imagesc(Z)
    axis([0 100 0 100])
    hold on
    for j = 1:n
        plot(x(i,j),y(i,j),'or','MarkerSize',5,'MarkerFaceColor','r')
    end
    pause(.001)
    hold off
end

end
compounds.m
function [ z ] = compounds(x,y)
%Compound density function over a 100x100 grid.
%   Must use element-wise operations (e.g. use .* instead of *). For best
%   results, use a function which wraps around 0:100 by 0:100 without
%   discontinuities, e.g. periodic in x and y directions with period 100 in
%   both.
    z = sin(x.*(pi/100))+sin(y.*(pi/100));
end

#2

This is fantastic! To add it to the thrive prototypes just use git.
If you’re unfamiliar with git I’d be happy to give a quick example.


#3

I’m familiar with it from looking at other people doing things in the Thrive repository, and I’ve made one or two file edits in the past. I’m just not sure how I’m meant to go about creating files and folders, e.g. should I make my own branch then submit a pull request or just add things directly (if I can)?


#4

I think it would be best to pull the thrive-prototypes and then put these in the AI folder then commit and push. That way all the AI stuff is in the same place.


#5

Firstly I think that’s really cool! I’m glad you’re getting into maths and programming. If you ever need help with anything just ask.

I like how realistic this idea is, I think that’s a real strength.

I also think it’s pretty powerful if all cells use the same ai. We don’t really need to distinguish between different types of cell IMO. It’s more work to have different ai’s when a simple system could work for every type of cell.

Also yeah don’t worry about branches with the prototypes repo, it’s fine to just add files and push to master.


#6

Nice work Oliver! The behaviour in that video looks really cool and realistic!