Here's the function from your Wikipedia link:
function reconstruct_path(came_from, current_node)
if current_node in came_from
p := reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node
return reconstruct_path(came_from, goal)
calls this function. The first if
recursively calls reconstruct_path
, each time with a different current_node
, until the current_node
is not in came_from
(until the if fails). Each time it calls itself, it returns p := p + current_node
. p
keeps getting added to with each call, making p
into a chain of nodes.
The thing that it's traversing, came_from
, is some map. It might look something like this:
1, 2
2, 3
3, 4
Calling came_from[1]
would return 2. Or, you could say, "2 came from 1".
In short: reconstruct_path
calls itself, each time walking a step back in the map came_from
, until it's build a path p
. This might look like, "1, 2, 3, 4", sticking with the example above.
return failure
is called when a path cannot be found.