A* Search combines the best features of Breadth-first search (always finds
				optimal paths) and Best-First search (visits fewer nodes).  A* is like
				Best-First search, except that the priority for a node is the sum of the <b>actual</b>
				distance from the start to the node and the <b>estimated</b> distance to the
				goal: <blockquote>
					<p><code>key(node) = distance_from_start_to_node + |node<SUB>x</SUB> - exit<SUB>x</SUB>|
							+ |node<SUB>y</SUB> - exit<SUB>y</SUB>|</code></p>

				</blockquote>
				<p>You will need to keep track of the true distance from the start in each
					node.&nbsp; Then, when find the neighbors of a node, their distance is the
					distance of the current node plus one.</p>
				<p>There are also some other minor but important modifications you need to make to
					the Best-First algorithm:</p>
				<ul>
					<li>
						After you first see a node, you might see it again but along a shorter
						path.&nbsp; Therefore, instead of just checking whether a node has been visited
						or not before adding it to the queue, you have to check whether it has been
						visited <b>and</b>

					whether the distance from the start to that node previously calculated is the
					same or shorter than the distance along the current path.&nbsp; If both
					conditions hold, then you don't add it to the queue.&nbsp; But, if you have
					found a shorter path to the node, go ahead and insert it into the queue
					again.&nbsp; It is okay to have several copies of the same node, but with
					different priorities, in the queue.<br><br>
					<li>
						Do not stop the search until the goal is first <b>removed</b> from the queue,
						not when it is first <b>inserted</b> in the queue.&nbsp; This is because the
						first time you insert the goal you may not have found the shortest path to it.</li>

				</ul>