ASIPathFinder documentation

Overview of the path finding process

Path finding is broadly broken down into three steps:

1) Path assessment

Path assessment involves finding a full route to the destination, if there is one. It works by performing an A* style search for a path, but in reverse - from the destination to the origin. It records the distance from the destination at each step - basically, how many moves it has taken travelling from the destination to arrive at that position. This data can then be used during path finding, which is the next step.

Generally, objects whose position can change are ignored during this step, as there’s no point avoiding an object that might not be there when we come within range of it.

Path assessment is handled by the ASISpatialPathAssessor class.

2) Path finding

Path finding is similar to path assesssment, but in reverse. That is, the path from the origin to the destination is calculated. It uses the data from the path assessment to work out the best position to move to next. At each position, it looks at the surrounding positions, and finds the one with the lowest distance from the destination. Because we already have a full path calculated to the destination, path finding can be split up easily to calculate only a partial path, which means objects can plan their route a little bit at a time, after the intial path assessment is complete.

Path assessment is handled by the ASISpaceTimePathFinder class.

Path finding also takes account of other objects that need to move. As units find a path, they reserve their position at a future point in time. When another object comes to perform path finding, it knows to avoid the positions other objects have already reserved for a particular point in time.

3) Movement

Actually moving the objects isn’t really part of path finding, however, it does impact on behaviour. The main thing about moving is that objects first check that they are able to move to the next position in their path. They may not be able to move if an object that wasn’t previously in the way has appeared since the object last performed path finding - for example, a newly created obstacle, or an ‘enemy’ unit that moves around but does not path find co-operatively with the object.

When an object encounters an unexpected obstacle, it simply stops to wait for the next path finding opportunity.

About the space time map

We have 3 units on a 5x5 map. Each has its destination marked with an ‘X’ in the same colour.

The green unit plans its route first. This is the route it will take, avoiding the grey obstacles.

Time step 1	Time step 2	Time step 3	Time step 4

Above are the reservations it will make on its space time map at each time step.

Time step 1	Time step 2	Time step 3	Time step 4

Now the second unit comes to perform path finding. Notice that it has to wait for the first object to move before going through the gap itself.

As we are only planning 4 time steps in advance, the second object hasn’t reached its destination. The next time it plans again (which will be once it has made 4 moves), it will move to its destination.

Logic overview

1) Telling units to perform path finding

In the main loop, we tell each team to perform movement and path finding.

For each team:

• If we’re on time step 0, tell each unit to perform path finding
• Otherwise, if any units have had their destination changed, tell them to perform path finding. They will perform path finding only for the rest of the moves we have in the time space map, and do a full path find once we reach time step 0 again.
• Tell each unit to move.

A team has an array of ASIUnits that need to path find. The order in which they path find is rotated. When we begin to path find, we clear the space time map, so that all time steps are empty. The first object to perform path finding can then reserve their full path. When the next object comes to path find, it will need to avoid the first unit’s path, and so on. Because we rotate the path finding order, if a unit is hemmed in, it will get a chance to take top priority for path finding when it’s turn comes around, and nearby units will have to move out of its way.

[diagram showing time steps after 1, 2, 3 paths have been calculated]

Other factors can affect the order in which units search for a path:

Firstly, if you have a large number of units bunched together, but only one of them wants to move, it doesn’t make sense for the static ones to plan first, since all they’re going to do is reserve their current position, which may block the object that does want to move from doing so until it gets a chance to plan first. So, we only allow an object to plan first if it’s actually going to move.

Secondly, if there are objects in the way of a unit once it has planned its path, it would make sense for us to force those to path find next, so they can move out of the way. To accomplish this, we recursively force units in the way of the top unit to perform path finding.

Finally, we loop through any remaining units, and tell them to path find. As each unit performs path finding, we add it to an array (planOrder). When we come to move units, we loop through this array in reverse order so that the first unit to plan always moves last. This should mean that by the time that first unit comes to move, any object that was in his way has already moved out of it, leaving him free to move.

2) Performing path finding

When a unit is asked to perform path finding, it will first perform path assessment, if it hasn’t already. It sets the origin of its path assessor to the destination, and the destination of its path assessor to its current position. Once path assessment starts, it will continue to consider positions until it has either reached its destination, or it has looked at MAX_NODES_TO_ASSESS_PER_STEP nodes. If the latter, path assesment is basically paused, and will be resumed next time around from where we left off.

Once path asessment has happened, we do different things depending on the outcome:

• If the path asssesor didn’t complete, we perform path finding, but will the goal of staying at our current position
• If the path assessor did complete, but didn’t find a route, we do the same. We will repeat this five times, and then start path assessment again on the sixth attempt. This is to prevent us wasting too much time assessing a path that may never be possible
• If the path assessor did complete, and it did find a path, perform path finding as normal.

3) Handling unanticipated collisions

As part of the final step, movement, units first need to double check that the position they are about to move to is not occupied. Though our path finding helps our units avoid collisions with friendly units before they happen, new obstacles can be introduced, or enemy units may be occuping that position.

ASIUnit’s canMove method returns true when the unit is able to move. It returns false if:

• There is an immovable obstacle in the way
• There is a unit in the way that has either already moved this frame, or will be unable to move this frame, because another object is in its way (we call canMove recursively to check).