Unreal Engine 4 AI Programming Essentials

The A* algorithm

At the core of the Path Finding system is an algorithm that calculates the shortest navigable path between two points on NavMesh. Dijkstra's algorithm is named after the computer scientist Edsger Dijstkra, who originally created it in 1956 and later published it in 1959 to find the shortest paths between two points. There are a few path finding algorithms worth mentioning, but the most commonly used in gaming is a variant of Dijkstra's algorithm. The variant is called the A* algorithm. A* works by having a list of traversable points. Then, from the start position, we want to search for the shortest path in each available direction. We can determine this by heuristic values. These values will tell us how much it costs to traverse ...