Ant AI

I've been toiling away trying to come up with an algorithm which will make ants move in a believable manner while only using a very limited view (the 4 adjacent tiles which they can move to). This was much more difficult than I was expecting, it sounds too easy to say "the ants wander around randomly, then once they found food they could head home following the chemicals they left behind". Implementing it like that not only doesn't work, but the ants end up congregating around the ant hill and don't accomplish much of anything.

The final algorithm is a set of rules that look like this:
1. If carrying food, call go home AI.
2. If carrying food and in base, drop food (or wander until there is a spot to drop the food), set chemical output to low.
3. If not on surface, wander until on surface.
4. If on surface, check for food, pickup, change chemical output to high.
5. If on surface and no food, try to follow a chemical trail.
6. If no trail to follow search for food by looking for a spot with low (or no) chemicals.

The most successful part of this algorithm is step #6, the ants really spread out and find food spawned in a random location quickly.

The other interesting part, which isn't in the steps above, has to do with how the ants apply their pheromone to the tiles. I'm not sure how it is done in nature, but I have it set so if the trail is cold and the ant doesn't want other ants to follow it (i.e. not carrying food) it deposits only a small chemical trail, essentially marking that someone has been there. On the other hand if it does want other ants to follow it (i.e. carrying food), it will deposit a high amount.

To glue everything together in a natural manner, the chemical levels "decay" over time.

The biggest surprise of all this how complex the chemical trail following algorithm became. In an ideal world the chemical trail would be a high resolution heat-map style implementation which would allow the direction they are moving in to be clear. With my low resolution chemical trail, if there is a block of several high-chemical tiles all clumped up the ants start getting put into cycles, so I have to add special cases to resolve that. I'm not sure how interesting those special cases are so I'll leave them out for now.

I now have lots of variables to tweak (chemical output low, chemical output high, chemical decay rate, decay amount, max chemical per tile) several algorithms and functions which could use tweaking (chemicalOutput, trail following). All in all I'm very happy with the result given the constraints, and will hopefully have a demo out soon.

0 comments:

Post a Comment