Features

GDC 2002: Polygon Soup for the Programmer's Soul: 3D Pathfinding

Anatomy of a Sector

Once a sector is generated it contains two important pieces of information, a bounding box and a list of portals. The bounding box is used at run-time to determine where, in the pathfind world, an AI currently is. The portal-list is the connection information that the path solver uses to calculate how an object gets from its current position to its destination position.

     class CPathfindSector
     {
        .
        .
        .
        CAABox BoundingBox;
        CVector<CPathfindPortal *> PortalList;
     };

As you can see, the sector is really just a spatial portal linkage; most of the interesting data is contained in the portal.

Anatomy of a Portal

The portal contains as much data as is necessary to get the AI from one sector to the next. At a minimum this data is a reference to the destination sector (possibly two sectors for a two-way portal), and its bounding box. A portal may also contain information about a teleport mechanism or an action to perform.

     class CPathfindPortal
     {
        .
        .
        .
        CPathfindSector * DestSector1;
        CPathfindSector * DestSector2;
        int MechanismID;
        MECHANISM_TYPE MechanismType;
        CPathfindPortal * MechanismExitPortal;
        ACTION_TYPE ActionType;
     };

As you can see all the connection information is stored in the portal and is therefore the "key" to solving a path.

Solving the Path

Bob, the digital super spy, needs to avert international tragedy at the UN building. Unfortunately, he's currently washing dirty socks in his basement. To make matters worse, everywhere he looks he sees an ocean of polygons swimming before his eyes. How can he possibly hope to reach his goal before time runs out?

Luckily for Bob, we can use his (X,Y,Z) location to lookup the pathfind sector he's washing socks in. This sector contains a list of portals he can use to get to other sectors, which contain their own portal lists, which can be used to get to yet more sectors, and so on and so forth.

At this point any number of best-path algorithms can be applied to get Bob to the UN building. We found a modified A-star algorithm solves the problem nicely. A simple implementation would use the accumulated distance between portals as the traversal cost, and the straight-line distance to the goal as the heuristic cost.

Now pretend that Bob and twenty of his closest buddies need to get to the UN building at the same time. Twenty different requests for complex paths can well exceed the amount of CPU your game devotes to AI each frame. Luckily for us, it is not very noticeable if we distribute the processing of these paths over a few frames. For example, if Bob sits and thinks for a half second before getting up and walking out the door, is anyone likely to notice? On the flip side, a half a second (500 milliseconds, ~1 billion clock cycles) is more then sufficient for a pathfinding system to solve a few simultaneous paths.

To distribute path solves over multiple frames you could use an algorithm like the one outlined in the following pseudo-code.

     while (Time_Has_Not_Elapsed () && CurrentPathSolver != NULL)
     {
        if (CurrentPathSolver->Process (Time_Remaining_This_Frame))
        {
           RELEASE (CurrentPathSolver);
           CurrentPathSolver = Get_Next_Path_Solver ();
        }
     }

This is a simple time slice manager which allows the current path to process a little bit each frame. When the path is solved, a new path is processed until either it finishes or time has elapsed.

To distribute the path solve itself over multiple frames, consider the following pseudo-code.

     CPathSolver::Process (float time)
     {
        while (Time_Has_Not_Elapsed)
        {
           CPathfindSector * sector = Get_Least_Cost_Sector ();

           if (sector == NULL)
           {
              Handle_No_Path ();
           }
           else if (sector == DestinationSector)
           {
              Hande_Path_Found ();
           }
           else
           {
              CPathfindPortal *portal = NULL;
              while (portal = sector->Get_Next_Portal (portal))
              {
                 Process_Portal (portal);
              }
           }
        }
     }

This algorithm will process as many sectors as necessary until its time-slice has elapsed.

Loosen Up Dude! Avoiding Robotic Paths

Using the sector/portal system, a solved path is represented by an ordered series of portals. This path will follow the form: walk to portal AB, turn to face portal BT, walk to portal BT, turn to face portal TU, walk to portal TU, and so on. Unless your AI is a robot, it is desirable for the unit to behave as organically as possible; bee-lining to each portal does not make for a very organic path.

To make our path appear a little more natural we'd like to use splines. In layman's terms, splines are basically curved lines that follow a set of points. Different types of splines follow their points in different ways. Some splines pass through their control points, whereas other splines act like magnets and are either attracted or repulsed by their control points. To see the advantage of splining the path, consider the following diagram.

	Splining the final path yields a much more organic curve.

