I was hoping that someone could help me with a bit of clarification on this algorithm. Below is the pseudocode listed for the A* algorithm on Wikipedia. I am very confused as to what "an empty map" and "map with default value of Infinity" are in this case. In the case that the nodes are xy coordinates, and the paths between the nodes are an adjacent xy coordinate (every coordinate being a whole number), then could I receive an explanation on what a map would be in that case? Would it be an empty array of coordinates? How would I represent map with infinity as its value then? What relevance does is have in the code. Sorry if this question isn't very well suited here, I'm just asking for a better explanation from someone who is familiar with the A* algorithm.
function A*(start, goal)
// The set of nodes already evaluated
closedSet := {}
// The set of currently discovered nodes that are not evaluated yet.
// Initially, only the start node is known.
openSet := {start}
// For each node, which node it can most efficiently be reached from.
// If a node can be reached from many nodes, cameFrom will eventually contain the
// most efficient previous step.
cameFrom := an empty map
// For each node, the cost of getting from the start node to that node.
gScore := map with default value of Infinity
// The cost of going from start to start is zero.
gScore[start] := 0
// For each node, the total cost of getting from the start node to the goal
// by passing by that node. That value is partly known, partly heuristic.
fScore := map with default value of Infinity
// For the first node, that value is completely heuristic.
fScore[start] := heuristic_cost_estimate(start, goal)
while openSet is not empty
current := the node in openSet having the lowest fScore[] value
if current = goal
return reconstruct_path(cameFrom, current)
openSet.Remove(current)
closedSet.Add(current)
for each neighbor of current
if neighbor in closedSet
continue // Ignore the neighbor which is already evaluated.
if neighbor not in openSet // Discover a new node
openSet.Add(neighbor)
// The distance from start to a neighbor
//the "dist_between" function may vary as per the solution requirements.
tentative_gScore := gScore[current] + dist_between(current, neighbor)
if tentative_gScore >= gScore[neighbor]
continue // This is not a better path.
// This path is the best until now. Record it!
cameFrom[neighbor] := current
gScore[neighbor] := tentative_gScore
fScore[neighbor] := gScore[neighbor] + heuristic_cost_estimate(neighbor, goal)
return failure
Here is the reconstruct_path() function:
function reconstruct_path(cameFrom, current)
total_path := [current]
while current in cameFrom.Keys:
current := cameFrom[current]
total_path.append(current)
return total_path
Source: wikipedia
I am very confused as to what "an empty map" and "map with default value of Infinity" are in this case. In the case that the nodes are xy coordinates, and the paths between the nodes are an adjacent xy coordinate (every coordinate being a whole number), then could I receive an explanation on what a map would be in that case? Would it be an empty array of coordinates? How would I represent map with infinity as its value then?
For the word "map" in this context, you should not be thinking of anything like a map in regular english (like an overview of what the area looks like). A map is simply a data structure in which you can store Key-Value pairs, and later on efficiently look up the Value for any given Key. For more info on this, see the tag info page.
When they initialize cameFrom as an empty map, they simply mean a map that does not yet contain any Key-Value pairs initially. Later on in the code, the line
cameFrom[neighbor] := current
means that they store (neighbor, current) as a Key-Value pair, where neighbor is the Key, and current is the value. Storing this pairs enables efficient reconstruction of the path later on in the reconstruct_path() function.
When they initialize gScore as a map with a default value of infinity, this is initially also simply an empty map (containing no pairs). However, with "default value of infinity", they mean that if you ever try to query a value from it with a Key that does not yet exist, it will return infinity as value (the default value).
In the following line of code
gScore[start] := 0
they add the (Key, Value) pair (start, 0) to the map. So, after that, if you were to ask the map what its Value is for Key = start, you'd get 0. If you were to ask the same for any other Key, you'd get the default value of infinity, because at that point in the code it does not contain any other Keys (later on this changes of course, as more pairs are added).