AStar

// A* Search Algorithm

1. Initialize the open list

2. Initialize the closed list put the starting node on the open list (you can leave its f at zero)

3. while the open list is not empty a) find the node with the least f on the open list, call it "q"

   b) pop q off the open list

   c) generate q's 8 successors and set their parents to q

   d) for each successor i) if successor is the goal, stop search successor.g = q.g + distance between successor and q successor.h = distance from goal to successor (This can be done using many ways, we will discuss three heuristics- Manhattan, Diagonal and Euclidean Heuristics)

     successor.f = successor.g + successor.h
   
   ii) if a node with the same position as 
       successor is in the OPEN list which has a 
      lower f than successor, skip this successor
   
   iii) if a node with the same position as 
       successor  is in the CLOSED list which has
       a lower f than successor, skip this successor
       otherwise, add  the node to the open list
   

   end (for loop)

   e) push q on the closed list end (while loop)