Searching using A* (A-Star)

Searching using A* (A-Star)
The question arises while programming bfs and dfs: What if instead of blindly guessing the next node to traverse like in a simple dfs we pick the node which looks most promising? A* searches exactly like that: in a nutshell, we generate our possibilities and pick the one with the least projected cost. Once a possibility is generated and its cost is calculated, it stays in the list of possibilities until all the better nodes have been searched before it.

The cost function: f = g + h
 g is the cost it took to get to the node, most likely the number of squares we passed by from the start. h is our guess as to how much it'll cost to reach the goal from that node. It's our heuristic (a heuristic, informally, is something which is not a definite series of steps to a solution (like an algorithm) but it helps us determine our answers is a rough way).

struct node {
    node *parent;
    int x, y;
    float f, g, h;
}

Introduction to A*
http://www.redblobgames.com/pathfinding/a-star/introduction.html
I recommend using both: pathfinding for big picture, slow changing obstacles, and long paths; and movement for local area, fast changing, and short paths.

These algorithms represent the map as a graph and then find a path in that graph.
The key idea for all of these algorithms is that we keep track of an expanding ring called the frontier.
BFS:

frontier = Queue()
frontier.put(start)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()
   for next in graph.neighbors(current):
      if next not in came_from:
         frontier.put(next)
         came_from[next] = current

current = goal
path = [current]
while current != start:
   current = came_from[current]
   path.append(current)

Movement costs

We want Dijkstra’s Algorithm for this.

We need to track movement costs, so let’s add a new variable, cost_so_far, to keep track of the total movement cost from the start location. We want to take the movement costs into account when deciding how to evaluate locations; let’s turn our queue into a priority queue. Less obviously, we may end up visiting a location multiple times, with different costs, so we need to alter the logic a little bit. Instead of adding a location to the frontier if the location has never been visited, we’ll add it if the new path to the location is better than the best previous path.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost
         frontier.put(next, priority)
         came_from[next] = current

Movement costs can also be used to avoid or prefer areas based on proximity to enemies or allies.
Heuristic search

With Breadth First Search and Dijkstra’s Algorithm, the frontier expands in all directions. This is a reasonable choice if you’re trying to find a path to all locations or to many locations. However, a common case is to find a path to only one location. Let’s make the frontier expand towards the goal more than it expands in other directions. First, we’ll define a heuristic function that tells us how close we are to the goal:

def heuristic(a, b):
   # Manhattan distance on a square grid
   return abs(a.x - b.x) + abs(a.y - b.y)

In Dijkstra’s Algorithm we used the actual distance from the start for the priority queue ordering. Here instead, in Greedy Best First Search, we’ll use the estimated distance to the goal for the priority queue ordering. The location closest to the goal will be explored first. The code uses the priority queue from Breadth First Search but not cost_so_farfrom Dijkstra’s Algorithm:

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
came_from[start] = None

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      if next not in came_from:
         priority = heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

Those paths aren’t the shortest. So this algorithm runs faster when there aren’t a lot of obstacles, but the paths aren’t as good.
The A* algorithm
Dijkstra’s Algorithm works well to find the shortest path, but it wastes time exploring in directions that aren’t promising. Greedy Best First Search explores in promising directions but it may not find the shortest path. The A* algorithm uses both the actual distance from the start and the estimated distance to the goal.

A* combines the two. Instead of contour lines showing distances from start or goal, in A* the contour lines show the length of the paths. The inner region has the shortest paths. A* starts by exploring that inner region, and moves outwards only if it can’t find a path in there. Try drawing some walls to see how A* has to climb out of the innermost region to find a path.

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = {}
cost_so_far = {}
came_from[start] = None
cost_so_far[start] = 0

while not frontier.empty():
   current = frontier.get()

   if current == goal:
      break
   
   for next in graph.neighbors(current):
      new_cost = cost_so_far[current] + graph.cost(current, next)
      if next not in cost_so_far or new_cost < cost_so_far[next]:
         cost_so_far[next] = new_cost
         priority = new_cost + heuristic(goal, next)
         frontier.put(next, priority)
         came_from[next] = current

You can see that A* tries to stay within the same estimated path length (which we use as the priority for the queue) as much as possible. Why does it run faster than Dijkstra’s Algorithm? Both algorithms explore the same set of locations. However, the heuristic function lets us visit the locations in a different order that makes it more likely that the goal node will be encountered sooner.

• If you want to find paths from or to all all locations, use Breadth First Search or Dijkstra’s Algorithm. Use Breadth First Search if movement costs are all the same; use Dijkstra’s Algorithm if movement costs vary.
• If you want to find paths to one location, use Greedy Best First Search or A*. Prefer A* in most cases. When you’re tempted to use Greedy Best First Search, consider using A* with an “inadmissible” heuristic.

What about optimal paths? Breadth First Search and Dijkstra’s Algorithm are guaranteed to find the shortest path given the input graph. Greedy Best First Search is not. A* is guaranteed to find the shortest path if the heuristic is never larger than the true distance. As the heuristic becomes smaller, A* turns into Dijkstra’s Algorithm. As the heuristic becomes larger, A* turns into Greedy Best First Search.

What about performance? The best thing to do is to eliminate unnecessary locations in your graph. If using a grid, see this. Reducing the size of the graph helps all the graph search algorithms. After that, use the simplest algorithm you can; simpler queues run faster. Greedy Best First Search typically runs faster than Dijkstra’s Algorithm but doesn’t produce optimal paths. A* is a good choice for most pathfinding needs.

Read full article from Searching using A* (A-Star)