Pathfinding
Don't get stuck
Search Space Representation
Pathfinding directly over the level data is to expansive so simpler data structure is used that describe where in the world it is possible to move. The data structure is called the search space and the common ones are Grid, Point and Navmesh. Each search space contains some form of node that represent a position or area in the world and they are connected with each other with links. When picking a search space for a game one need to look at the following characteristics that affect the choice. The search itself is done with a graph search algorithm.
Dynamic
How well can the search space handle Dynamic obstacles that modify the search space at run-time.
Localization:
What is to cost to take a position in the world and convert it to the search space position.
Memory Usage:
How much memory does the search space take to represent an area in the world.
Planning
Cost of finding a path in the search space. Fewer nodes is better when searching for a path.
Smoothing
How easy it is to improve a path returned by the search space. Paths are often returned as the 'best path' and it might contain sharp turns or detours. It might be the fastest path or whatever 'best' is set as but it would not be the way a human walks for example.
- Crowd
- Hierarchical pathfinding
Reference
- Baby steps to an Artificial Intelligence - 2015
- JPS+: Over 100x Faster than A* - 2015
- Generalized Platformer AI Pathfinding - 2014
- Solving path finding and AI movement in a 2D platformer - 2014
- Path Finding for Innovative Games - 2014
- Object Avoidance and Smoothing Movement
- Navigation
- Graph Creation and Best Path Selection
- Steering Behaviors For Autonomous Characters -
- Path Finding for Innovative Games: Object Avoidance and Smoothing Movement - 2014
- Pathfinding II: A* and Heuristics - 2014
- Pathfinding III: Putting it All Together - 2014
- Pathfinding I: Map Representation and Preprocessing - 2013
- Pathfinding concepts, the basics - 2013
- Lazy Theta*: Faster Any-Angle Path Planning - 2013
- AI Pathfinding Ray Casting - 2013
- Clearance-based Pathfinding and Hierarchical Annotated A* Search - 2009
- Search Space Representations, AIGPW2 p85-102. - 2004.
- Inexpensive Precomputed Pathfinding Using a Navigation Set Hierarchy, AIGPW2 p103-113. - 2004.
- Path Look-up Tables - Small is Beautiful, AIGPW2 p115-129. - 2004.
- An Overview of Navigation Systems, AIGPW2 p131-139. - 2004.
- Jumping, Climbing, and Tactical Reasoning: How to Get More Out of a Navigation System, AIGPW2 p141-150. - 2004.