Looks great, right? Unfortunately, there is a problem. Since the spline doesn't know anything about the sectors and portals that define the "safe" area for a unit to walk, it is likely that a curve on the spline will leave these volumes causing the unit to walk into desk corners, doorways, trash cans, or even meander off the edge of a cliff!

Luckily we can take advantage of a mathematical property of Bezier curves (a type of spline): if the control points of the Bezier curve lie inside a volume, then the curve itself will lie inside the volume. A Bezier curve is a cubic spline defined by a start point, an end point and a series of control points. The control points act like magnets to "pull" the curve away from the line segment defined by the start and end points.

Given this, our organic post process algorithm would function as follows:

Build a Bezier curve from the points on the final path. Build a list of the sectors and portals that the AI will pass through on its path. For each control point on the Bezier curve, clip it to the sector volumes. To clip a control point, form a line from the control point to the corresponding point on the un-splined path. Test this line segment to see if it passes through the side of any of the sector boxes in the list. If it does, check to see if the area of intersection is a portal. If the point intersects a sector wall, and it does not pass through a portal, then clip the control point to the sector wall; otherwise leave the point alone - it is valid.

	Control points that pass through a sector wall need to be clipped. Control points that pass through a portal are valid.

This algorithm will allow the AI to follow a nicely curved path without ever leaving the safe pathfind sectors.

Using Innate Waypaths

In a busy city, it would be odd to see cars driving down the sidewalk and pedestrians meandering through the streets. However, using our current pathfinding system this is exactly what you'd see. The flood fill algorithm does not encode (nor is it aware of) the type of ground covered, be it sidewalk, highway, or burning hot lava. A possible solution to this problem is to store surface information in each cell of the flood fill and have your compression algorithm only generate sectors containing cells of the same type. This would yield sidewalk sectors, highway sectors and burning hot lava sectors. The run-time path solver could then utilize this information when determining what sectors are valid for a given object (i.e. cars only pathfind through street sectors).

Innate waypaths are another powerful solution that integrates well with our pathfind system. A waypath is a manually created series of waypoints which form a path. This waypath can be rigid or splined. Each waypoint on the waypath can encode specific information, such as crouch here, speed up, slow down, or even jump to the next waypoint. To integrate this information into our path solver, consider the following algorithm.

Run a normal pathfind flood fill to generate sectors and portals. For each innate waypath, create a "dummy" sector (a sector without size or position), and add it to the system. For every waypoint in the waypath, find which pathfind sector the waypoint intersects. Create a two-way portal from the pathfind sector to the dummy waypath sector at the location of the waypoint. Add this new portal to both the pathfind sector and the dummy waypath sector.

During the run-time path solve, the algorithm's heuristic should bias toward these waypath sectors (i.e. multiply the cost of using a waypath sector by 0.75). This will cause AIs to "tend" to follow innate waypaths.

Given this system, to enable vehicle AIs to drive along the right side of the street, a level designer would simply draw a one-way, vehicle only, innate waypath along each side of the road.

	Innate waypaths can be used to keep vehicles driving along the right side of the street.

Follow the Leader

Currently, players are smarter then AIs: humans have the ability to combine abstract concepts and make leaps of logic. This reasoning ability allows players to perform actions that AIs cannot originate, but if we're lucky perhaps they can replicate. For instance, during a firefight on the second floor of a building, the player reasons he cannot win. In desperation he shoots out the window and, with a mighty leap, escapes onto the street. What does the AI do? Unless we give it an option, the AI will pathfind down the stairs, open the front door and look dumbly down the street, for the player is long gone. Wouldn't it be much more fun if the AI simply jumped out the window after the player?

There are many different ways to approach this problem, so let's choose the simplest. We know where the player jumped from and we know where the player landed. If both points are inside the pathfind data, why not add a temporary one-way "jump" portal between these two sectors? All we need to do is encode a little information about the jump such as orientation, velocity, and time. Depending on the physics system, this may be enough for the AI to replicate the player's mighty leap. We can even keep a FIFO "bucket" of these temporary portals so other AIs can follow.

______________________________________________________

Vehicles

join | contact us | advertise | write | my profile
news | features | companies | jobs | resumes | education | product guide | projects | store



Copyright © 2003 CMP Media LLC

privacy policy | terms of service