Path-finding in Games: A* Algorithm

Above picture is the sample application on which I had implemented the A* algorithm. The application had multiple maps and various movement toggle options. It also timed how fast the A* search was. The best time that I could do was somewhere 84 ms units. This A* algorithm also implements rubber-banding and smooths the path by using a Catmull-Rom Spline.

The problem we’re trying to solve is to get a game object from the starting point to a goal. Path finding addresses the problem of finding a good path from the starting point to the goal―avoiding obstacles, avoiding enemies, and minimizing costs (fuel, time, distance, equipment, money, etc.). Movement addresses the problem of taking a path and moving along it. It’s possible to spend your efforts on only one of these. At one extreme, a sophisticated pathfinder coupled with a trivial movement algorithm would find a path when the object begins to move and the object would follow that path, oblivious to everything else. At the other extreme, a movement-only system would not look ahead to find a path (instead, the initial “path” would be a straight line), but instead take one step at a time, considering the local environment at every point. Best results are achieved by using both path finding and movement algorithms.

The secret to A*'s success is that it combines the pieces of information that Dijkstra’s Algorithm uses (favoring vertices that are close to the starting point) and information that Greedy Best-First-Search uses (favoring vertices that are close to the goal). In the standard terminology used when talking about A*, g(n) represents the exact cost of the path from the starting point to any vertex n, and h(n) represents the heuristic estimated cost from vertex n to the goal. In the above diagrams, the yellow (h) represents vertices far from the goal and teal (g) represents vertices far from the starting point. A* balances the two as it moves from the starting point to the goal. Each time through the main loop, it examines the vertex n that has the lowest f(n) = g(n) + h(n).