Week 13:
Pathfinding: Help! I'm lost!
Hrmm....my time for the weekly update. This is going up late because I'm very busy trying to bring you, the gamer, an awesome game. I touched on the basis of the AI in my last update and I think this time I will touch on the movement and pathfinding code used by the AI this time.
There are a several means for an AI to navigate successfully a level; in particular precalculated pathfinding and dynamic pathfinding. When implementing the movement code for the AI in Blood 2, I had an interesting decision to make on what kind of implementation to use. I opted for a pure dynamic pathfinding implementation for several reasons. First, I have the intention of creating a lot of action and interaction in typical encounters between AI, the player, and other objects in a typical level. Because of the dynamic nature of a lot of objects in the levels, precalculated paths would have a high chance of never reaching completion due to some object or other AI crossing the path and blocking the moving AI. Bottom line: wasted processing on paths I would never follow through to the end. Also, if I did choose a precalculated path and become blocked by a dynamic object, I could then revert to a dynamic pathfinding method for the moment to deal with the obstruction. Since the shortest path to a destination is a straight line and such lines will make up a precalculated path when possible, why not just tell the AI to walk a straight line to the destination and use a momentary dynamic pathfinding scheme to deal with a dynamic obstruction?
The simplest way to see if an AI is obstructed is to measure the distance from the last position to the current position and see if that distance is less than the distance it was trying to go in the last frame. It is a very low processor intensive activity which is always good since a dynamic pathfinding scheme needs to be fast. An additional calculation occurs at the same time to handle ledges by simply casting a downward segment in front at a distance equal to the desired distance to move in the next frame.
Next, if an obstruction is detected, the exact way the AI is obstructed needs to be defined.
Most, if not all, obstructions can be classified and dealt with in several categories: obstructions that can be crawled under, obstructions that can be climbed/jumped over, and obstructions that can/must be walked around. AI models in Blood 2 use a square bounding box to determine collisions and boundaries. When the obstruction in encountered, a series of points are generated on front of the AI and "frames" it. Line segments are thrown forward from each of these points around the front of the AI and intersections and misses with the obstruction are recorded.
After determining how the AI is obstructed, the recorded data is compared and the determines one of three courses of action: jump over it, crawl under, or go around it.
The first two actions are straight forward and self-explanatory. The third action brings further calculations because of an additional question: which way around is the best/fastest? The AI will generate two points on the center left and right and throw a line segment forward and recorded intersections and misses. If an intersection occurs at a point, the point is moved left or right accordingly a distance equal to the width of the AI. When a miss is generated, the AI will turn to that direction as that has been determined to be the shortest path around the obstruction. However, if the expanding points intersects another obstruction to the right or left, the AI will turn in the opposite direction and head that way hoping to find another way out later on.
Some AI will use different elements of their pathfinding to solve other problems such as taking cover. For example, an AI will check if a low obstruction is within a distance in front of it and if so, will crouch to avoid being hit. The pathfinding and navigation code in Blood 2 is very flexible to all potential situations providing more realistic movement that is almost never repeated, does not require additional work from level designers, and does not produce a lot of partially wasted computations from precalculated paths.
One last thing: keep up in math class!! This stuff is not for the light-hearted, especially in a 3-D environment. However, it is fun to do. Any questions, feel free to mail me.
