Diffusion
One of my long-running hobbies is playing with artificial-life-like simulation ideas. Most of the time, it starts when I read about some tidbit on some blog somewhere about how ants communicate or how bees swarm or whatever and I decide it might be fun to mess with that. Of course given my tendency toward getting bored to sleep while reading academic papers, I usually just skim for the big ideas and then run ahead with my instincts instead. That approach works surprisingly well, but sometimes I’ll miss something important or lack the mathematical knowledge in order to make some idea perform decently, scale, etc.
For months I’ve had a little idea brewing and sloshing around in my head that I’ve implemented/tested in various ways. It started out with the idea of how to manage a “world” with perhaps hundreds of tiny ants running around without having to run the usual path finding code on each ant. In other words, I wanted to make the path finding emergent from some simple rules in the system.
There’s a few ways to approach this problem (that I knew/know of), but I had some important constraints on myself: I wanted it to actually work in a somewhat intelligent/natural way so that it would *look* somewhat intelligent/natural, and I wanted to keep code very small with a small ruleset.
So my idea was to have the ants drop a scent trail as they moved and then have other ants follow scent trails. This of course led to a situation where the ants pretty much just ended up following each other around in circles. Then I changed it so that the ants had a food source to seek out. They moved randomly until they got close to the food source, then started laying down a trail. When other ants saw a trail, they followed it. This worked to effectively make the food location be a bigger target, was all. Nothing amazing. The next step was to make the ants drop scent when they saw food, or when they saw the scent of food dropped by another ant. This worked remarkably well, as I recall. Once the first random ant saw the food, it often was just a few game cycles before almost every single ant in the world was dropping trails to food and funneling directly to the goal. It was pretty cool to watch.
However, there were flaws. For one thing, this didn’t look very natural. The information (in the form of scent droppings) passed far, far too quickly. It was like the first ant sent out a radio signal and all the others picked up the GPS coordinates of the food immediately. This isn’t how real ants appear to work and so didn’t look natural. Adding a second food source often meant nothing as the ants would all end up funneling to the first food source that got noticed and no ants would wander around looking for other sources until the first one was depleted. I don’t know enough about ants to know if this is how they work, but I kind of doubt it. It felt too systematic to be natural - and perhaps this was because the ants didn’t have any other conflicting rules to follow, I dunno.
Another thing I tried was giving the ants a field of vision which meant they couldn’t see anything that wasn’t directly in their field of vision. This was kind of interesting as it changed things up a bit, but often it seemed the ants would just wander around randomly unless they got lucky and were near the food frenzy. Otherwise they never found the food since they couldn’t “see” all around them. I could never come up with a better ruleset to keep them from moving randomly and yet making them appear to naturally be milling around. :/
I’ve tried a ton of variations on these ideas, but the core of it is leaving scent trails in the world and using them for indirect communication. It just feels like somehow there is something to that idea as a way to replace individual intelligence in the ants so that they could be as simple as possible and as little code as possible.
Recently I ran across a paper about an idea called antiobjects. The core of the idea there, I think, is that sometimes thinking in OO causes us to try to do things the wrong way and their example was trying to program intelligent pac-man ghosts with a naive OO mindset can lead you to trying to make the ghosts learn how to navigate the maze and make the strategies they need to attack pac-man using the information available to the ghost from the ghost’s point of view. This caught my attention because of course that’s how I was trying to make my ants work - I wanted them to act according to the information available only to them and not cheat by having them somehow know the layout of the entire world (as you would need for a traditional path-finding algorithm). That’s why I used scent trails - to give the ants more information, but in a way that fit with what I know of nature.
The solution the paper tried to sell was the idea that somehow OO thinking was wrong in this case and you needed a new buzzword to fix it. In their example, they said to make the tiles of the world be smarter and then the ghosts only need to be simple. This is exactly what I was already doing with my ants - I was leaving scent trails for other ants to follow. I arrived at that conclusion myself simply by reading a bit about how ants communicate and then object-ifying the idea. So I find their argument of “antiobjects” to be pretty weak, frankly, because if you just think like mother nature does, you end up modeling it with objects the usual way anyway and it works just as well. 
That aside, though, the real bit that caught my eye was what they used to model their “scents” in their demos. They used a diffusion function to model the spread of the “scent” and then using some simple rules so things like walls didn’t influence the scent. So what ended up happening was, the scent filtered around the maze in a very natural way causing the ghosts to be able to track down the pac-man from far away with virtually no effort. This is what I was making my ants do, only I didn’t have the idea of using this diffusion function to model it.
The diffusion thing was interesting, so I decided I had to implement something just to see it work. So on Saturday I did - and it was cool. A single point of “release” of the scent would slowly diffuse to fill the entire area the longer I ran the simulation. I added walls which were simply cells that didn’t participate in the diffusion function, and suddenly I had what appeared to be a shockingly natural looking gas cloud, basically. It went around walls, slowly filled in spaces that were more shielded from the origin point, etc. Neat.
So then I took the next step which was to add a “creature” to the simulation that simply moved from cell to cell following a path of ever increasing values. It finds the approximate center of the “cloud of gas” pretty naturally - even navigating through small holes in the walls. (It’s like a scent-tracking dog!) This is all without ever actually making an explicit path finding algorithm. The creature literally only “sees” 4 neighbor cells at a time and simply moves according to simple rules. The emergent behavior is the appearance that the creature can sniff out the highest concentration of the gas cloud and move in and around walls as needed to get there and even follow the highest concentration as the diffusion process continues and the “gas” density shifts with time.
I recorded a video of it: diffusion.mov
This was pretty fun. I’m not sure if the diffusion itself is necessary, though. I still think just having the creatures/ants drop packets of scent works about the same in the end. However I could use the idea that the scent packets diffuse for a couple of simulation steps after they are dropped so as to expand their area of influence/visibility rather than having the ants themselves need to worry about fields of vision or something. It’s possible that would simplify some things - but I don’t know for sure. I’ll need to think about it and see what happens…