Spanish Military Mods Panzer General for Real-World Pathfinding

There's few things that kill immersion more quickly than bad pathfinding. Watching your adversaries saunter in aimless loops, wander into crossfire or constantly bound off walls makes it hard to consider them the crack shock troops your supposed to be battling and quickly devolves tactical combat into a Laurel and Hardy affair. The problem gets even more complicated in situations like real-time strategy games, where groups of units not only need to be able to navigate but consider goals, obstacles and other environmental conditions.

Believe it or not, real-world militaries composed of human beings experience the same basic problem. What is the quickest, safest, most tactically sound way to move troops across a battlefield?

Researchers at the University of Granada have made some progress on this front. The team used the classic WWII strategy game Panzer General and an algorithm called ant colony optimization (ACO) to develop software that does pathfinding for real armies.

The ACO algorithm is a probabilistic method that uses principles evolved by ants to find and reinforce optimal paths between their colony and food. While they're foraging, ants wander fairly randomly. Once they find food, they head more or less straight back to the colony, leaving a trail of pheromones behind them. Other ants that pick up the scent are much more likely to follow the already traveled path, laying down pheromone tracks of their own, which reinforce the path. Over time, the pheromones evaporate, so paths that aren't reinforced die off. Since more ants will end up traveling a shorter path rather than a longer one during the same period of time, the shorter paths are continually reinforced while the longer ones become weaker. The result is that though each individual ant is fairly stupid, the colony itself is rather smart, finding optimal routes through the collective intelligence of the group.

The researchers at the University of Granada applied the algorithm to unit movement in a Panzer General mod. Each 'ant' in the simulation represented a company of troops. The ants were then tasked with finding the fastest path across a hostile map while sustaining as few casualties as possible, leaving behind digital pheromones based on their success. Using this information to build on their successes and avoid their failures, the colony was able to find optimal paths across the simulated battlefields.

The Spanish Ministry of Defense was so impressed by the research that it is considering using the simulator to plan real military strategies.

For their part, the researchers say their Panzer General mod could be tweaked to solve other real-world problems such as distributing aid relief. Variations of the ACO algorithm have already been used to tackle problems of protein folding and digital network routing.

We just want to know when they'll solve these problems...

[AGR via PopSci]