L'uso dell'intelligenza artificiale nei videogame

[Dragonball (POL)]

Artificial Intelligence

Overview
Some of my earliest memories are of my dad bouncing me on his knee, playing computer games on our 8088. I was fascinated with computers, despite the fact that we only had two games for the machine: a game where a donkey ran down the road avoiding cars, and an app that used the PC speaker to crudely simulate a piano. One of my first phrases was "Dunkee n musik," a jumbled group of syllables I would yelp when I wanted to play the games.

Right around then was when I saw my first AI application. The title escapes me (I believe it may have been just Animal), but the premise was simple enough. The object of the game was for the computer to guess an animal you were thinking about. It would ask a series of yes/no questions that would narrow down the possible choices (examples would be "does your animal fly?" or "does your animal have four legs?"), and when it was sure, it would tell you what it thought your animal was. The neat thing was, if it didn't guess your animal, it would ask you for a question that differentiated the two animals, something your animal had that the other didn't. From then on, the program would be able to guess your animal! It could learn!

This impressed my young mind to no end. After some formal training in programming, I've come to accept that it's a fairly trivial program: The application keeps an internal binary tree with a question at each branch and an animal at each leaf. It descends down the tree asking the question at each branch and taking the appropriate direction. If it reaches a leaf and the animal stored there isn't yours, it creates a new branch, adds your question, and puts your animal and the animal previously in the leaf in two new leaves.

How the program worked, however, really isn't that important. The trick is, it seemed intelligent to me. Game programmers need to aim for this. While academia argues for the next 50 years over whether or not human-level intelligence is possible with computers, game developers need only be concerned with tricking humans into thinking what they're playing against is intelligent. And luckily (for both developers and academia), humans aren't that smart.

This is, of course, not as easy as it sounds. Video games are rife with pretty stupid computer opponents. Early first-person shooters had enemies that walked towards the player in a zigzag pattern, never walking directly towards their target, shooting intermittently. Bad guys in other games would sometimes walk into a corner looking for you, determined that they would eventually find you even though you were several rooms away. Fighting games are even worse. The AI governing computer opponents can become extremely repetitive (so that every time you jump towards the opponent, they execute the same move). I can't promise to teach you everything you need to know to make the next Reaper Bot; that would be the topic of an entire book all its own. By the end of this chapter, however, you should be able to write an AI that can at least challenge you and maybe even surprise you!

