   A Star search
  There's one aspect of A* I'm unsure of. I've coded up my interpretation of what I've read on A* and it finds a path, but it's certainly not guaranteed to be the best path, or even a good one.The part I don't understand is the open list. 1. I add my start node to the open list. 2. I look at all elements in the open list and find the "best" one.3. I remove it from the open list and add it to the closed. 4. Clear the open list.5. I add all nodes reachable from the node I just added to the closed list to the open list. Set the parent of all the nodes just added to the open list to the node that was just added to the closed list.6. goto 2 unless destination was just added to open list.The issue is clearly step 4. But if I don't do that step, my path back shows every option I took along the way, including the wrong ones. I could just not include the nodes that are more than 1 step away when back tracing, but that seems more like a hack fix. With step 4 not included, I think I'm missing a step that lets me "bubble up" when the path changes.   
  You should set the parent at step 5 if the total cost is less than the previous total cost for that node. Also, don't clear the open list on step 4. These are potential nodes you need to explore in case your best node leads you to a dead end.   ;  Let me quickly write up A* in the same basic form you have it in your procedure.1. Add the start node S to the open list.2. Select a minimum-cost node from the open list, E.3. Remove E from the open list, add E to the closed list.5. Generate set of nodes E+ which are possible states reachable from E. These nodes will have node E as their parent.6. Add each node X in E+ to the open list.7. If the goal state G is in the open list, you are done. Otherwise, go to step 2.Your problem is simply that your "step 4" is not part of the A* algorithm; you still may need to explore paths in the open list that your heuristic isn't leading you towards. For instance, your heuristic can lead you into a dead end, or just lead you in a non-optimal direction (say, by driving into tall grass in a straight line towards the goal, when there's actually a nearby road you can take that leads all the way there).   ;Quote:Original post by Wyrframe6. Add each node X in E+ to the open list.Just remember that this has some added complexity6a. If a node is not on the open list than calculate it's g score (g score of the current node + the cost to get from the current node to this one)6b. If a node is already on the open list, calculate the g score for that node as if it had been reached by the current node. If that score is more than the current score, ignore it. If that score is less than the score already recorded on that node (the score that was calculated when it was first added) then change it's g score and change it's fromNode value.  If you're using a binary heap, you will have to resort the heap in this case.-me