A-star search

Intro

A* is a pathfinding graph traversal algorithm. The algorithm was first described in 1968 by Stanford researchers Peter Hart, Nils Nilsson and Bertram Raphael.

$$f(n)=g(n)+h(n)$$

A Formal Basis for the Heuristic Determination of Minimum Cost Paths

https://ieeexplore.ieee.org/document/4082128

Resources

• https://theory.stanford.edu/~amitp/GameProgramming/AStarComparison.html

A* Algorithm

A* Algorithm

https://www.redblobgames.com/pathfinding/a-star/introduction.html

frontier = PriorityQueue()
frontier.put(start, 0)
came_from = dict()
cost_so_far = dict()
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

Heuristic

A heuristic is a function that estimates the cost from the current node to the goal node.

https://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html

Euclidean distasnce

Euclidean distance meaures the shortest path between points as a straight line.

$$d=\sqrt{(x_2-x_1{)}^2+(y_2-y_1{)}^2}$$

Euclidean distance

If your units can move at any angle (instead of grid directions), then you should probably use a straight line distance:

function heuristic(node) =
    dx = abs(node.x - goal.x)
    dy = abs(node.y - goal.y)
    return D * sqrt(dx * dx + dy * dy)

Manhattan distance

The standard heuristic for a square grid is the Manhattan distance (AKA taxicab distance), which measures distance only along the x and y axes.

$$d=|x_2-x_1|+|y_2-y_1|$$