The A* algorithm is a really interesting one. It's conceptually quite simple if you approach it from the right angle, but most of the time I've seen it poorly explained, and as a consequence, people really struggling to "get it".
My little contribution is a very accessible series of articles that derives A* almost from scratch, in a way that is really easy to understand: http://gabrielgambetta.com/path1.html
What I find interesting is that A star, DFS, BFS, Dijkstra's algorithm, JPS, etc are all basically the same algorithm. The only real difference is the queuing priority. (BFS is LIFO, DFS is FIFO, Dijkstra is min-distance-from-start-first, A star is min-distance-from-start-plus-(admissible,ideally)-heuristic-distance-to-end-first )
Most CS courses I've seen teach them as entirely separate algorithms, which I find... frustrating. Or rather, unnecessarily complex.
What you say is absolutely correct, and I really don't understand why this is not the way it's explained by default. I've written some articles, linked from some other comment here, that does exactly what you propose. People generally find them extremely useful.
In 2011, Harabor and Grastien introduced Jump Point Search (JPS) that achieves up to a 10x speed improvement over A* on uniform cost grids. In the last year, an additional 10x speed improvement to JPS, called JPS+ was independently developed by Steve Rabin as well as Harabor and Grastien. This improved algorithm is over 100x faster than A* on maps with open areas and over 2x faster than A* on worst-case maps. This incredible speed-up is due to pre-computation, eliminating the recursion in JPS and focusing only on touching select relevant nodes during the search.
There is another pathfinding algorithm with smaller pre-computation step and comparable (if not higher) speed. It allows you to do benchmarks on various maps, and it compares itself to other algorithms. I also think it's simpler than JPS.
And if your maps don't change, you can use precomputation with A* , making it even faster than JPS+.
1. Preprocess the graph to make it smaller. Visibility graphs are a first step, but if you have grid movement you can remove the redundancies (e.g. N-N-W taking you to the same place as W-N-N) to make an even smaller pathfinding graph. Here's a library implementing one of many such algorithms: http://mikolalysenko.github.io/l1-path-finder/www/
2. Preprocess the graph to get better distance estimates. The closer your A* heuristic is to the actual distance, the faster A* will run. “Differential heuristics” use the triangle inequality: if you have exact distances to one point L, then you can say dist(A, B) >= dist(L, B) - dist(L, A). There are other approaches too.
I wrote a tutorial for this too which includes c++ source code that's been used in some succcesful video games and thereby tested by millions of people http://heyes-jones.com/astar.php
One of the most used in industry approaches to pathfinding in things like RTSes is what's called a flow field. It's a bit like a precalculated pathfinding map.
These are some of the most interesting for what you can accomplish (pathfinding a ton of units at once!).
Is it really necessary to write so many blog posts explaining this 50 year old algorithm? I would have thought that there is enough material around right now.
My little contribution is a very accessible series of articles that derives A* almost from scratch, in a way that is really easy to understand: http://gabrielgambetta.com/path1.html