Pathfinding

Pathfinding is probably the single most popular and frustrating game AI problem in the industry. Games like role-playing games (RPGs) and real-time strategy games (RTS) often have characters sent on missions from their current location to a predetermined, player determined, or menu-selected waypoint (destination). The perfect situation of a movement would be a no-collision or obstacle path.

The typical path from a character’s current position to the destination (waypoint) usually passes directly through one or more obstacles.

The first solution in avoiding these obstacles is to “ride the rail” or walk around the object’s surface until you’re free to continue toward the destination.

Although the “riding the rail” algorithm solves the problem of avoiding obstacles, it looks silly and unrealistic, sort of a blind person’s path solution.

The next solution is to make the path less blocky by connecting points of the hypotenuse of the triangles.

The last issue to make the path to our waypoint truly realistic is to curve the path.

The way to simulate a realistic character movement in 3D is to plot a straightforward path from the character’s current position to its destination and record all of the obstacles from a world table that lie on this straight line. For each obstacle, calculate the original collision point and the two tangent points on either side of the obstacle. The point closest in distance is the one selected to be connected as the hypotenuse of the triangle.

There are several techniques to achieve this pathfinding problem, such as algorithmic (equations) or methods such as “flood fill” and “A*” (pronounced “A star”) solutions. A flood fill is similar to a graphics application’s “paint” tool, which will completely color a given area.

If we were to flood fill the white area with black, it would continue filling until it hit a non-white spot.

If we were to start on location “A,” the fill would traverse in all directions until the new space was non-white.

Each space or “node” would check its neighbors in the four directions, and if the neighbor is white, it would be changed to black. This recursive (repeating) process would repeat until all four directions starting with node “A” return a “false” or no non-white connecting nodes are left.

The A* algorithm is similar. A node is placed on an “open” list, and if a shorter node path is found, the new path replaces the current path (which gets placed on a “closed” list). The shortest path from a start node to a destination node is the final path left when all paths have been searched.

The objects that are on the map as collision areas should include the static objects like buildings, water, fences, and so on, as well as dynamic, moveable objects like vehicles, people, and floating bridges. The game design may include the ability to destroy objects like buildings and bridges, thereby modifying the original list of static objects. Another game design might require that characters avoid areas due to hazardous conditions that may be in effect under certain conditions or for a certain time period or avoid specific tribes and clans. These avoidance issues greatly change the terrain path created. One solution would be to dynamically (on the fly) set these areas when needed as an obstacle block or zone and let the path-finding function handle this as though it were a large building to walk around.

The solutions discussed thus far don’t take into account various terrain elevations. Nature has rivers running downhill, and our characters would probably prefer a downhill path to town rather than a Mount Everest climbing shortcut. The distance over Everest may be the shortest, but its elevation and treachery makes it less desirable. If each node had an elevation factor, the path created would be the shortest path within reason. Otherwise, the character’s morale and fatigue factors would be greatly increased, causing negative results later. The elevation factor could also be used in the character’s “line of sight” functionality. If a character were standing in a ditch, that character probably wouldn’t see the massive horde of enemy troops heading toward him in the distance. On the other hand, a fort on top of a mountain would have its residents’ “line of sight” able to see quite a distance and its cannons able to fire a long distance. If a character is standing on one side of a building, the enemy approaching from the other side would be unnoticed since the character’s “line of sight” would be blocked by the building. These factors add to the realism of the game, and that’s what players demand. That’s what your game design should include.

Other pathfinding issues would include formations (groups of moving objects) and the turn radius and ramping up or down speed to initialize a movement and terminate a movement. A formation is a group of characters all moving independently but as a group. Soldiers in two columns march behind their leader. As the leader turns, so does the entire troop. They all must maintain their relative distance from the row in front of them, march at the same speed (pace), and turn their bodies relative to their path line. The leader may be marching north as the last soldier in the line is still marching east 50 feet behind the leader. Formations also must not collide and bounce off each other like billiard balls. These are complex structures that must be in your game design and algorithmically understood by the team developing your vision.

Humans are bipeds and, if they are moving the wrong direction, can turn on a dime and reverse their movement toward the goal. Vehicles and horses need more space to create a turn radius. Your car needs to circle or turn around when reversing from the road south to the road north. We have fancy terms like the “U-turn” and the “K-turn” when a car is reversing its direction. People can perform this maneuver with an “about face” motion. These factors must be incorporated into the game design for a realistic look and feel in your game. People, horses, and vehicles don’t jump into a quick speed and just stop on a dime at will. Moving objects need to increase their speed (velocity) and decrease it before coming to a complete stop. These factors are not easy to implement but should be addressed in the design document and discussed as the game is being developed. Often, ideas, concepts, and features that are in the design document hit the cutting room floor (do not make it to the final product). These design document items should be frequently discussed and addressed to determine their status as to whether they are “in,” “out,” or “on hold” for the final product. Most items, given enough development time and money, can be implemented. In reality, developers don’t have this luxury of unlimited time and available finances.

AI is an important consideration in the success of your game. Often, I read on Internet gaming sites that the development team planned to do AI last and within a week or two. This inexperienced and ignorant decision severely delayed the project, and the AI was quickly finished without a real solid solution. The teams have often said in the aftermath of a major project that they wished they had started the AI earlier and had longer to work on the best AI possible (not the best AI as soon as possible).