Don't understand what return does in pseudo code

Question

I am trying to add A* path finding in a game I'm making. I understand how to do it now but I don't understand what the returns do. http://en.wikipedia.org/wiki/A*_search_algorithm is the reference that I'm using. Questions:

• What does return reconstruct_path(came_from, goal) do?
• When is return failure invoked?

Answer 1

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.

Answer 2

Generically, return function() first evaluates the function() on stack and then whatever the function returns is returned by the parent/calling function.

In your case, return reconstruct_path(came_from, goal) will evaluate reconstruct_path(came_from, goal) and return that value back.

EDIT:

For instance-

A(){
  print(B());
}

B(){
  return 10;
}

This is a more 'static' example of how return works. Here, A() is the calling function and B() is the called function. The value being returned is 10 in this case. Moving on, in your problem, return f() first calls f(). f() has a return within it and returns a value- say 10. Then whatever f() evaluates into, is sent back to the original callee function.

Answer 3

reconstruct_path simply recursively returns the list of nodes the path consists from.