#Coding #Adventure #Ant #Slime #Simulations
Hi everyone, and welcome to another episode of Coding Adventures. Today we’re going to be experimenting with some little ant and slime simulations — but first, I’d like you to imagine that you’re a merchant who travels from town to town selling cabbages, perhaps.
So you’d like to find a path that takes you through all of the towns on this map, arriving back home in the shortest possible distance. Here is some slightly confusing code which recursively generates all the possible solutions to this problem, and each of these solutions
Is evaluated in this function over here, simply by calculating the length of the path, and then saving it if it’s the best one we’ve found so far. So for these 12 towns, let’s try running the program, and it only takes a second or so
To crunch the numbers and here we have your optimal cabbage route. But now let’s say that a new town crops up over here, which you obviously want to visit as well. So, let’s run the program again. This time, it’s taking a lot longer figure
Out the answer. The trouble is, the number of unique solutions is equal to the number of points minus one, factorial, divided by 2. So with 3 towns, there’s just one solution, but by the time we get to a modest 20 towns, there’s already something outrageous like 60 quadrillion possible solutions.
Even with much more sophisticated algorithms, it’s very expensive and often just completely infeasible to find the optimal solution, and so a lot of interesting techniques have been developed for finding something close to perfect very quickly. As I was reading up on these
A little, I became intrigued by one approach in particular: Ant Colony Optimization, which is inspired by the foraging behaviour of — you guessed it! –ants. Essentially how it goes is we place a virtual ant at one of these towns, which then needs
To pick a new town to travel to that it hasn’t visited yet. The ant would prefer someplace nearby, so I’ll calculate each town’s desirability as 1 over the distance, raised to some power. The higher that power is, the more strongly the ant will prefer the nearby towns. It’ll
Make its final decision at random, but the probabilities are weighted based on that desirability value. So let’s watch our adventurous little ant on its mission. Now that it’s visited every town, we can retrace its steps to see the path that it took. It’s
Not a fantastic path, but solving the entire problem is a lot to ask of one tiny ant, so let’s give it some friends to help it explore. Once they’ve have all finished their journeys, what we’ll do is score each of their paths by how good they are, and these will act like
Pheromone trails as the analogy goes, to help guide the next round of ants. So ultimately each ant chooses the next town in its path probabilistically, based on the distance to the town and the strength of the pheromone trail there. In that way, each new
Group of ants explores random variations of the best paths found so far, and any improvements are reinforced thanks to the pheromones. Let’s try run this new approach on those twenty towns from earlier, to see if it actually
Works. I’ve slowed the simulation down so we can get an idea of how the pheromone trails change over time, and here it has already settled into a really good looking path. It took about 50 ants a split second to find this, which is a nice improvement from the
6 centuries we were facing before, although of course the tradeoff is we have no assurance that this is actually the best possible solution. Just for fun — and please try to contain your excitement — I’m going to ramp this
Up to one hundred towns. Here again I’m showing a slowed down view of the pheromone trails, but it’s maybe interesting as well if I run it again and instead display the best path the ants have found so far, so we can see how that develops over time as well.
So I think this is a really cool algorithm, the only slightly annoying thing is there a number of parameters for controlling the simulation, and it takes a bit of trial and error to find values that work well for a given problem.
Anyway, this has got me interested in playing around with a less practical, but more sort of fun visual simulation of ants. So I started by making a simple flat ant graphic, and brought it to life a little with a crude walk animation. I then imported it into Unity,
But something went terribly wrong… and the result was mildly terrifying. I got it working in the end though, and wrote some code to make it follow this green dot around, which is going to represent the ants’ food source.
Here is the ant’s code as it stands right now… and I want to modify this quickly to get the ant to wander about on its own. I’ll try achieve this by simply nudging the desired direction by some random vector each frame, and let’s see how that looks.
This ant is too indecisive and not making much progress in its life, but I can turn the wander strength way down, and now it’s exploring its surroundings quite nicely. I think the next step should be for the ant to be able to sense food if it’s nearby, and
Pick it up. So I’ve added some lines of code for handling that, and let’s test this with just one ant to start with. That’s working well I think, so now I’ll test this with a bunch of ants. The ants shouldn’t just keep all the food they find for themselves though, they need
To take it back home to support the colony. I don’t know much about ants, so I did a little research about how they even find their way home. It turns out they’re smarter than I’d imagined, for example beyond recognizing landmarks which is pretty impressive, some desert-dwelling
Species are apparently able to combine directional information from polarized light with distance information from essentially an internal pedometer to calculate a straight path back home. I’d like to keep things simple though, and have all navigation done via pheromones. So,
Inspired by this really cool video that I came across, I’m going to have the ants use two types of pheromones, this blue one they’ll lay down when leaving their home to search for food, and then if they actually find food, they should turn around and follow the blue
Pheromones home, while laying down these red pheromones to try recruit other ants to the food source. They’re not doing a great job at the moment, but that’s not their fault — I haven’t actually implemented the pheromone following yet. So for that, I’m going to ask each ant to sample
Three regions in front of it, and based on the concentration of pheromone it detects in these regions it will either turn left, keep moving forwards, or turn right, plus a little of random turning still on top of that. I think this is a nice simple way of
Handling it, which I actually came across in this paper, which describes an approach to that problem we looked at at the start of the video, inspired by slime moulds of all things. It’s quite intriguing, so I might come back to it, but for now I’ll just be
Borrowing this little sensory scheme for the ants. Here is the actual code for it, and as you can see down over here, I’ve made the pheromones lose strength over time to sort of mimic the effect of evaporation. I’d really like the
Pheromones to also diffuse outwards over time, but I’m not quite sure how to handle that yet. Anyway, let’s give this a quick trial run with a handful of ants. Okay, it seems to be working roughly how I intended, so next up I want the ants to be
Able to avoid obstacles, or at least not simply walk right through them, so I’ve spent a bit of time writing some dubious collision detection code, which does nevertheless seem to be getting the job done. I then wanted to generate some sort of map like one of these from this ancient tutorial
Series of mine. I have a strong aversion to my old code though, so instead of reusing that project like a reasonable person I began reimplementing it all from scratch. After several hours work, however, I came to the realisation that my new code is not so great either… Fast-forwarding through some frustration,
I eventually did get it working, and I also added a brush so that I could easily paint in obstacles, or carve out little passageways. Come to think of it, I could have just taken 2 minutes to draw this in Paint, but anyway
I ended up making this map for the ants, and I wrote a simple spawner script to scatter some clumps of food about the place. And so, with this all set up, let’s unleash 500 ants from the nest, and see what they get up to.
Over on the right, the ants have collected that entire food cluster, but they’ll keep returning there for a while still, until the pheromone trail has finally evaporated. Real ants are vastly more sophisticated than what I’m simulating here of course, and in this
Situation for example I read that pharaoh ants have been found to actually deposit repellent pheromones when a resource has been depleted, to discourage future ants from that trail. This has been fun to play with, and there are many things I’d still like to try out,
But my attention has been sidetracked somewhat by these strange and fascinating slime mold organisms. Here’s another slime paper I came across, this time about pattern formation. The behaviour described here is pretty similar to the ant stuff I’ve been doing, but I’d
Like to give it a quick try and this time I want to implement it as a compute shader so that I can hopefully do a much larger simulation. The first thing I wanted to get working was generating pseudo random numbers in the shader.
I saw a recommendation for using this little function, which takes in a number, and just fiddles with the bits a little. There’s nothing actually random about this of course, but the outputs should hopefully be very different for inputs which are close together.
To test it, I have this little function, which is going to be run in parallel for every pixel in a texture that I’ve given it. We can start by getting the index of the current pixel,
Which’ll be 0 for the first pixel, one for the next, and so on. And then we can generate a pseudo random number for that pixel simply by passing the index through the hash function. I’ll set the brightness of the current pixel to that value, divided by the maximum possible
Value just to scale it between 0 and 1. And let’s now take a look at the result! So it seems we have some nice random looking noise, but let me increase the size of the texture, just to see if this still holds up. We’re on the lookout for any suspicious repeating
Patterns; for example if it looked like this, or even worse like this — we should definitely use a different hash function. But I think it was looking good. So I’ve now started work on the slime simulation – first of all, I’ve created this agent structure,
Which simply holds a position and an angle, and then I have some code for updating each agent. The update rule is very simple at the moment, just move the agent based on its current angle, and if it tries to go off the edge of the screen, don’t let it, and turn it to
Face some new random angle. At the end I have this trail map texture, and I’m just recording the agent’s position as a white pixel in there. Let’s see what this looks like. Not terribly interesting so far, unsurprisingly. Now just
Like with the ants, we want these trails to evaporate over time, so I’ll make another function that runs for every pixel in the trail map, and just subtracts a little bit each frame. You can probably imagine how this looks, but I’ll show it anyway. Next we want
The trails to diffuse over time, which is something I never got around to implementing for the ants, but it’s really simple with this setup, because the map is an image, so we can just blur it a little each frame. Here’s my very crude code for that, which just sets
The colour of each pixel to be the average of its neighbours. Now we just need to make these agents attracted to the trails. So I’ve added this code, which simply senses the concentration of the trail at three points in front of the agent like
Before, and turns based on that. And there’s also some randomness involved. The sense function looks like this, and in here it’s simply adding up all the values in the trail texture that lie inside the bounds of the sensor. Let’s have a look at the result.
This is currently taking place on a very small scale, it’s a 320 x 180 map, with 250 agents, but because we’ve taken the trouble to write this as a compute shader, it should be able to handle something much bigger. For our first experiment, I’ve initialized the agents with
Random positions inside a circle, all facing towards the centre, and let’s see how this evolves over time. So these have been pretty interesting-looking I think, but let’s try making multiple species of slime. This should actually be really simple, I’ll go into the agent structure, and add
A species mask, so each agent can belong to one of four different species. Then when drawing the trail, I’ll draw into the red, green, blue, or alpha channel of the texture based on that mask, and finally in the sense function, I’ll just modify this line so that it treats
The trails of other species as negative, so it should try steer away from them. Let’s try a simple test with red and green slime. That’s kind of cool, let’s try mutating a third of the population into blue slime and see what that looks like.
I find it pretty fascinating seeing these organic looking patterns emerge from those really simple rules we’ve implemented. There’s definitely much more to explore here, but other projects are calling, so I’m going to leave this here for now. I’ll put links in the description though to some far more
Impressive stuff that others have done with this technique, in case you’re interested in checking those out. In any case, I hope you’ve enjoyed the video, and until next time, cheers.
0 Comments