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?
Here's the function from your Wikipedia link:
return reconstruct_path(came_from, goal)
calls this function. The firstif
recursively callsreconstruct_path
, each time with a differentcurrent_node
, until thecurrent_node
is not incame_from
(until the if fails). Each time it calls itself, it returnsp := p + current_node
.p
keeps getting added to with each call, makingp
into a chain of nodes.The thing that it's traversing,
came_from
, is some map. It might look something like this: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 mapcame_from
, until it's build a pathp
. This might look like, "1, 2, 3, 4", sticking with the example above.return failure
is called when a path cannot be found.