|
A* Pathfinding
Near Optimal Hierarchical Path-Finding
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 |  |
Topics: A* Pathfinding; Genres: General
Abstract:
Generic A* Pathfinding
Topics: A* Pathfinding; Genres: General
Abstract:
Pathfinding Design Architecture
Topics: A*, Pathfinding; Genres: General
Abstract:
How to Achieve Lightning Fast A*
Topics: A* Pathfinding; Genres: General
Abstract:
Practical Optimizations for A* Path Generation
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* | |
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 | |
Topics: A* Pathfinding; Genres: General
Abstract:
A* Aesthetic Optimizations
Topics: A* Pathfinding; Genres: General
Abstract:
A* Speed Optimizations
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:
|
