Illogica
The science of artificial intelligence.


Pathfinding

Easily the most frequently encountered AI challenge in game development is pathfinding. In a nutshell, pathfinding is a way to direct an AI agent from their present location to a goal (usually a good position to attack the player), while avoiding obstacles and hazards. One of the most popular ways of doing this is to assign a cost for each patch of ground. Some areas have infinite cost; they're flagged as barriers. The best route is the one with the least cost. A simple real-life analogue is to think about how much time it would take to drive through a certain area. If you want to get from point A to point B, you have the choice of taking surface streets with tons of stoplights, back roads with little traffic, or freeways with traffic but high top speeds. Even if the route would be shorter by taking surface streets, many of us would take back roads or freeways, whichever is fastest, unless the destination is pretty close by. If the destination is 4 blocks away, we'd likely take surface streets, even if there was a freeway route, simply because the time to get to the freeway and back would be greater than the amount of time taking the freeway would save us. If we knew back roads that paralleled a stretch of freeway clogged by traffic, many of us would choose to take the back roads unless doing so would take significantly longer. As an example of a barrier, you'd have to drive around a lake rather than attempt to go straight through it unless there was a ferry that would drastically cut the time of crossing the late.

Likewise, AI agents consider the cost of passing through each patch of ground. To use the previous example, traveling along a surface road could cost 5 units per mile, but taking a freeway would cost 1 unit unless the freeway was likely to be clogged with traffic, in which case it would cost 4 units (or 50 units if you live in Los Angeles....!) A back road with little traffic and few stoplights would cost 3 units. After the AI has considered all likely routes, it finds the route that costs the least and takes it. This can be very computationally very expensive if not done right. After all, calculating the cost from point A to point B for every possible route (even ones that are obviously not right, such as going from Los Angeles to San Francisco by driving to Florida to New York to Alaska to San Francisco) would take an insane amount of computational power. The algorithms that exist to do pathfinding often start by removing trivial cases, or such cases are automatically eliminated as the algorithm goes from one iteration to the next. The most widely used algorithm is A*, but there are plenty of others. If you're interested in learning more about there are a billion good web pages that describe the A* algorithm and its many offshoots.

Pathfinding becomes more complicated when the AI has to also exhibit certain behavior during the pathfinding process. They may need to avoid a ticking time bomb, for instance, or there may be zones that provide cover from enemy fire that the AI should move through even if doing so would be a more costly path than simply running from point A to point B. Often, guide points are added to maps that help tell the AI to modify their AI behavior. A "safe" guide point would reduce the cost moving through spaces around it, so that AI agents would prefer to go through those points. A hazard guide point would increase the cost of moving through spaces around it. Such guide points could be added dynamically to the world (such as a grenade landing next to an AI soldier) or be "baked in" to the environment, such as guide points that are placed around particularly tricky paths through hazardous terrain.

Assigning the cost per patch of terrain is a computationally expensive task. Often in games, a program is created that takes a map and creates a grid of path nodes and their costs. Then, when that level is loaded into a game, the nodes are a part of the map data, and the game doesn't have to take the time to calculate it all on the fly.

In real life, there often is no such option. Pathfinding by assigning costs to various terrain types is much more difficult to do than it is in games, where the developer has complete control over the environment. A pathfinding algorithm can help guide you around a city's roads, but it would work very poorly when an AI-controlled car is trying to traverse a dirt road that's not on any sort of map. DARPA recently performed a race between AI-controlled cars in the desert, and they used placed markers as guide points that the AI could use to find which way it was supposed to go. That helped these cars to go roughly in the direction they needed to go, but it didn't help them actually navigate the terrain very well. A vast majority of the cars ended up in a ditch or stuck on a rock. Needless to say, pathfinding technology works extremely well in video games, but it has a ways to go before it will work equally well in real life.


Back to The Science of A.I.

Back to Illogica