0

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?
bstempi
  • 2,023
  • 1
  • 15
  • 27
Sicarius Solaris
  • 23
  • 2
  • 6
  • please provide source code – niyou Dec 17 '13 at 07:07
  • if you dont understand the algorithm why don't you choose another source as wikipedia – WhileTrueSleep Dec 17 '13 at 07:10
  • Source code is about 30ish lines long. I figured out the first part of my question. In adobe director I have to do "myvariable = myhandler(data)" with a return in the myhandler. My only question now is what does "Return failure" do? There is no variable or function named "failure" in the code – Sicarius Solaris Dec 17 '13 at 07:11

3 Answers3

0

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.

erbdex
  • 1,899
  • 3
  • 22
  • 40
  • The scripting style I use is old and quite different than most. I've never had to use returns, i use global variables. My only question now is about the "return failure" – Sicarius Solaris Dec 17 '13 at 07:20
  • Am i more clear now? And [this](http://stackoverflow.com/questions/7129285/why-would-you-use-the-return-statement-in-python) may help. – erbdex Dec 17 '13 at 08:03
0

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

martin
  • 2,520
  • 22
  • 29
0

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.

bstempi
  • 2,023
  • 1
  • 15
  • 27
  • Thanks for explaining it. I figured out how to implement it but still didn't really understand what the function did exactly. – Sicarius Solaris Dec 17 '13 at 07:28
  • The `came_from` map keeps track of where you've been in the graph. `reconstruct_path` walks through it backwards to build that path. By using recursion, it manages to build a path that goes from start->finish instead of finish->start. Does that help? – bstempi Dec 17 '13 at 07:33
  • yes it helps a lot. thank you. Only thing I don't understand now is the "return failure" part. is that just to end the script? – Sicarius Solaris Dec 17 '13 at 08:03
  • If it is able to find a path, then the path is returned. `return failure` is called when no suitable path is found. – bstempi Dec 17 '13 at 15:02