I will be focusing on the A* Algorithm. A* is the most popular choice for pathfinding, because it’s fairly flexible and can be used in a wide range of contexts.
A* is like other graph-searching algorithms in that it can potentially search a huge area of the map. It’s like Dijkstra’s algorithm in that it can be used to find a shortest path. It’s like BFS in that it can use a heuristic to guide itself. In the simple case, it is as fast as BFS:
In the example with a concave obstacle, A* finds a path as good as what Dijkstra’s algorithm found:
The secret to its 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 BFS uses (favoring vertices that are close to the goal). In the standard terminology used when talking about A*, g(n) represents the 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).
No comments:
Post a Comment