I’m implementing the A* search algorithm from this pseudo on wikipedia’s article:
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. 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] := h_score[start] // Estimated total cost 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, 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 else if 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_cost_estimate(y, goal) f_score[y] := g_score[y] + h_score[y] 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_nodeI’m stuck on the line where I’m asked to retrive the node in openSet with the lowest f value. When has openSet been filled? With what? Should it just have start on the first run?
I also don’t undestand the reconstruct path pseudo:
ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){ //if came_from[current_node] is set //what does it mean "ïs set"? //??? return null; }How should that pseudo instructions be implemented?
boolean AStar (Point start, Point goal){ HashSet <Point>closedSet = new HashSet<Point>(); HashSet <Point>openSet = new HashSet<Point>(); HashMap <Point,Point> came_from = new HashMap<Point, Point>(); HashMap <Point, Integer> g_score = new HashMap<Point, Integer>(); HashMap <Point, Integer> h_score =new HashMap<Point,Integer>(); HashMap <Point,Integer> f_score =new HashMap<Point,Integer>(); g_score.put(start, 0); h_score.put(start, heuristic_cost_estimate(start,goal)); f_score.put(start, heuristic_cost_estimate(start,goal)); openSet.add(start); while(!openSet.isEmpty()){ // x := the node in openset having the lowest f_score[] value //???? } return false; } Integer heuristic_cost_estimate(Point start, Point goal){ double minusI = (start.I-goal.I); int minusIi =(int)Math.pow(minusI,2.0D); double minusJ = (start.J-goal.J); int minusIj =(int)Math.pow(minusJ,2.0D); int ri = minusIj + minusIi; Integer result = new Integer(ri); return result; }ArrayList<Point> reconstructPath(Point cameFrom, Point current_node){ //if came_from[current_node] is set //what does it mean "ïs set"? //??? return null; }Advertisement
Answer
The open set initially contains the node that you start your search from – the starting node.
openset := set containing the initial node // The set of tentative nodes to be evaluated.As for the reconstruct path part – each time you process a node and find its neighbour X can be reached with a lower cost from the current node, you should set the came_from entry of X to the node you’re currently processing. Once you find the destination node, you reconstruct the path by following the came_from entries from the destination node until you reach to source node. You can implement this by modifying the Point class to have an additional field called came_from.
The only way to extract the node with the lowest value from the hash table is to iterate through the hash table. An alternative is to additionally have a tree map which will allow you to quickly find the element with the smallest value (or have a specialized heap, e.g. binary or Fibonacci heap which additionally allows you to decrease values of elements within the heap).
This is where I originally learned A*.