algorithm - How does A* pathfinding work?

I would like to understand on a fundamental level the way in which A* pathfinding works. Any code or psuedo-code implementations as well as visualizations would be helpful.

Answer

Disclaimer

There are tons of code-examples and explanations of A* to be found online. This question has also received lots of great answers with a lot of useful links. In my answer I'll try to provide an illustrated example of the algorithm, which might be easier to understand than code or descriptions.

---

Dijkstra's algorithm

To understand A*, I suggest you first have a look at Dijkstra's algorithm. Let me guide you through the steps Dijkstra's algorithm will perform for a search.

Our start-node is A and we want to find the shortest path to F. Each edge of the graph has a movement cost associated with it (denoted as black digits next to the edges). Our goal is to evaluate the minimal travel cost for each vertex (or node) of the graph until we hit our goal node.

This is our starting point. We have a list nodes to examine, this list currently is:

{ A(0) }

A has a cost of 0, all other nodes are set to infinity (in a typical implementation, this would be something like int.MAX_VALUE or similar).

We take the node with the lowest cost from our list of nodes (since our list only contains A, this is our candidate) and visit all its neighbors. We set the cost of each neighbor to:

Cost_of_Edge + Cost_of_previous_Node

and keep track of the previous node (shown as small pink letter below the node). A can be marked as solved (red) now, so that we don't visit it again. Our list of candidates now looks like this:

{ B(2), D(3), C(4) }

Again, we take the node with the lowest cost from our list (B) and evaluate its neighbors. The path to D is more expensive than the current cost of D, therefore this path can be discarded. E will be added to our list of candidates, which now looks like this:

{ D(3), C(4), E(4) }

The next node to examine is now D. The connection to C can be discarded, as the path isn't shorter than the existing cost. We did find a shorter path to E though, therefore the cost for E and its previous node will be updated. Our list now looks like this:

{ E(3), C(4) }

So as we did before, we examine the node with the lowest cost from our list, which is now E. E only has one unsolved neighbor, which is also the target node. The cost to reach the target node is set to 10 and its previous node to E. Our list of candidates now looks like this:

{ C(4), F(10) }

Next we examine C. We can update the cost and previous node for F. Since our list now has F as node with the lowest cost, we're done. Our path can be constructed by backtracking the previous shortest nodes.

---

A* algorithm

So you might wonder why I explained Dijkstra to you instead of the A* algorithm? Well, the only difference is in how you weigh (or sort) your candidates. With Dijkstra it's:

Cost_of_Edge + Cost_of_previous_Node

With A* it's:

Cost_of_Edge + Cost_of_previous_Node + Estimated_Cost_to_reach_Target_from(Node)

Where Estimated_Cost_to_reach_Target_from is commonly called a Heuristic function. This is a function that will try to estimate the cost to reach the target-node. A good heuristic function will achieve that less nodes will have to be visited to find the target. While Dijkstra's algorithm would expand to all sides, A* will (thanks to the heuristic) search in the direction of the target.

Amit's page about heuristics has a good overview over common heuristics.