2012-03-05 14:41:25

Abel Gancsos
A* Algorithm

function A*(start,goal)
closedset := the empty set // The set of nodes already evaluated.
openset := {start} // The set of tentative nodes to be evaluated, initially containing the start node
came_from := the empty map // The map of navigated nodes.

g_score[start] := 0 // Cost from start along best known path.
h_score[start] := heuristic_cost_estimate(start, goal)
f_score[start] := g_score[start] + h_score[start] // Estimated total cost from start to goal through y.

while openset is not empty
current := the node in openset having the lowest f_score[] value
if current = goal
return reconstruct_path(came_from, came_from[goal])

remove current from openset
foreach neighbor in neighbor_nodes(current)
if neighbor in closedset
continue
tentative_g_score := g_score[current] + dist_between(current,neighbor)

if neighbor not in openset
h_score[neighbor] := heuristic_cost_estimate(neighbor, goal)
tentative_is_better := true
else if tentative_g_score < g_score[neighbor]
tentative_is_better := true
else
tentative_is_better := false

if tentative_is_better = true
came_from[neighbor] := current
g_score[neighbor] := tentative_g_score
f_score[neighbor] := g_score[neighbor] + h_score[neighbor]

return failure

function reconstruct_path(came_from, current_node)
if came_from[current_node] is set
p := reconstruct_path(came_from, came_from[current_node])
return (p + current_node)
else
return current_node

TIP: REPLACE [] WITH STANDARD HYPERTEXT PROTOCOL.
TIP: REPLACE WHATEVER IS BETWEEN THE [] WITH YOUR INFORMATION.

Hope that helps!