Starting Point
Most AI problems that programmers face fall into three groups. At the lowest level is the problem of physical movement-how to move the unit, how to turn, how to walk, etc. This group is sometimes called locomotion, or motor skills. Moving up one level is a higher-level view of unit movement, where the unit has to decide how to get from point A to point B, avoiding obstacles and/or other units. This group is called steering, or task generation. Finally, at the highest level, the meatiest part of AI, is the actual thinking. Any cockroach can turn in a circle and do its best to avoid basic obstacles (like a human's foot). That does not make the cockroach intelligent. The third and highest stage is where the unit decides what to do and uses its ability to move around and plan directions to carry out its wishes. This highest level is called motivation, or action steering.

Locomotion
Locomotion, depending on how you look at it, is either trivial or trivially complex. An animation-based system can handle locomotion pretty easily, move forward one unit, and use the next frame of animation in the walk cycle. Every game on the market uses something similar to this to handle AI locomotion.

However, that isn't the whole story. When you walk up stairs, you need a stair walking animation; when you descend down a hill, you naturally lean back to retain your balance. The angle you lean back is dependent on the angle of the hill. The amount you dig your feet into the ice is dependent on how slippery the ice is and how sure your footing needs to be before you proceed. Animation systems robust enough to handle cases like this require a lot of special casing and scripting; most animation systems use the same walk animation for all cases. I always found it kind of disappointing when the guards in the surface level of Goldeneye could simply walk up 8-foot tall, 70 degree banks of snow.

A branch of control theory attempts to solve this with physical controllers. You can actually teach an AI how to stand and tell it how to retain its balance, how to walk around, jump, anything. This gives the AI incredible control, as the algorithms can handle any realistic terrain, any conditions. Many people agree that the future of locomotion in games is physical controllers.

However, physical controllers aren't easy. At all. For these purposes, it's total overkill. As Moore's law inevitably marches forward, there will eventually be enough processing power to devote the cycles to letting each creature figure out how to run towards its target. When this happens, games will be one huge step closer to looking like real life.



Steering-Basic Algorithms
Even games with little or no AI at all need to implement some form of steering. Steering allows entities to navigate around the world they exist in. Without it, enemies would just sit there with a rather blank look in their eyes. There are a slew of extremely basic steering algorithms that I'll touch upon, and a couple of slightly more advanced ones that I'll dig into a little deeper.

Chasing
The first AI that most people implement is the ruthless, unthinking, unrelenting Terminator AI. The creature never thinks about rest, about getting health or ammo, about attacking other targets, or even walking around obstacles: It just picks a target and moves towards it each frame relentlessly. The code to handle this sort of AI is trivial. Each frame, the creature takes the position of its target, generates a vector to it, and moves along the vector a fixed amount (the amount is the speed of the creature). Pseudocode to handle this type of AI is in Listing 6.1.

Listing 6.1: The Terminator manifested


void cCreature::Chase( cObject* target )
{
// Find the locations of the creature and its target.
point3 creatureLoc = m_loc;
point3 targetLoc = target->GetLoc();

// Generate a direction vector between the objects
point3 direction = targetLoc - creatureLoc;

// Normalize the direction (make it unit-length)
direction.Normalize();

// move our object along the direction vector some fixed amount
m_loc += direction * m_speed;
}




Evading
The inverse of a chasing algorithm is what I could probably get away with calling rabbit AI, but I'll leave it at evading. Each frame, you move directly away from a target as fast as you can (although in this case the target would most likely be a predator).

Listing 6.2: John Connor, perhaps?


void cCreature::Evade( cObject* target )
{
// Find the locations of the creature and its target.
point3 creatureLoc = m_loc;
point3 targetLoc = target->GetLoc();

// Generate a direction vector between the objects
point3 direction = targetLoc - creatureLoc;

// Normalize the direction (make it unit-length)
direction.Normalize();

// move our object away from the target by multiplying
// by a negative speed
m_loc += direction * -m_speed;
}




Pattern-based AI
Another fairly simple AI algorithm I'm going to discuss is pattern-based AI. If you have ever played the classic Space Invaders, you're familiar with this AI algorithm. Aliens take turns dive-bombing the player, with every type of alien attacking in one uniform way. The way it attacks is called a pattern. At each point in time, each creature in the simulation is following some sort of pattern.

The motivation engine (in this case, usually a random number generator) decides from a fixed set of patterns to perform. Each pattern encodes a series of movements to be carried out each frame. Following the Space Invaders theme, examples of pattern-based AI would be moving back and forth, diving, and diving while shooting. Anyone who has played the game has noticed that each unit type dives towards the player the same way, oblivious to where the player is. When the baddies aren't diving, they all slide back and forth in the same exact way. They're all following the same set of patterns.

The algorithm to run a pattern-based AI creature is straightforward. I'll define a pattern to be an array of points that define direction vectors for each frame of the pattern. Since the arrays can be of any length, I also keep track of the length of the array. Then during the AI simulation step the creature moves itself by the amount in the current index of the array. When it reaches the end of an array, it randomly selects a new pattern. Let's examine some pseudocode to handle pattern-based AI.

Listing 6.3: Pattern-based AI


struct sPattern
{
int patternLength;
point3 *pattern; // array of length patternLength
};

sPattern g_patterns[ NUM_PATTERNS ];

void cCreature::FollowPattern()
{
// pattFrame is the current frame of the pattern
// pattNum is the current pattern we're using.

if( pattFrame >= g_patterns[ pattNum ].patternLength )
{
// new pattern
pattNum = rand()%NUM_PATTERNS;
pattFrame = 0;
}

// follow our current pattern.
m_loc += g_patterns[pattNum].pattern[pattFrame++];
}




Pattern-based AI can be specialized into what is known as scripted AI. When a certain state is reached, the motivation engine can run a certain scripted steering pattern. For example, an important state would be your player entering a room with a bad guy in it. This could cause the creature to follow a specialized animation just for that one game situation. The bad guy could run and trip an alarm, dive out of bed towards his bludgeoning weapon of choice, or anything else you can dream up.

[Rick Hunter]

c'è una traduzione in italiano?

[Dragonball (POL)]

Steering—Advanced Algorithms
In case you haven't figured it out yet, the basic steering algorithms provided so far are terrible! They merely provide the creature with an ability to move. Moving in a pattern, moving directly towards an opponent, or fleeing directly away from it is only slightly more believable than picking a random direction to move every frame! No one will ever mistake your basic cretins for intelligent creatures. Real creatures don't follow patterns. Moving directly towards or directly away from you makes them an easy target. A prime example of how this would fail is illustrated in Figure 6.1.

Figure 6.1: Chasing directly towards a target wouldn't be too smart in many cases
How can you make the creatures appear more intelligent? It would be cool to give them the ability to navigate through an environment, avoiding obstacles. If the top-level motivation AI decides that it needs health or ammo, or needs to head to a certain location, the task of getting there intelligently should be handed off to the steering engine. Two general algorithms for achieving this are what I'll discuss next.

Potential Functions
Luckily for game programmers, a lot of the hard problems in steering and autonomous navigation for AI creatures have already been solved by the robotics community. Getting an autonomous unit, like a Mars rover, to plan a path and execute it in a foreign environment is a problem that countless researchers and academics have spent years trying to solve. One of the ways they have come up with to let a robot (or a creature in the game) wander through an unknown scene is to use what are called potential functions.

Imagine a scene filled with obstacles, say tree trunks in a forest. There is a path from the start to the goal and no tricky situations (like a U-shaped wall of trees, which ends up being a real problem as you'll see in a moment). The unit should be able to reach the goal; all it needs to do is not run into any trees. Anytime it gets close to a tree, logically, it should adjust its direction vector so it moves away from the tree. The amount it wants to move away from the tree should be a function based on the distance from the obstacle; that is, if it is right next to the obstacle, it will want to avoid it more than if it is half a mile away from it. Figure 6.2 shows an example of this. It will obviously want to try to avoid obstacle 1 more than it tries to avoid obstacle 2, since obstacle 2 is so much farther away.

Figure 6.2: Some obstacles should be avoided more than others
This statement can be turned into an equation. Initially the direction is the normalized vector leading to the goal (or the goal location minus the current location). Then, for each obstacle, you find the normalized vector that moves directly away from it. Then multiply it by a constant, and divide it by the squared distance from the obstacle. When finished, you have a vector that the object should use as a direction vector (it should be normalized, however).

Generally the obstacles (and the object navigating) have some radius associated with them, so the last term in the equation can be adjusted to use the distance between the spheres, instead of the distance between the spheres' centers.

The Good
Potential functions work great in sparse areas with physical obstacles, particularly outdoor scenes. You can reach a goal on the other side of a map avoiding trees, rocks, and houses beautifully and with little computational effort. A quick and easy optimization is to only consider the objects that are within some reasonable distance from you, say 50 feet; that way you don't need to test against every object in the world (which could have hundreds or thousands of objects in it).

One great advantage of potential functions is that the obstacles themselves can move around. You can use potential functions to model the movement of a squad of units across a map for example. They can avoid obstacles in the scene (using potential functions or more complex path finding algorithms like A*) and then avoid each other using potential functions.

The Bad
Potential functions are not a silver bullet for all problems, however. As intelligent as units can look being autonomously navigated with this method, they're still incredibly stupid. Mathematically, think of the potential functions as descending into a valley towards a goal, with the obstacles appearing as hills that roll past. If there is a miniature valley that is descended into, there is no way of getting out of it, since the only way to move is downward. This miniature valley can appear all over the place; if two obstacles are too close to each other, you won't be able to pass between them, and if obstacles are organized to form a barrier, like a wall or specifically a U-shaped obstacle, you're totally screwed. Figure 6.3 gives an example of this.

Figure 6.3: Potential functions alone cannot get to the goal in this configuration

[Dragonball (POL)]

c'è una traduzione in italiano?

Eh mi spiace,ma per questi argomenti solo in inglese.

[Dragonball (POL)]

Application: potentialFunc
To help explain the ideas described above, I wrote a small test app to show off potential functions. You can use the z, x, and c keys to make large, medium, and small obstacles under the mouse, respectively. The Space key releases a creature under the mouse that heads to the goal, which appears as a green circle. Since the GDI is so slow, I decided against clearing the window every frame, so the creatures leave trails as they move around. For most cases, the creatures (more than one can be created at once) reach their goal well, as evidenced in the following picture:

Figure 6.4: Potential functions doing their job
However, they don't work all the time, as evidenced by this picture:

Figure 6.5: Potential functions failing spectacularly
You'll notice that inside the code I sum the potential forces for the objects and move a bit ten times each frame. If I only moved once, I would need to move a fairly large amount to have the speed of the creature be anything interesting. However, when the deltas are that large, the result is some ugly numerical stability problems (characterized by a jittering when the creature gets very close to an obstacle). Sampling multiple times each frame fixes the problem.

The GDI isn't useful for writing 3D games, so I'm covering it very minimally in this book. However, for doing something like a potential function application it turns out to be quite useful. While I'm providing no explanations of how GDI works, armed with this code and the Win32 SDK documentation, figuring it out on your own won't be terribly difficult.

The code uses two main classes, cCreature (an entity that tries to reach the goal) and cObstacle (something obstructing the path to the goal). The code keeps vectors of all of the creatures and objects in the scene. Each frame, each member of the creature vector gets processed, during which it examines the list of obstacles. A nice extension to the program would be for creatures to also avoid other creatures; currently they blindly run all over each other.

The code for this application is mostly GUI and drawing code, and the important function is cCreature::Process. It is called every frame, and it performs the potential function equation listed above to find the new location. After each creature gets processed, the entire scene gets drawn. Rather than list all of the code for the program, I'll just give this one function.

Listing 6.4: The main function of note, cCreature::Process


bool cCreature::Process()
{
point3 goalVec = g_goalLoc - m_loc;

if( goalVec.Length() < g_creatureSpeed )
return false; // we reached the goal, destroy ourselves

point3 dirVec = goalVec / goalVec.Length();

float k = .1f;

// for each obstacle
for( int i=0; i<g_obstacles.size(); i++ )
{

// find the vector between the creature and the obstacle
point3 obstacleVec = m_loc - g_obstacles[i].m_loc;

// compute the length, subtracting object radii to find
// the distance between the spheres,
// not the sphere centers
float dist = obstacleVec.Length()
g_obstacles[i].m_rad - m_rad;

// this is the vector pointing away from the obstacle
obstacleVec.Normalize();

dirVec += obstacleVec*(k/ (dist * dist) );
}
dirVec.Normalize();

m_loc += g_creatureSpeed * dirVec;
return true; // we should continue processing
}




Path Following
Path following is the process of making an agent look intelligent by having it proceed to its destination using a logical path. The term "path following" is really only half of the picture. Following a path once you're given it is fairly easy. The tricky part is generating a logical path to a target. This is called path planning.

Before it is possible to create a logical path, it must be defined. For example, if a creature's desired destination (handed to it from the motivation code) is on the other side of a steep ravine, a logical path would probably be to walk to the nearest bridge, cross the ravine, then walk to the target. If there were a steep mountain separating it from its target, the most logical path would be to walk around the mountain, instead of whipping out climbing gear.

A slightly more precise definition of a logical path is the path of least resistance. Resistance can be defined as one of a million possible things, from a lava pit to a strong enemy to a brick wall. In an example of a world with no environmental hazards, enemies, cliffs, or whatnot, the path of least resistance is the shortest one, as shown in Figure 6.6.

Figure 6.6: Choosing paths based on length alone
Other worlds are not so constant. Resistance factors can be worked into algorithms to account for something like a room that has the chance of being filled with lava (like the main area of DM2 in Quake). Even if traveling through the lava room is the shortest of all possible paths using sheer distance, the most logical path is to avoid the lava room if it made sense. Luckily, once the path finding algorithm is set up, modifying it to support other kinds of cost besides distance is a fairly trivial task. If other factors are taken into account, the chosen path may be different. See Figure 6.7.

Figure 6.7: Choosing paths based on other criterion

[Dragonball (POL)]

Groundwork
While there are algorithms for path planning in just about every sort of environment, I'm going to focus on path planning in networked convex polyhedral cells. Path planning for something like a 2D map (like those seen in Starcraft) is better planned with algorithms like A*.

A convex cell will be defined as a region of passable space that a creature can wander through, such as a room or hallway. Convex polyhedrons follow the same rules for convexity as the polygons. For a polygon (2D) or a polyhedron (3D) to be convex, any ray that is traced between any two points in the cell cannot leave the cell. Intuitively, the cell cannot have any dents or depressions in it; there isn't any part of the cell that sticks inward. Concavity is a very important trait for what is being done here. At any point inside the polyhedron, exiting the polyhedron at any location is possible and there is no need to worry about bumping into walls. Terminator logic can be used from before until the edge of the polyhedron is reached.

The polyhedrons, when all laid out, become the world. They do not intersect with each other. They meet up such that there is exactly one convex polygon joining any two cells. This invisible boundary polygon is a special type of polygon called a portal. Portals are the doorways connecting rooms and are passable regions themselves. If you enter and exit cells from portals, and you know a cell is convex, then you also know that any ray traveled between two portals will not be obstructed by the walls of the cell (although it may run against a wall). Until objects are introduced into the world, if the paths are followed exactly, there is no need to perform collision tests.

Figure 6.8: Cells and the portals connecting them
I'll touch upon this spatial definition later in the book when I discuss hidden surface removal algorithms; portal rendering uses this same paradigm to accelerate hidden surface removal tasks.

The big question that remains is how do you move around this map? To accomplish finding the shortest path between two arbitrary locations on the map (the location of the creature and a location the user chooses), I'm going to build a directed, weighted graph and use Dijkstra's algorithm to find the shortest edge traversal of the graph.

If that last sentence didn't make a whole lot of sense, don't worry, just keep reading!

Graph Theory
The need to find the shortest path in graphs shows up everywhere in computer programming. Graphs can be used to solve a large variety of problems, from finding a good path to send packets through on a network of computers, to planning airline trips, to generating door-to-door directions using map software.

A weighted, directed graph is a set of nodes connected to each other by a set of edges. Nodes contain locations, states you would like to reach, machines, anything of interest. Edges are bridges from one node to another. (The two nodes being connected can be the same node, although for these purposes that isn't terribly useful.) Each edge has a value that describes the cost to travel across the edge, and is unidirectional. To travel from one node to another and back, two edges are needed: one to take you from the first node to the second, and one that goes from the second node to the first.

Dijkstra's algorithm allows you to take a graph with positive weights on each edge and a starting location and find the shortest path to all of the other nodes (if they are reachable at all). In this algorithm each node has two pieces of data associated with it: a "parent" node and a "best cost" value. Initially, all of the parent values for all of the nodes are set to invalid values, and the best cost values are set to infinity. The start node's best cost is set to zero, and all of the nodes are put into a priority queue that always removes the element with the lowest cost. Figure 6.9 shows the initial case.

Figure 6.9: Our initial case for the shortest path computation
Note Notice that the example graphs I'm using seem to have bidirectional edges (edges with arrows on both sides). These are just meant as shorthand for two unidirectional edges with the same cost in both directions. In the successive images, gray circles are visited nodes and dashed lines are parent links.


Iteratively remove the node with the lowest best cost from the queue. Then look at each of its edges. If the current best cost for the destination node for any of the edges is greater than the current node's cost plus the edges' cost, then there is a better path to the destination node. Then update the cost of the destination node and the parent node information, pointing them to the current node. Pseudocode for the algorithm appears in Listing 6.5.

Listing 6.5: Pseudocode for Dijkstra's algorithm


struct node
vector< edge > edges
node parent
real cost

struct edge
node dest
real cost

while( priority_queue is not empty )
node curr = priority_queue.pop
for( all edges leaving curr )
if( edge.dest.cost > curr.cost + edge.cost )
edge.dest.cost = curr.cost + edge.cost
edge.dest.parent = curr




Let me step through the algorithm so I can show you what happens. In the first iteration, I take the starting node off the priority queue (since its best cost is zero and the rest are all set to infinity). All of the destination nodes are currently at infinity, so they get updated, as shown in Figure 6.10.

Figure 6.10: Aftermath of the first step of Dijkstra's algorithm
Then it all has to be done again. The new node you pull off the priority queue is the top left node, with a best cost of 8. It updates the top right node and the center node, as shown in Figure 6.11.

Figure 6.11: Step 2
The next node to come off the queue is the bottom right one, with a value of 10. Its only destination node, the top right one, already has a best cost of 13, which is less than 15 (10 + the cost of the edge −15). Thus, the top right node doesn't get updated, as shown in Figure 6.12.

Figure 6.12: Step 3
Next is the top right node. It updates the center node, giving it a new best cost of 14, producing Figure 6.13.

Figure 6.13: Step 4
Finally, the center node is visited. It doesn't update anything. This empties the priority queue, giving the final graph, which appears in Figure 6.14.

Figure 6.14: The graph with the final parent-pointers and costs


Using Graphs to Find Shortest Paths
Now, armed with Dijkstra's algorithm, you can take a point and find the shortest path and shortest distance to all other visitable nodes on the graph. But one question remains: How is the graph to traverse generated? As it turns out, this is a simple, automatic process, thanks to the spatial data structure.

First, the kind of behavior that you wish the creature to have needs to be established. When a creature's target exists in the same convex cell the creature is in, the path is simple: Go directly towards the object using something like the Terminator AI I discussed at the beginning of the chapter. There is no need to worry about colliding with walls since the definition of convexity assures that it is possible to just march directly towards the target.

Warning I'm ignoring the fact that the objects take up a certain amount of space, so the total set of the creature's visitable points is slightly smaller than the total set of points in the convex cell. For the purposes of what I'm doing here, this is a tolerable problem, but a more robust application would need to take this fact into account.


So first there needs to be a way to tell which cell an object is in. Luckily, this is easy to do. Each polygon in a cell has a plane associated with it. All of the planes are defined such that the normal points into the cell. Simply controlling the winding order of the polygons created does this. Also known is that each point can be classified whether it is in front of or in back of a plane. For a point to be inside a cell, it must be in front of all of the planes that make up the boundary of the cell.

It may seem mildly counterintuitive to have the normals sticking in towards the center of the object rather than outwards, but remember that they're never going to be considered for drawing from the outside. The cells are areas of empty space surrounded by solid matter. You draw from the inside, and the normals point towards you when the polygons are visible, so the normals should point inside.

Now you can easily find out the cell in which both the source and destination locations are. If they are in the same cell, you're done (marching towards the target). If not, more work needs to be done. You need to generate a path that goes from the source cell to the destination cell. To do this, you put nodes inside each portal, and throw edges back and forth between all the portals in a cell. An implementation detail is that a node in a portal is actually held by both of the cells on either side of the portal. Once the network of nodes is set up, building the edges is fairly easy. Add two edges (one each way) between each of the nodes in each cell. You have to be careful, as really intricate worlds with lots of portals and lots of nodes have to be carefully constructed so as not to overload the graph. (Naturally, the more edges in the graph, the longer Dijkstra's algorithm will take to finish its task.)

You may be wondering why I'm bothering with directed edges. The effect of having two directed edges going in opposite directions would be the same as having one bi-directed edge, and you would only have half the edges in the graph. In this 2D example there is little reason to have unidirectional edges. But in 3D everything changes. If, for example, the cell on the other side of the portal has a floor 20 feet below the other cell, you can't use the same behavior you use in the 2D example, especially when incorporating physical properties like gravity. In this case, you would want to let the creature walk off the ledge and fall 20 feet, but since the creature wouldn't be able to turn around and miraculously leap 20 feet into the air into the cell above, you don't want an edge that would tell you to do so.

Here is where you can start to see a very important fact about AI. Although a creature seems intelligent now (well… more intelligent than the basic algorithms at the beginning of the chapter would allow), it's following a very standard algorithm to pursue its target. It has no idea what gravity is, and it has no idea that it can't leap 20 feet. The intelligence in this example doesn't come from the algorithm itself, but rather it comes from the implementation, specifically the way the graph is laid out. If it is done poorly (for example, putting in an edge that told the creature to move forward even though the door was 20 feet above it), the creature will follow the same algorithm it always does but will look much less intelligent (walking against a wall repeatedly, hoping to magically cross through the doorway 20 feet above it).

Application: Path Planner
The second application for this chapter is a fully functioning path planner and executor. The code loads a world description off the disk, and builds an internal graph to navigate with. When the user clicks somewhere in the map, the little creature internally finds the shortest path to that location and then moves there.

Parsing the world isn't terribly hard; the data is listed in ASCII format (and was entered manually, yuck!). The first line of the file has one number, providing the number of cells. Following, separated by blank lines, are that many cells. Each cell has one line of header (containing the number of vertices, number of edges, number of portals, and number of items). Items were never implemented for this demo, but they wouldn't be too hard to stick in. It would be nice to be able to put health in the world and tell the creature "go get health!" and have it go get it.

Points are described with two floating-point coordinates, edges with two indices, and portals with two indices and a third index corresponding to the cell on the other side of the doorway. Listing 6.6 has a sample cell from the world file you'll be using.

Listing 6.6: Sample snippet from the cell description file


17

6 5 1 0
-8.0 8.0
-4.0 8.0
-4.0 4.0
-5.5 4.0
-6.5 4.0
-8.0 4.0
0 1
1 2
2 3
4 5
5 0
3 4 8

... more cells




Building the graph is a little trickier. The way it works is that each pair of doorways (remember, each conceptual doorway has a doorway structure leading out of both of the cells touching it) holds onto a node situated in the center of the doorway. Each cell connects all of its doorway nodes together with dual edges—one going in each direction.

When the user clicks on a location, first the code makes sure that the user clicked inside the boundary of one of the cells. If it did not, the click is ignored. Only approximate boundary testing is used (using two-dimensional bounding boxes); more work would need to be done to do more exact hit testing (this is left as an exercise for the reader).

When the user clicks inside a cell, then the fun starts. Barring the trivial case (the creature and clicked location are in the same cell), a node is created inside the cell and edges are thrown out to all of the doorway nodes. Then Dijkstra's algorithm is used to find the shortest path to the node. The shortest path is inserted into a structure called sPath that is essentially just a stack of nodes. While the creature is following a path, it peeks at the top of the stack. If it is close enough to it within some epsilon, the node is popped off the stack and the next one is chosen. When the stack is empty, the creature has reached its destination.

The application uses the GDI for all the graphics, making it fairly slow. Also, the graph searching algorithm uses linear searches to find the cheapest node while it's constructing the shortest path. What fun would it be if I did all the work for you? A screen shot from the path planner appears in Figure 6.15 on the following page. The creature appears as a red circle.

Listing 6.7 gives the code used to find the shortest path in the graph. There is plenty of other source code to wander through in this project, but this seemed like the most interesting part.

Listing 6.7: The graph searching code for the path planner



cNode* cWorld::FindCheapestNode()
{
// ideally, we would implement a slightly more advanced
// data structure to hold the nodes, like a heap.
// since our levels are so simple, we can deal with a
// linear algorithm.

float fBestCost = REALLY_BIG;
cNode* pOut = NULL;
for( int i=0; i<m_nodeList.size(); i++ )
{
if( !m_nodeList[i]->m_bVisited )
{
if( m_nodeList[i]->m_fCost < fBestCost )
{
// new cheapest node
fBestCost = m_nodeList[i]->m_fCost;
pOut = m_nodeList[i];
}
}
}

// if we haven't found a node yet, something is
// wrong with the graph.
assert( pOut );

return pOut;
}

void cNode::Relax()
{
this->m_bVisited = true;

for( int i=0; i<m_edgeList.size(); i++ )
{
cEdge* pCurr = m_edgeList[i];
if( pCurr->m_fWeight + this->m_fCost < pCurr->m_pTo->m_fCost )
{
// relax the 'to' node
pCurr->m_pTo->m_pPrev = this;
pCurr->m_pTo->m_fCost = pCurr->m_fWeight + this->m_fCost;
}
}
}

void cWorld::ShortestPath( sPath* pPath, cNode *pTo, cNode* pFrom )
{
// easy out.
if( pTo == pFrom ) return;

InitShortestPath();

pFrom->m_fCost = 0.f;

bool bDone = false;
cNode* pCurr;
while( 1 )
{
pCurr = FindCheapestNode();
if( !pCurr )
return; // no path can be found.
if( pCurr == pTo )
break; // We found the shortest path

pCurr->Relax(); // relax this node
}

// now we construct the path.

// empty the path first.
while( !pPath->m_nodeStack.empty() ) pPath->m_nodeStack.pop();

pCurr = pTo;
while( pCurr != pFrom )
{
pPath->m_nodeStack.push( pCurr );
pCurr = pCurr->m_pPrev;
}
}

[Dragonball (POL)]

Continua...

Copyright © 2003 Wordware Publishing, Inc.

[Rick Hunter]

Peccato, sono troppo tecnici per il mio inglese risicato.