Pathfinding is a pretty important aspect of any game. Be it a first person shooter or real time strategy. It literally means getting an AI controlled unit from point a to point b.
It is actually one of the more difficult things to get right in a game. A programmer needs to code for possible chokes in a path (units crowding into a bottle neck thereby blocking the path temporarily), danger in an area (a bad guy deciding if it’s a good idea to take the shortest path available or take a safer path in which chances of getting hit are less) and so on.
Such pathfinding problems, i.e. finding the quickest and safest path, are faced by real military strategists as well.
Some of you may be familiar with the world war 2 strategy game Panzer General released in 1994. it was a turn based game and spawned quiet a few sequels. Researchers at the University of Granada, Spain used the game and the ant colony optimization algorithm to develop a software that can do pathfinding for real armies.
The Ant Colony Optimization algorithm is a heuristic algorithm that is based on the behavior of ants.
Ants can be considered to wander randomly, until they find food. Once they find food they head straight back to their colony, leaving a trail of pheromones behind them. Other ants will pick up this trail and follow it and reinforce it with their own pheromone trail. The pheromones evaporate over time so the ‘trail’ might get weak if it is used less often and eventually ‘die’. In the picture on the right the first ant finds a path from N to F. The other ants follow this path and the other alternate ones. The center one is shortest so more ants use it and it is reinforced until eventually it is the only one that is used.
This same principle was applied by the people over at the University of Granada to an army. Each ant can be considered a company of troops. This company was then tasked with finding the fastest path from point A to point B while sustaining as few casualties as possible. They would leave a trail of digital pheromones based in how successful they were at the task. Using their progress the whole army could find an optimal path through the digital battlefield.
Meanwhile the Spanish Ministry of Defence was so impressed it is considering employing the simulator to plan real military strategies.