Delphi Graphics and Game Programming Exposed! with DirectX For versions 5.0-7.0:Artificial Intelligence Techniques                       Search Tips   Advanced Search        Title Author Publisher ISBN    Please Select ----------- Artificial Intel Business & Mgmt Components Content Mgmt Certification Databases Enterprise Mgmt Fun/Games Groupware Hardware IBM Redbooks Intranet Dev Middleware Multimedia Networks OS Productivity Apps Programming Langs Security Soft Engineering UI Web Services Webmaster Y2K ----------- New Arrivals









Delphi Graphics and Game Programming Exposed with DirectX 7.0

by John Ayres

Wordware Publishing, Inc.

ISBN: 1556226373   Pub Date: 12/01/99














Search this book:
 



Previous Table of Contents Next As you can see from this simplistic example, the change in behavior of the enemy sprite is subtle, but you should be able to tell a definite personality, especially between the Aggressive and Defensive postures. Indeed, if we changed a sprite’s personality based on game state (i.e., going from Aggressive to Defensive when hit points went below 30%), the sprite would seem a little more dynamic. We could even change the distribution based on the success of a particular state within a personality during the game. For example, if the game timed how long it took to kill the player during each state and found that a particular state was more effective, it could modify the distribution so that that state was chosen more often. This would make the game grow with the player; the sprites would appear to “learn,” and the game would become more challenging. Path Finding Most games feature some form of entity or sprite that must move from one position in the game world to another. Usually, this is pretty simple, as we can determine an appropriate x and y velocity that will move the sprite in the direction of its goal and sit back until it gets there. This will work fine for game worlds that are flat and don’t feature any obstacles that would hinder movement. Unfortunately, most game worlds tend to be a bit more complex, with several immobile or impassible objects. The presence of these objects negates the possibility of game entities always moving in straight lines to get from their origin to their destination, posing a problem that has been researched heavily over the years by both the academic world and the gaming industry alike. When a game entity encounters an object that hinders its movement, it must find another direction of movement leading around the obstacle and toward the final destination. This is known as path finding. Technically, path finding describes algorithms for determining the shortest, most direct path from a starting position to an ending position, avoiding all impassible obstacles. path finding: Algorithmic techniques for determining the shortest, most direct path from a starting position to an ending position based on terrain and obstacles in the game world. There are numerous applications for such techniques. Real–time strategy games such as Age of Empires and WarCraft make heavy use of path finding algorithms. Indeed, any game that features entities moving through a world filled with impassible obstacles needs to implement some form of path finding. Path finding algorithms can be applied to real–world problems as well. We’ll focus our discussion on path finding as it applies to 2–D game worlds, and we’ll examine one well–known algorithm that produces acceptable results. Algorithms The subject of finding a particular path over a specific terrain and algorithms for accomplishing this task have been researched almost as extensively as methods for producing graphical output. Several books have been published that cover this subject to varying degrees of depth. Many of these algorithms, while accurate, tend to be too slow for implementation in a game. However, three algorithms are well documented and well known in the game industry, and tend to serve as the basis from which most game implementations of path finding algorithms are drawn. These are known as breadth first search, depth first search, and A* (pronounced “A–Star”). Breadth First Search The breadth first search algorithm is very exhaustive, and while it can eventually find a very accurate, short path, it typically takes way too long for most games. It searches for the shortest path by choosing the next node in a particular direction and determining its distance from the destination. It performs this for all available directions, then it moves to the node closest to the destination and performs these calculations again. However, if two or more nodes are the same distance from the destination, it recursively performs these calculations for each of these nodes. Essentially, this algorithm explores all possible paths from the starting point to the destination, as long as those paths lead toward the destination. This can result in an exponentially increasing number of calculations depending on the size of the map and the position of obstacles. Calculation times for this algorithm are typically measured in seconds. While this may be completely appropriate for real–world problems, it is way too slow for a game application, which needs to calculate paths in milliseconds, if not faster. Depth First Search By contrast, the depth first search simply chooses a direction toward the destination and begins moving along nodes in that direction until it reaches the destination. If it encounters an obstacle, it backs up one node and tries again in a different direction. While this algorithm can eventually find some path to the destination, it typically will not be the shortest or the most direct route. However, also unlike breadth first search techniques, path calculation times are much, much shorter. While this will find some type of path in a short amount of time, it will usually result in a path that makes game entities wander about almost aimlessly, and certainly in no logical or intelligent manner. A* Perhaps the most widely documented solution for path finding problems is the A* algorithm. A* combines the best of both breadth first search and depth first search to determine the shortest path in a relatively minimal amount of time. Like the depth first search, it chooses a direction toward the destination, and begins moving along nodes in that direction. Like the breadth first search algorithm, it checks the distance of the next nodes in several directions to determine which is closest to the destination. It then moves to this next node and starts the calculations again. The result is a single path for which several directions were considered at each node. This typically produces a fairly intelligent looking path within an acceptable amount of time. Basic Implementation In our example, we’ll take a fairly typical approach and define a two–dimen– sional game world composed of square tiles. We’ll need to define a starting point and an ending point, and populate this map with several impassible obstacles, like so: Figure 12–5:  The game world Additionally, we’ll need to set up a list that will hold information for the nodes we have selected on our path. We’ll also need an array the size of the game world to mark nodes that have already been explored. We’ll examine how these two requirements are utilized below. We begin by determining the direction of the goal relative to our starting point. We’ll use this to determine which nodes we should look at next. Based on this direction, we’ll examine three nodes—the next node in the direction of the goal and the two nodes to either side of it. In this example, our goal is directly east of the starting point, so we’ll examine the northeast, east, and southeast nodes relative to our starting point: Figure 12–6:  Examining nodes Now, for each of these nodes being examined, we need to determine their distance from the destination. If you remember your algebra, the distance formula is: Distance := Sqrt(Sqr(X2 X1) + Sqr(Y2 Y1)); Tip: The Sqrt and Sqr functions are very slow. We could simply use multiplication in the case of the Sqr function, and perhaps utilize a lookup table for the Sqrt function in order to optimize this equation. Using this equation, we find that the node directly to the east is the closest to the destination. We’ll add this new node to our list of nodes along the path, as well as mark this new node as visited in our array of visited nodes (we also need to add the starting node to the list as well as mark it as visited before we start searching for a path). We then move to this new node, and begin the process again. Note: The phrase “moving to the new node” indicates that we are simply tracking the current node we are processing in our algorithm. The actual movement of the game entity does not take place until the entire path is determined; it does not move in real time. Previous Table of Contents Next Products |  Contact Us |  About Us |  Privacy  |  Ad Info  |  Home Use of this site is subject to certain Terms & Conditions, Copyright © 1996-2000 EarthWeb Inc. All rights reserved. Reproduction whole or in part in any form or medium without express written permission of EarthWeb is prohibited. Read EarthWeb's privacy statement.