Algorithm Details:

• The A* search algorithm uses a heuristic function h that estimates the distance between v_i and t such that:
  1. underestimates the cost: h(v_i) < d(v_i,t) where d(i,j) is the smallest distance between i and j
  2. Is monotonic: h(v_i) < h(v_j) => d(v_i,t) < d(v_j,t)
  Such heuristics are said to be admissible and guarantee that A* will give a correct optimal solution.
  Note: We have used the Manhattan distance (= |x₂-x₁| + |y₂-y₁|) as the heuristic because our graph is of the form of a grid where each vertex represents a x,y coordinate.
• The A* algorithm expands node n with min f(n) + h(n) every iteration, where f(n) is the currently known distance of n from s. This is an optimistic choice as the f(n) + h(n) gives a lower bound on the length of the current path to t.
• This continues until the algorithm selects n = t, when it terminates and an optimal path is found. Note that this path has to be optimal since, all the other paths had larger optimistic estimates f(v)+h(v).