A* Pathfinding
From WorkCDN
A* (pronounced "A star") is a best-first graph search algorithm. It is used to find the path with the least cost from one node to another out of one or more possible goals.
It uses a distance-plus-cost multi-part heuristic function. One part is the path-cost function (which might not be heuristic) and the other an admissible "heuristic estimate" of the distance to the goal. It uses these functions to determine the order in which the search visits nodes in the tree.
This algorithm is a bidirectional heuristic search algorithm.
To read more visit the Wikipedia article on A*.
Contents |
A* In Game Engines
Unity Game Engine
While Unity doesn't have A* integrated into it, several members of the Unity community have written (or attempted to) a code or a plugin that enables A* to work in Unity games. Here's a few:
- Implementation by Jonathan Czeck of Graveck Interactive. The PathFinder Class is his scripts are pretty much a fairly straight forward implementation of the AStar alogorithm with support for Manhattan and Euclidean path techniques.
- A newer implementation by "angryant". His Path project implements the A* algorithm on a user-provided NavMesh. It includes support for multiple inter-connected NavMeshes in one scene and provides an easy to use interface for requesting and handling calculated pathes.
Torque Game Builder
Torque Game Builder contains integrated A* in the API.
