Introduction to A*
Excellent article - I recently worked on some pathfinding stuff and the material I found on A* was not that great but this is very well laid out.<p>Important side note: A* or other "best path" algorithms are not always preferable - there are some situations where it makes sense to use even less ideal paths in exchange for greater speed and less memory usage - even ones that are faster than greedy-best-first search with A* shown here.<p>If you use recursive backtracking with a decent set of heuristics (i.e. choose the node with the closest distance to the goal, "as the crow flies"), it can be be fast and ideal in many situations (it will always give an ideal path when there are few hook or concave shapes to deal with, which in many games or applications is often the case). It can be done in linear time and memory - it is important to note the cost of adding and searching nodes in the algorithm as well. It will never "fail" but it will produce very bad paths sometimes in complex situations, although even then it occasionally produces ideal paths.  In many situations where having an ideal path is not critical (say, townspeople just walking about doing their business) this can work well. Of course, you can use multiple algorithms or even mix them depending on what you are trying to achieve. RBT can be a good starting point just because it is so easy (maybe the easiest fail-safe algorithm outside of brute force?).<p>Secondary note: it is also good to subdivide your space - it does not need to be something complex like a sparse octree (in fact, that will make it harder to write and get good performance with in many situations).  Rather consider something like two levels of nodes.  On a 2D map, say you were to divide it into subsets of NxN grids of nodes.  Each one of these node grids attaches to its neighbor based on whether or not it is traversable in that direction (i.e. no matter where you enter the node grid, there is a path out in that direction).  This allows you to easily find a "high level" path which can be rapidly changed or discarded based on changing circumstances.