can anyone explain this for me?

[soldierno77]

function A*(start,goal)
     closedset := the empty set                 // The set of nodes already evaluated.     
     openset := set containing the initial node // The set of tentative nodes to be evaluated.
     g_score[start] := 0                        // Distance from start along optimal path.
     h_score[start] := heuristic_estimate_of_distance(start, goal)
     f_score[start] := h_score[start]           // Estimated total distance from start to goal through y.
     while openset is not empty
         x := the node in openset having the lowest f_score[] value
         if x = goal
             return reconstruct_path(came_from[goal])
         remove x from openset
         add x to closedset
         foreach y in neighbor_nodes(x)
             if y in closedset
                 continue
             tentative_g_score := g_score[x] + dist_between(x,y)
 
             if y not in openset
                 add y to openset
 
                 tentative_is_better := true
             elseif tentative_g_score < g_score[y]
                 tentative_is_better := true
             else
                 tentative_is_better := false
             if tentative_is_better = true
                 came_from[y] := x
                 g_score[y] := tentative_g_score
                 h_score[y] := heuristic_estimate_of_distance(y, goal)
                 f_score[y] := g_score[y] + h_score[y]
     return failure
 
 function reconstruct_path(current_node)
     if came_from[current_node] is set
         p = reconstruct_path(came_from[current_node])
         return (p + current_node)
     else
         return current_node

Can anyone explain this algorithm for me, please? Especially the g_score, f_score, h_score and the came_from. Thanks.

[caswal]

This is how it works, but its been a while since I looked at it.


f score is just a total of g and h.

H is an estimated (generally as the crow flies) distance to the target node
G is the cost so far, of getting to the current node.

These are added up to make the f score. The node with the lowest score in the open list is then used for the next iteration of the algorithm. As that is currently perceived as the optimum path.

A* As an algorithm works as follows (I am going to talk in tiles)
1) Start Tile g = 0;
2) Start Tile h = distance to target tile
3) Set CurrentTile to StartTile
4) Add CurrentTile to the open list

5) From the Current tile, iterate through all the adjacent tiles that are not in the open or closed list
6) Set adjacent tile g to CurrentTile.g + 1;
7) Set adjacent tile h to estimated distance to target tile
8) Set adjacent tile f to g + h
10) Set adjacent tile parent/previous to currentTile
9) Add adjacent tile to open list
10) Move CurrenTile to the closed list
11) Find a tile in the open list with the smallest f (best score), set as current tile
12) Goto step 5) unless CurrentTile is target
13) using the Parent of the currentTile, recurse back to produce the path

So in more human terms, look at all adjacent tiles, record how many steps it took to get there from the parent tile, and estimate how far it is to the target tile. Then Always pick the tile with the least amount of steps + distance to target. Don't look at tiles that have already been looked at, so we don't go backwards.

Hope that makes sense.