Book, 614 pages plus CD-ROM of example source code.
This book is another “classic” of the computer game industry and, like LaMothe’s Tricks of the Windows Game Programming Gurus above, includes a CD-ROM of example source code. Gems, however, is comprised of a series of articles both written specifically for this book and those reprinted from other sources.
Chapter 3, Artificial Intelligence, includes the following articles:
Designing a General Robust AI Engine by Steve Rabin.
This is a general overview of AI engines used in games and suggests a method as described in the flow chart below.
A central message router sorts and clears ‘game objects’ that are then sent to a specific State Machine for processing. Rabin’s message consists of five fields: a descriptive name, name of sender, name of receiver, time it should be delivered and relevant data. An example message from the article is: name:damaged, from:dragon, to:knight, deliver_at_time:245.34, data:10 (damage)
Rabin also states the value of this system because it leaves an ‘electronic paper trail’ which is useful for debugging and the desirability of sending “delayed messages” which can be acted upon at a later time. Caveat: ensure that the game object has not been destroyed before a delayed message is acted upon.
A Finite-State Machine Class by Eric Dybsand.
This article is primarily source code for implementing an FSM in C++.
Game Trees by Jan Svarovsky.
Game trees are only applicable to discrete games such as chess and checkers and, therefore, are not of
The Basics of A* for Path Planning by Bryan Stout. Note: Stout also wrote Smart Moves: Intelligent Pathfinding. Stout (1996) below.
Theoretically an A* search will eventually return the “cheapest” path (as defined by the code which can weight various terrain types in different “costs”). However, on large maps an A* search can create thousands of nodes which can quickly consume all available memory.
Stout writes, “The case in which A* is most inefficient is in determining that no path is possible between the start and goal locations; in that case, it examines every possible location accessible from the start before determining that the goal is not among them…”
See also Amit's Thoughts on Path-Finding on this disk.
A* Aesthetic Optimizations by Steve Rabin.
This is an interesting short article describing various methods of smoothing A* paths by using Catmull-Rom and other spline techniques.
A* Speed Optimizations by Steve Rabin.
A* is a very slow algorithm because it must search every possible ‘square’ in a map. For example a 1,000 x 1,000 grid map will produce 1 million squares that need to be evaluated.
This article presents two basic methods for speeding up A* path searches. The first is reducing the number of ‘squares’.
The diagrams above represent: a) a rectangular (or hexagonal) grid; b) an actual polygonal floor; c) a polygonal floor representation and d) points of visibility. ‘A’ is, of course, the slowest. ‘B’ uses the actual polygons created by a 3D program; which can be extraordinarily complex in many cases. ‘C’ cheats by having a pathing map created and overlaying the real map. This method is completely unacceptable for terrains that are not predesigned. ‘D’, again, represents another predesigned method.
Other techniques suggested are a hierarchical pathfinding system which, again, is restricted to certain medthods of terrain and/or obstacles representation. Lastly, modifications of the heuristic cost of the A* search will produce optimatization but it is impossible to predict at what cost of the quality of the path found.
Simplified 3D Movement and Pathfinding Using Navigation Meshes by Greg Snook.
This method involves “cheating” and precalculated paths which are not applicable to my are of interest.
Flocking: A Simple Technique for Simulating Group Behavior by Steven Woodcock.
The boids.c source code is included here.
Fuzzy Logic for Video Games by Mason McCuskey.
A very good, but very short, primer for fuzzy logic.
A Neural-Net Primer by André LaMothe.
This appears to be an expanded article of what first appeared in his Tricks of the Windows Game Programming Gurus (see above). This also includes source code on the CD-ROM and briefly describes Hebian nets and Hopfield autoassociation nets.