A* uses a best-first search and finds a least-cost path from a given initial node to one goal node (out of one or more possible goals). As A* traverses the graph, it builds up a tree of partial paths. The leaves of this tree (called the open set or fringe) are stored in a priority queue that orders the leaf nodes by a cost function, which combines a heuristic estimate of the cost to reach a goal and the distance traveled from the initial node. Specifically, the cost function is:

f(n) = g(n) + h(n)

Here, g(n) is the known cost of getting from the initial node to n; this value is tracked by the algorithm. h(n) is a heuristic estimate of the cost to get from n to any goal node. For the algorithm to find the actual shortest path, the heuristic function must be admissible, meaning that it never overestimates the actual cost to get to the nearest goal node. The heuristic function is problem-specific and must be provided by the user of the algorithm.

For example, in an application like routing, h(x) might represent the straight-line distance to the goal, since that is physically the smallest possible distance between any two points.

Like all informed search algorithms, it first searches the routes that appear to be most likely to lead towards the goal. What sets A* apart from a greedy best-first search is that it also takes the distance already traveled into account; the g(x) part of the heuristic is the cost from the starting point, not simply the local cost from the previously expanded node.

Starting with the initial node, it maintains a priority queue of nodes to be traversed, known as the open set or fringe. The lower f(x) for a given node x the higher its priority. At each step of the algorithm, the node with the lowest f(x) value is removed from the queue, the f and g values of its neighbors are updated accordingly, and these neighbors are added to the queue. The algorithm continues until a goal node has a lower f value than any node in the queue (or until the queue is empty). (Goal nodes may be passed over multiple times if there remain other nodes with lower f values, as they may lead to a shorter path to a goal.) The f value of the goal is then the length of the shortest path, since h at the goal is zero in an admissible heuristic.

The algorithm described so far gives us only the length of the shortest path. To find the actual sequence of steps, the algorithm can be easily revised so that each node on the path keeps track of its predecessor. After this algorithm is run, the ending node will point to its predecessor, and so on, until some node's predecessor is the start node.

First choose the environment in which you want to run the algorithm. The two options being:

1. Empty grid
2. Perfect maze

After that you can customize the grid in case you don't want to use the default settings.
Turn cells into walls, and vice versa, by simply clicking them. Setting the start and end node works the same way, you only need to click the button prior to making those changes. If you don't want to set walls individually you can also cick the 'generate walls' button which will turn some of the regular cells into walls.

Once everything is set click the 'start' button and watch the algorithm find its way from the start node (red) to the end node (blue). Unvisited cells are white, cells from the open set are gray and cells from the closed set are yellow. Every visited cell shows a line which points to the cell's predecessor.
Take a look at the 'description' section on this page to understand the meaning of the open and closed sets, and a cell's predecessor.

declare openSet as PriorityQueue with Nodes
declare closedSet as Set with Nodes
		        	
function a-star {
	// initialize open set, closed set still epmty
	openSet.enqueue(startNode, 0) 
	
	// repeat until shortest path was found or it is clear that no path exists       		
	while openSet.isNotEmpty() {
	
		// remove node from open set with minimal f value and store it in currentNode 
		currentNode = openSet.removeMin()
		
		// found end node? (path exists)
		if currentNode == endNode
			return PathFound
		
		// currentNode fully evaluated, no need for further analysis
		closedSet.add(currentNode)
			        			
		// add all successors of currentNode to open set	        			
		expandNode(currentNode)
	}
	
	// open set is empty, no path exists
	return NoPathFound	
}
		        	
// analyze all successors of a given node and add them to open set and/or set their cost if:		  
// successor was visited for the first time
// or a shorter path to that successor was found      	
function expandNode (currentNode) {
	foreach successor of currentNode {
		// if successor is already in closed set, do nothing and continue with next successor
		if closedSet.contains(successor)
   			continue
		
		// g value for new path is g value of currentNode plus cost from currentNode to successor        				
		tentative_g = g(currentNode) + costFromTo(currentNode, successor)
		
		// if successor is already in open set but new path is not better than the old one, do nothing        			
		if openSet.contains(successor) and tentative_g >= g(successor)
			continue
		
		// set pointer of successor and set its g value        				
		successor.predecessor = currentNode
		g(successor) = tentative_g
		
		// add successor to open set with new f value or   
		// update f value of successor if it's already in open set     			
		f = tentative_g + h(successor)
		if openSet.contains(successor)
			openSet.decreaseKey(successor, f)
		else
			openSet.enqueue(successor, f)
	}
}