Samstag, 27. März 2010

Pathfinding - Navigation

So finally we with our distance matrix defined and initialized we can go ahead and compute our shortest paths. The most popular approach to determine the shortest paths to all possible targets from a single source is probably the A* algorithm.

However, we will do something completely different: In order to prevent the multiple application of A* for different objects at runtime we are going to compute all shortest paths in a preprocessing. This approach is only possible due to the fact that we will never have to take into account any waypoints or paths other than the ones among our 225 squares.

The Floyd/Warshall algorithm computes all shortest paths in a graph in O(n³). It belongs to the area of dynamic programming where solutions to large problems are found by computing the solution for smaller subproblems first and then storing this information and reusing it to find the solution for the large problem.

Given a pair of nodes "from" and "to" and assuming that we already know for all other nodes "x" the shortest paths from->x and x->to, it is clear that the shortest path from->to uses the node x as an intermediate, where the sum of the lengths of from->x and x->to is minimal.

Note: As we are not only interested in the lengths of our shortest paths but also in the information where we have to go to follow a shortest path, we need something else than the distance matrix to store this information. A naive idea would be to somehow store all paths for all pairs of nodes, but indeed it will be sufficient to store the information, given a node "from" and a node "to" where we have to go next on a shortest path. We will then simply go to this next node and look up which node is our next stop from this node to the node "to" until we reach our destination. We thus introduce a two-dimensional array which will - for the time being - store the information about the intermediate node "x" from our desciption above.



Running Floyd/Warshall for our 225-nodes-graph on an Xbox 360 takes only a couple of seconds, which is ok to do during the loading of a map. If we consider this too long we can think about storing the shortest path information later. The good thing is that we will never have to worry about runtime performance.

Now assume that we have 4 neigbor nodes (a,b,c,d) in a row such that neither of them contains a wall. Then the shortest path from a to d obviously has length 2+2+2 = 6.
And we will find this information in distance[a,d].

Due to the way (Floyd/Warshall) we computed the intermediates however, we do not necessarily have intermediate[a,d] = b but possibly intermediate[a,d] = c. This is due to the fact that the sums a->b + b->d and a->c + c->d are the same and so it depends on which intermediate was looked at first.

In order to follow a path step by step (and not driving to an intermediate that lies behind a corner, i.e., behind a wall) we want to compute the direct successor nodes. For this task we simply look up the intermediate of from->to. If there is no intermediate, then the nodes are neighbors and we have found the direct successor. Otherwise we look up the intermediate of from->intermediate, i.e. we proceed with the "first half" of our path recursively.



We're almost there!! In the example of our last post we have now computed a shortest path that uses only orthogonal and diagonal ways between neighbor squares. Following this path with our tank is already a nice thing, but to finally avoid the zigzaging that may occur here, we have to apply one last method which is called "string-pulling": Assume that the white path is a string. If we take the source and destination of the path and pull we will get a path that stretches around corners and avoids zigzaging.



The straightforward way to compute string pulling is to go through a path and check, whether - given a present node "from" and a destination "to" - we have to stick with our direct successor x or if it is possible to go to the successor of x directly. This is the case if and only if there is a line of sight between from and the successor of x. We follow the path as long as possible, i.e. we compute the last successor y such that there is a line of sight between from and y.

Remark: To answer whether we have a line of sight, we avoid high-cost computations like collision detection. Instead, we follow the vector between to squares and check whether the squares in between contains walls. (The step-distance 5 that is used in the algorithm below is about a third of square length.)



It remains to tell our PacifistAI to use the information we have computed so far. Given our current square (from) and some destination square (to), we can simply overwrite the player's controls-vector with a vector that points from our present position to the center of the square shortestPathsIntermediate[from,to].



If we subsitute the content of our method TestAI() by something as simple as...

curPlayer.chassis.thumbstick = Steer(enemy.chassis.positionAsSquare);

...we obtain a hunting behavior (on any user-generated map) that we can finally enjoy as the fruits of our work:

Keine Kommentare:

Kommentar veröffentlichen