So I've never actually implemented an a-star pathfinding algorithm. I have done pathfinding - back when I was in college I wrote a computer version of Steve Jackson's *Melee* for the Mac; it had a hex map and I worked on making it so orcs could find their way to you. It was a hairy, horrible algorithm that involved raycasting and seeing if there was an obstacle and raycasting around that obstacle and recursing. I mentioned what I was doing to Peter Akemann (who would later found Treyarch) and on the busride home from UCSD he sat with his head in his hands, thinking, and when we got back to the apartment he wrote an algorithm in about an hour that he called "blobmap".
The way blobmap worked is this: you have a two-dimensional array that matches your map. (Blobmap assumes your map is a two-dimensional array, and not an arbitrary network, which is one disadvantage it has over a-star.) You do a flood-fill in this two-dimensional array, starting at the destination you're trying to reach. You initialize the array to whatever the max value is for the data size you're using. You put a zero at the destination. You surround that destination square with 1's. And then you surround the 1's with 2's. And the 2's with 3's. Obstacles on the original map are left untouched in the array. So the flood-fill will naturally go around walls and terrain.
Once you've filled the map - it's completely blobbed - your character can simply walk downhill to find the fastest route to the destination. And you can do terrain costs with blobmap, too: instead of incrementing by 1, increment by the terrain cost.
Is it as fast as a-star? Probably not. Is it more or less memory efficient? I believe the a-star data will usually take more space than the array, but I'm not positive. I'm not entirely sure how a-star works, to be honest with you. And I'm not the only one: I've talked to more than one programmer who knows how to implement a-star but doesn't actually totally grok the underlying details. Which is one of the nice things about blobmap: it's easy to understand. The code is simple to read. It is *elegant*.
We've used blob map on RPG's with tactical combat (Magic Candle 2, 3, 4) and we even used it on Die By The Sword - hashing our terrain polys into an array of sectors and then blobmapping through the sectors.
Then we heard about a-star and we used that on all our subsequent titles. But I kind of miss blobmap. And if I was doing an RTS or a tactical strategy game of some kind, where the terrain is a grid or a hex-map, I'd use blobmap first and only switch to a-star if I needed the performance boost.