Minimalistic 3D Obstacle Avoidance Behavior using Simulated Evolution genetic algorithms is the subject of a fascinating page I ran across.

The authors of the page describe a system in which they use genetic algorithms to "evolve" a software agent that can both learn to fly and learn how to avoid obstacles during flight. There are some fascinating movies on the site through which you can watch agents evolve, and there's an abstract about the thinking behind the design that makes for some interesting reading.

Justin Heyes-Jones is an enthusiast who's put together a nice page explaining the A* algorithm in all its gory detail. What makes it of interest to me is that he discusses using it to solve the famous "8 puzzle" (that sliding numbers puzzle in which you have to get everything sequential)....something I've not seen (or at least not noticed) A* used for before. All in all, a fine page for understanding what the A* algorithm is all about, how it works, and how you can use it.

Amit's Game Programming Page -- An excellent collection of game programming links, articles, and whatnot, with a special focus on pathfinding. Amit has been a frequent contributor to both the comp.ai.games newsgroup and the Software Solutions page. You could do a lot worse than to use his page as a starting point for any pathfinding investigation.

Justin Heyes-Jones -- has put up a great online tutorial on the A* pathfinding algorithm, describing how it works and why. He uses examples from his own implementation (written while working for Sony Psygnosis) to help explain how everything works, and provides some links to other sites on the topic. If you're not sure about this A* thing, this is a great place to learn!

Thomas Grubb has put together an interesting little A* application written entirely in Delphi. He says it was inspired by Bryan Stout's excellent A* article in the October/November, 1996 issue of Game Developer (which you can find here). It's not a bad implementation at all, and it's a bit easier to follow than some. If you don't already have your own pet A* algorithm, or if you just gotta see it in Delphi to understand it, this is a good place to start.

Djikstra's Pathfinding Algorithm is the subject of a very interesting page on pathfinding in general....

The D* Algorithm -- Researcher Anthony Stentz of Carnegie Mellon University wrote a very good paper describing a variation on the classic A* algorithm named D*. D* (short for Dynamic A*), D* allows for the fact that terrain costs may change as you move across the map and presents an approach for modifying your cost estimates in realtime. Fascinating stuff if you're always looking for ways to tweak your favorite pathfinder, and very useful for game environments in which the terrain can change. It's got its downside in terms of foricing recalculatios more often that most game developers might like, however, so you definitely want to think about the implications of this approach before you use it.

Maxim Berkoultsev is a Soviet researcher who's building an interesting toolkit to support graph searches, named the Graphic Search Library (GSL). As you might or might not know, the venerable A* algorithm is a type of graph search, and that means Maxim's toolkit could prove useful in all kinds of interesting ways to game developers.

The GSL toolkit is in C++ and includes a tutorial with examples. Source code is included, of course, and there's a discussion group for talking about problems and new features.

Worth checking out!

Pathfinding Theory -- Researcher Marksu Jonsson of Sweden has made available an extremely well-written thesis on pathfinding in general and the A* algorithm in particular. It's well written and easy to understand, with plenty of diagrams. I recommend it for anybody who needs a solid starting foundation in pathfinding theory.

Peter Norvig (one of the co-authors of the excellent Artificial Intelligence: A Modern Approach") has posted some well-done A* and general search code on his site, and it's well worth a look if you're new to the idea of pathfinding or just looking for a good implementation to borrow. There's a host of other AI stuff there too, and it's all well worth a visit.

PackHunter is a nifty tool created by the folks over at HRL (they used to be Hughes Research Labs but now they're just "HRL"). A 3D pathfinding technology they're trying to commercialize, PackHunter fundamentally uses "digital scents" to mark a trail for future searches. Kinda nifty. HRL is looking for ideas and partners for talking about commercialization of the technology, offering up a toolkit, etc.

We'll keep an eye on it from this end as we're in regular touch with the evelopers. If you're interested in PackHunter, swing by the HRL site (above) and check it out.

PathFinder2D is a pretty neat piece of freeware that can help you study A*, Djikstra, and BFS
There's a lot of stuff in here and it's worth some time to understand. Definitely recommended.

3D Terrain Navigation -- Bjorn Reese has put up an excellent page dedicated to 3D terrain navigation solutions of various types. Most of the page is devoted to robotics (which have to solve all the same problems as a game does, and which must do it for a multi-million dollar piece of hardware), though there is also a good list of recommended books and links to other game-related navigation pages. An interesting page recommended for anybody seeking pathfinding algorithms other than A*.

Bryan Stout wrote an excellent primer on path-finding in general and the A* algorithm in particular way back in the October/November, 1996 issue of Game Developer magazine. For reasons utterly unknown to me I somehow managed to miss adding a pointer to said article when I put this page together; it's the basic reference on the subject.

The A* and LPA* Algorithms are the subject of a series of pages by AI researcher Sven Koenig (who also put together an excellent page on Greedy Online Planning). Built in the form of a Java applet, it allows you to compare the searches performed by the generic A* algorithm with a refined method called Lifelong Planning A*.

LPA* is rather intriguing, in it uses an optimized search algorithm that allows it to reuse parts of previous seraches that are identical to the current search. This in turn results in faster solutions over time.

There are several papers on the site as well as pointers to source code and the like. Neat stuff...and a fun applet to play with.

Terrain Analysis is a technique used by the AI in the excellent Ensemble game Age of Empires for planning its attacks, city construction, etc. The whole thing is far too long and detailed to go into here, but essentially the game uses a variety of techniques to simplify pathfinding and make the AI smarter about where it builds outposts and organizes armies for attacks. Fascinating stuff and well worth a read for anybody thinking about upgrading their RTS game's AI!