7.5 Terrain Cost

< Day Day Up >

7.5 Terrain Cost As the previous example shows, path scoring already plays a major role in the A* algorithm. The standard A* algorithm in its most basic form simply determines path cost by the distance traveled. A longer path is considered to be more costly, and hence, less desirable. We often think of a good pathfinding algorithm as one that finds the shortest possible path. However, sometimes other considerations exist. For example, the shortest path isn't always the fastest path. A game environment can include many types of terrain, all of which can affect the game characters differently. A long walk along a road might be faster than a shorter walk through a swamp. This is where terrain cost comes into play. The previous example shows how we calculate each node's cost by adding its distance from the initial location to the heuristic value, which is the estimated distance to the destination. It might not have been obvious, but the previous example basically did calculate terrain cost. It just wasn't very noticeable because all the terrain was the same. Each step the game character took added a value of 1 to the path cost. Basically, every node had the same cost. However, there's no reason why we can't assign different cost values to different nodes. It requires just a minor change to the cost equation. We can update the cost equation by factoring in the terrain cost. This is shown in Figure 7-19. Figure 7-19. Scoring with terrain cost This results in paths that are longer, but that involve easier terrain. In an actual game this can result in a game character getting from point A to point B in a shorter amount of time, even if the actual path is longer. For example, Figure 7-20 shows several hypothetical types of terrain. Figure 7-20. Types of terrain The previous example essentially had only open terrain. The cost of moving from one node to another was always 1. As Figure 7-20 shows, we will now introduce two new types of terrain. The first new terrain type is grassland, which has a cost of 3. The second new type of terrain is swampland, which has a cost of 5. In this case, cost ultimately refers to the amount of time it takes to traverse the node. For example, if it takes a game character one second to walk across a node of open terrain, it will take three seconds to walk across a node of grassland, and five seconds to walk across a node of swampland. The actual physical distances might be equal, but the time it takes to traverse them is different. The A* algorithm always searches for the lowest-cost path. If the cost of every node is the same, the result will be the shortest path. However, if we vary the cost of the nodes, the lowest-cost path might no longer be the shortest path. If we equate cost with time, A* will find the fastest path rather than the shortest path. Figure 7-21 shows the same tile layout as the previous example, but with the introduction of the terrain elements shown in Figure 7-22. Figure 7-21. Adding different terrain elements Figure 7-22. Original path over terrain elements As you can see in Figure 7-21, the obstacles and game characters are in the same locations as they were in the previous example. The only difference now is the addition of terrain cost. We are no longer looking for the shortest physical path. We now want the fastest path. We are going to assume that grassland takes three times longer to traverse than open terrain does, and that swampland takes five times longer. The question is, how will the added terrain cost affect the path? Figure 7-22 shows the path derived from the previous example. As Figure 7-22 shows, the shortest path was found. However, you'll notice that the path is now over several high-cost terrain elements. There is no question that it's the shortest path, but is there a quicker path? We determine this by using the same A* algorithm we stepped through in the first example, but this time we add the terrain cost to the total cost of each node. Figure 7-23 shows the results of following the entire algorithm to its conclusion. Figure 7-23. Calculating the lowest-cost path As you can see in Figure 7-23, this is very similar to how we calculated the path in the previous example. We use the same branching technique where we examine the adjacent tiles of the current tile. We then use the same open and closed list to track which tiles need to be examined and which are no longer of interest. The main difference is the s value, which is the cost of moving to any given node from the starting node. We simply used a value of 1 for every node in the previous example. We are now adding the terrain cost to the s value. The resulting lowest-cost path is shown in Figure 7-24. Figure 7-24. The lowest-cost path As Figure 7-24 shows, the A* algorithm has worked its way around the higher-cost terrain elements. We no longer have the shortest physical path, but we can be assured that no quicker path exists. Other paths might exist that are physically shorter or longer and that would take the same amount of time to traverse, but none would be quicker. Terrain cost also can be useful when applying the A* algorithm to a continuous environment. The previous examples showed how you can apply the A* algorithm to a tiled environment where all nodes are equidistant. However, equidistant nodes are not a requirement of the A* algorithm. Figure 7-25 shows how nodes could be placed in a continuous environment. Figure 7-25. Continuous environment node placement In Figure 7-25, you'll notice that the distance between the nodes varies. This means that in a continuous environment it will take a longer period of time to traverse the distances between the nodes that are farther apart. This, of course, assumes an equivalent terrain between nodes. However, in this case, the cost of moving between nodes would vary even though the terrain is equivalent. The cost would be equal to the distance between nodes. We've discussed several different types of costs associated with moving between nodes. Although we tend to think of cost as being either time or distance, other possibilities exist, such as money, fuel, or other types of resources.

< Day Day Up >