I am trying to implement in c the pseudocode of a* algorithm given by wikipedia but I am really stuck in understanding what is the reconstruct_path function, can someone explain to me what do the variables in this function (p, p+current_node, set) represent?
function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node
came_from := the empty map // The map of navigated nodes.
g_score[start] := 0 // Cost from start along best known path.
// Estimated total cost from start to goal through y.
f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)
while openset is not empty
current := the node in openset having the lowest f_score[] value
if current = goal
return reconstruct_path(came_from, goal)
remove current from openset
add current to closedset
for each neighbor in neighbor_nodes(current)
tentative_g_score := g_score[current] + dist_between(current,neighbor)
if neighbor in closedset
if tentative_g_score >= g_score[neighbor]
continue
if neighbor not in openset or tentative_g_score < g_score[neighbor]
came_from[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
if neighbor not in openset
add neighbor to openset
return failure
function reconstruct_path(came_from, current_node)
if came_from[current_node] in set
p := reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node
Thank you
came_from is a map of navigated nodes, like the comment says. It can be implemented in several ways, but a classic map should be fine for this purpose(even a list is fine).
If you are not familiar with maps, checkout std::map.
The goal of A* is to find a list of moves, that will solve the given problem (represented as a graph). A solution is a path through the graph.
In the pseudocode proposed, came_from store the "history" of the solution you are actually evaluating (so a possible path through the graph).
When you explore a node (a new node or one with less cost in the already visited list):
if neighbor not in openset or tentative_g_score < g_score[neighbor]
came_from[neighbor] := current
you are saving in the came_from map the node where you come from. (It's simpler to think at it as the ordered list of moves till the solution node is reached. A map is used instead of a list for performance issues).
The line above basically means:
"Now I'll visit neighbor node. Remember that I reached neighbor node coming from current node".
When goal node is reached, A* needs to return the list of moves from start node to goal. You have the reference to the goal node, so you can now recontruct the list(reconstruct_path) of moves to reach it coming from start node, because you stored the list of moves in came_from map.