6.5 Waypoint Navigation

< Day Day Up >

6.5 Waypoint Navigation Pathfinding can be a very time-consuming and CPU-intensive operation. One way to reduce this problem is to precalculate paths whenever possible. Waypoint navigation reduces this problem by carefully placing nodes in the game environment and then using precalculated paths or inexpensive pathfinding methods to move between each node. Figure 6-19 illustrates how to place nodes on a simple map consisting of seven rooms. Figure 6-19. Placing nodes In Figure 6-19, you'll notice that every point on the map is in the line of sight of at least one node. Also, every node is in the line of sight of at least one other node. With a game environment constructed in this way, a game-controlled character always will be able to reach any position on the map using a simple line-of-sight algorithm. The game AI simply needs to know how the nodes connect to one another. Figure 6-20 illustrates how to label and connect each node on the map. Figure 6-20. Labeling nodes Using the node labels and links shown in Figure 6-20, we can now determine a path from any room to any other room. For example, moving from the room containing node A to the room containing node E entails moving through nodes ABCE. The path between nodes is calculated by a line-of-sight algorithm, or it can be a series of precalculated steps. Figure 6-21 shows how a computer-controlled character, indicated by the triangle, would calculate a path to the player-controlled character, indicated by the square. Figure 6-21. Building a path The computer-controlled character first calculates which node is nearest its current location and in its line of sight. In this case, that is node A. It then calculates which node is nearest the player's current location and in the player's line of sight. That is node E. The computer then plots a course from its current position to node A. Then it follows the node connections from node A to node E. In this case, that is A B C E. Once it reaches the end node, it can plot a line-of-sight path from the final node to the player. This seems simple enough, but how does the computer know which nodes to follow? In other words, how does the computer know that to get from node A to node E, it must first pass through nodes B and C? The answer lies in a simple table format for the data that enables us to quickly and easily determine the shortest path between any two nodes. Figure 6-22 shows our initial empty node connection table. Figure 6-22. Empty node table The purpose of the table is to establish the connections between the nodes. Filling in the table becomes a simple matter of determining the first node to visit when moving from any starting node to any ending node. The starting nodes are listed along the left side of the table, while the ending notes are shown across the top. We will determine the best path to follow by looking at the intersection on the table between the starting and ending nodes. You'll notice that the diagonal on the table contains dashes. These table elements don't need to be filled in because the starting and ending positions are equal. Take the upper-left table element, for example. Both the starting and ending nodes are A. You will never have to move from node A to node A, so that element is left blank. The next table element in the top row, however, shows a starting node of A and an ending node of B. We now look at Figure 6-21 to determine the first step to make when moving from node A to node B. In this case, the next move is to node B, so we fill in B on the second element of the top row. The next table element shows a starting node of A and an ending node of C. Again, Figure 6-21 shows us that the first step to take is to node B. When filling in the table we aren't concerned with determining the entire path between every two nodes. We only need to determine the first node to visit when moving from any node to any other node. Figure 6-23 shows the first table row completed. Figure 6-23. Filling in the node table Figure 6-23 shows us that when moving from node A to any other node, we must first visit node B. Examining Figure 6-21 confirms this fact. The only node connected to node A is node B, so we must always pass through node B when moving from node A to any other node. Simply knowing that we must visit node B when moving from node A to node E doesn't get us to the destination. We must finish filling in the table. Moving to the second row in the table, we see that moving from node B to node A requires a move to node A. Moving from node B to node C requires a move to C. We continue doing this until each element in the table is complete. Figure 6-24 shows the completed node connection table. Figure 6-24. Completed node table By using the completed table shown in Figure 6-24, we can determine the path to follow to get from any node to any other node. Figure 6-25 shows an example of a desired path. In this figure, a hypothetical computer-controlled character, indicated by the triangle, wants to build a path to the player, indicated by the square. Figure 6-25. Finding the path To build a path we simply need to refer to the completed node connection table shown in Figure 6-24. As shown in Figure 6-25, we want to build a path from node B to node G. We start by finding the intersection on the table between node B and node G. The table shows node C at the intersection. So, the first link to traverse when moving from node B to node G is B C. Once we arrive at node C, we refer to the table again to find the intersection between node C and the desired destination, node G. In the case, we find node E at the intersection. We then proceed to move from C E. We repeat this process until the destination is reached. Figure 6-26 shows the individual path segments that are followed when building a path from node B to node G. Figure 6-26. Finding the path As Figure 6-26 shows, the computer-controlled character needs to follow four path segments to reach its destination. Each method we discussed here has its advantages and disadvantages, and it's clear that no single method is best suited for all possible pathfinding problems. Another method we mentioned at the beginning of this chapter, the A* algorithm, is applicable to a wide range of pathfinding problems. The A* algorithm is an extremely popular pathfinding algorithm used in games, and we devote the entire next chapter to the method.

< Day Day Up >