AI GFX Topic Genre All
 
State of the Industry
Architecture
State Machines
Learning
Scripting
A* Pathfinding
Pathfinding / Movement
Flocking / Formations / Coordinated Movement
Multi-Agent Cooperation
Strategy / Tactical
Animation Control
Camera Control
Randomness
Player Prediction
Fuzzy Logic
Neural Nets
Genetic Algorithms
Natural Language Processing
AI Game Programming Wisdom
AI Game Programming Wisdom 2
Game Programming Gems
Game Programming Gems 2
Game Programming Gems 3
Game Programming Gems 4
GDC Proceedings
Game Developer Magazine
Gamasutra


Home    By Topic    By Genre    All Articles    Contact
A* Pathfinding


Near Optimal Hierarchical Path-Finding
Adi Botea, Martin Müller, Jonathan Schaeffer (University of Alberta)
Journal of Game Development, March 2004.
Abstract: The article presents HPA* (Hierarchical Path-Finding A*), a hierarchical approach for reducing problem complexity in path-finding on grid-based maps. This technique abstracts a map into linked local clusters. At the local level, the optimal distances for crossing each cluster are precomputed and cached. At the global level, clusters are traversed in a single big step. A hierarchy can be extended to more than two levels. Small clusters are grouped together to form larger clusters. Computing crossing distances for a large cluster uses distances computed for the smaller contained clusters. Our method is automatic and does not depend on a specific topology. Both random and real-game maps are successfully handled using no domain-specific knowledge. Our problem decomposition approach works very well in domains with a dynamically changing environment. The technique also has the advantage of simplicity and is easy to implement.

Basic A* Pathfinding Made Simple

James Matthews (Generation5)
AI Game Programming Wisdom, 2002.
Topics: A* Pathfinding; Genres: General
Abstract:

Generic A* Pathfinding
Daniel Higgins (Stainless Steel Software)
AI Game Programming Wisdom, 2002.
Topics: A* Pathfinding; Genres: General
Abstract:

Pathfinding Design Architecture
Daniel Higgins (Stainless Steel Software)
AI Game Programming Wisdom, 2002.
Topics: A*, Pathfinding; Genres: General
Abstract:

How to Achieve Lightning Fast A*
Daniel Higgins (Stainless Steel Software)
AI Game Programming Wisdom, 2002.
Topics: A* Pathfinding; Genres: General
Abstract:

Practical Optimizations for A* Path Generation
Timothy Cain (Troika Games)
AI Game Programming Wisdom, 2002.
Topics: A* Pathfinding; Genres: General
Abstract: The A* algorithm is probably the most widely used path algorithm in games, but in its pure form, A* can use a great deal of memory and take a long time to execute. While most optimizations deal with improving the estimate heuristic or with storing and searching the open and closed lists more efficiently, this article examines methods of restricting A* to make it faster and more responsive to changing map conditions. Such A* restrictions take the form of artificially constricting the search space, using partial solutions, or short-circuiting the algorithm altogether. For each restriction, the situations in which these optimizations will prove most useful are discussed.

Tactical Path-Finding with A*

William van der Sterren (CGF-AI)
Game Programming Gems 3, 2002.
Topics: A* Pathfinding, Tactical; Genres: General, FPS, RTS
Abstract: Tactical paths consider cover and stealth in addition to travel time. Although costs for cover and stealth are easily added to the A* cost function, this alone does not result in convincing tactical paths. This chapter analyzes the defects in these paths, and discusses tactical improvements: taking into account exposure time and enemy aiming behavior, and anticipating likely enemy movement. The extensions to the A* cost functions introduce additional run-time costs. This chapter discusses the costs, and provides work-arounds and optimizations to make tactical pathfinding more efficient.

Toward More Realistic Pathfinding
Marco Pinter (Badass Games)
Game Developer Magazine, April 2001.
Available Online at Gamasutra, 2001.
Topics: A*, Pathfinding, Movement; Genres: General
Abstract:

The Basics of A* for Path Planning

Bryan Stout
Game Programming Gems, 2000.
Topics: A* Pathfinding; Genres: General
Abstract:

A* Aesthetic Optimizations
Steve Rabin (Nintendo of America)
Game Programming Gems, 2000.
Topics: A* Pathfinding; Genres: General
Abstract:

A* Speed Optimizations
Steve Rabin (Nintendo of America)
Game Programming Gems, 2000.
Topics: A* Pathfinding; Genres: General
Abstract:

Pawn Captures Wyvern: How Computer Graphics Can Improve Your Pathfinding
Mark Brockington (BioWare)
Game Developers Conference Proceedings, 2000.
Available Online at Gamasutra, 2000.
Topics: A* Pathfinding; Genres: General
Abstract: For a long period of time, the study of games of thought (such as computer chess) rarely included discussions about pathfinding. However, the two fields are highly related to one another. Advances in computer chess searching algorithms can be used to dramatically speed up search algorithms such as A-Star. This talk looks at a number of computer chess searching improvements and shows, with concrete examples, how to improve A-Star-style pathfinding algorithms with these chess derived techniques.

Real AI, Part 2: Pathfinding
W. Bryan Stout
Computer Game Developers Conference Proceedings, 1996.
Topics: A*, Pathfinding; Genres: General
Abstract:

Smart Moves: Intelligent Path-Finding
W. Brian Stout
Game Developer Magazine, October 1996.
Available Online at Gamasutra, 1999.
Topics: A*, Pathfinding; Genres: General
Abstract:

 
Survey of best prices
Survey of best prices
AI Game Programming Wisdom

AI Game Programming Wisdom 2

Game
Programming
Gems


Game
Programming
Gems 2


Game
Programming
Gems 3


Game
Programming
Gems 4



Home