CODEWITHSUNDEEP
a-star
archenil
archenil

Reputation: 153

A* (A Star) Algorithm Clarification

I was trying to implement a simple A* search program based on Wikipedia's pseudocode. However, its explanation of openset is somewhat unclear to me. I understand the start node will be added to openset initially. However, the code execution throws an error at remove current from openset, which makes sense because current was never added to the openset during first iteration. It seems the openset will also need to add start node's 8 neighbors before looping. Can someone please point me in the right direction?

Thanks,

 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.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

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

     remove current from openset
     add current to closedset
     for each 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 or tentative_g_score <= g_score[neighbor] 
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

Upvotes: 4

Views: 4943

Answers (1)

BlueRaja - Danny Pflughoeft
BlueRaja - Danny Pflughoeft

Reputation: 85966

The "Open set" is the set of nodes we choose current from - that is, it contains all the nodes we might be interested in looking at next. The "Closed set" is the set of nodes we've already considered. Often, rather than an actual closed-set, we'll just set a flag on each Node, named HasBeenVisited or something similar.

Initially, the Open set contains only start, so in the first iteration we remove start, add its neighbors to the Open set, and add start to the Closed set. Then we take the next node in the Open set, add its neighbors, etc.

Assuming your heuristic is consistent, they do not get readded to the open set once removed.

Upvotes: 4

Related Questions