If you’re writing a game that incorporates both a terrain of some sort and enemies that walk around, the chances are you’ll need some version of pathfinding to control the enemy movement patterns. The thing is, pathfinding is serious business–it’s not easy to grasp. To make things worse, there aren’t many good pathfinding resources–most of the articles that turn up on Google and such only serve to confuse you further. That’s why I’ve taken the time to compile this list of pathfinding resources that I’ve found to be actually helpful, as opposed to confusing or just plain wrong. Enjoy!
This site is an excellent compilation of articles on A*. It’s a great resource, but the articles it contains aren’t exactly for beginners. That said, I refer to them all the time–they’re not limited to just pathfinding articles. There’s stuff in there about pretty much every aspect of game programming.
This is really an excellent tutorial. It explains the concepts behind pathfinding very clearly and is pretty easy to grasp. If you’re just getting into A* pathfinding, this is definitely the article for you.
Wikipedia’s article is also quite useful, and this page has a handy language-agnostic implementation of pathfinding.
Another great article. This guy uses a cat to illustrate his point, so kudos to him for that (I’m a big fan of cats).
I like the pseudocode in this article and there’s a useful discussion about actually implementing A* towards the end of the article–what you’ll need as far as abstract classes and interfaces go.
Justin Heyes has written an excellent implementation of A* which can be found in the above repository. Although it’s in C++ it clearly illustrates the finer points of the algorithm and how to interface with it.
Here’s yet another version of the pathfinding algorithm in pseudocode, in case you didn’t “get it” from any of the previous 7 articles. The explanation is short and sweet and the pseudocode fairly readable. There’s also a link to a version of A* written in LISP at the bottom of the page, if that’s your thing.