Search Tips Advanced Search |
| 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
#### Enhancements Although this algorithm is relatively powerful, it is easy to bog it down and send it on a wild goose chase. In particular, large U–shaped sections of obstacles can make the algorithm calculate dozens or even hundreds of nodes that will not be part of the final path. This could potentially overflow the list of path nodes, or at a minimum cause a noticeable pause when a unit calculates a path over long distances. Therefore, your game world should avoid such constructions.
| Caution: This implementation could potentially get the sprite caught in an infinite loop on some maps, resulting in an overflow situation which would most likely crash the machine.
One way to avoid an overflow on the path list would be to restrict the number of nodes in this list to some arbitrary number. Our example constrains the path to a total number of 50 nodes. This may need to be adjusted for large maps, but it will ensure that the path node list never overflows, and it will restrict pathing time to a maximum amount. If a unit tries to path to a destination, but the path node list reaches the limit before the destination is reached, you could just set a flag for that entity, and repath when the unit reaches the last node in its list. Allowing the user to set waypoints for a unit will further improve pathing, as the paths between each waypoint tend to be shorter and encounter fewer obstacles. This algorithm is somewhat intelligent, but it can be easily fooled by certain obstacle constructions. Looking at nodes in the three directions relative to the direction of the destination is somewhat of an optimization, and cuts down on the number of calculations required at each node. However, this sometimes leads to paths that look less than intelligent, even downright stupid. The algorithm could be changed so that it checks all eight directions at each node. While this will dramatically increase the number of calculations, the overall path will tend to be much shorter and look more natural. Additionally, this algorithm does not take into account nodes with different movement costs. For example, say that the game world was populated by terrain consisting of hard rock, grasslands, mud, swamp, and water. While water terrain might be impassible, the others can be moved through but at different degrees of difficulty. Hard rock or roads would certainly be the easiest to move over, but grasslands, mud, and swamp would all impose penalties to movement while not being totally impassible. Elevation could also be a factor. This algorithm would need to be modified somewhat if your game world features terrain with varying movement costs. ### Summary In this chapter, we discussed techniques for implementing simplistic artificial intelligence routines that give our sprites the ability to display cunning and strategy when moving around the game world. We looked at different movement techniques, including chasing or evading the player and patterned movement. We also looked at controlling the movement decisions based on a finite state machine, as well as techniques for weighting the selected states as a method for implementing rudimentary personalities. When using artificial intelligence techniques in your games, it is important to keep these points in mind: • No matter how good your artificial intelligence algorithms may be, there is no greater challenge than playing another human being. However, some people may be unable to hook up with someone else to play a multiplayer game, or they may just enjoy playing by themselves. Therefore, it is important to include artificial intelligence algorithms in your games that make the antagonists at least moderately challenging. • The most noticeable display of artificial intelligence is in the movement of enemy units. In most action games, the user is going to be primarily concerned with the movement of enemy units, such as whether they are aggressively chasing the user’s ship or running like cowards. • Perhaps the simplest simulation of artificial intelligence is to introduce an element of randomness. When an enemy unit moves in a fashion that is unpredictable to the player, that unit can appear to exhibit a rudimentary intelligence. Consider the apparently random flight path of a common housefly. It darts about here and there, yet it always appears to have a mind of its own and to know where it’s going. • An enemy that actively hunts down the player can be perceived as confident, powerful, and aggressive. By contrast, an enemy that constantly eludes the player or turns tail can be perceived as cowardly, injured, or perhaps even cunning, like an assassin stalking its target. • We can use algorithms that make enemy units move about in a specific pattern. This can make antagonists appear to move in a very deliberate manner. Very complex movements can be modeled this way, where some patterns could be useful for evading the player, such as a zigzag pattern, and some patterns could be useful for chasing the player, such as a circular pattern to move around the player’s flank. • A finite state machine is a logical construction that consists of several “states,” each of which defines a specific behavior, and “state transitions,” which define specific rules for moving from state to state. Finite state machines are a method by which an enemy unit can make a series of rational decisions based on various inputs from the game world, such as the current environment as well as the actions of the player. • A probability machine is an extension of a finite state machine, allowing the application to simulate personalities based on a certain distribution factor. Using this technique, we can make some sprites appear more passive, some more aggressive, some a little bit sneakier, etc. It works by choosing the next state based on a weighted distribution as identified by the type of personality we’re modeling. • Most games feature a game world filled with moving sprites which must navigate around immovable or impassible obstacles. Path finding artificial intelligence routines must be utilized in order to make the sprite appear to move in an intelligent manner, selecting the most direct, shortest path available. • Breadth first search and depth first search techniques could be used, but these are typically too slow or too inaccurate for game applications. The A* (pronounced “A–star”) algorithm combines the best of breadth first search and depth first search to find a fairly direct, short path in a short amount of 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.