Well, I've been working on AStar this week. Last time I talked about switching to a dense waypoint mesh. This seems like a good choice so far.
I've been using some free AStar code from the net, which keeps crashing on me at certain points, so I've been reading numerous good tutorials on the subject in order to get ready to write my own.
It's amazing how, with so much code available on the net, very little can be directly used in a project. There are just too many assumptions and tradeoffs that must be made to make something usable for a certain purpose. And building these tradeoffs into the interface often serves to obfuscate the simpler uses of the code.
For my project, the map size will be up to about 128x128 in size, or 32k nodes. This can have implications regarding how you store the open & closed lists.
For the open list, you are inserting ~8 nodes for every node that you visit, so insertions should be relatively quick. But, you also need to find the cheapest node at each step in the algorithm, so having something sorted seems like the right approach.
For the closed list, the group of things you've already visited, you just need a quick way of checking if you've come to a node already. There are also cases where you may want to remove something from the closesd list ( rare ), but you need to check every node to see if it's on the list already ( often ).
The code I was using used the std::heap functions on a std::vector for the open list, and a linked list for the closed list, and seemed pretty fast.
A Few Hours Later :
I have since written & tested my own implementation. After trying to digest the std::heap functions, I'm not sure what advantage they have over storing the open list as a std::vector, and calling sort before you need the cheapest element ( stored at the end of the array ).
Tomorrow I may try the heap functions again to see if they are faster, but I'm not super-worried about it right now.
You can make some more optimzations if you have small map like I do, like storing the closed list as a grid or an array, for fast lookup, insertion and removal. Of course, if you have more than one path search in effect at any one time, you need a separate grid for each search.
My code is structured around the idea of an object called AStar_Search. You can call it with a maximum # of nodes to try, and it will quit early, while saving its progress, to be restarted later. For my purposes, A star will be used mainly for relatively short paths. The AI will use it to travel from room to room when on patrol, and to follow the player. Of course, the enemies won't have perfect sight of the player at all times, so if the player goes offscreen or behind something, they will path to the last place they saw the character, which by definition must be closeby.
So, I won't spend too much time optimizing this any further, as it seems to run well, and most importantly, doesn't crash like the old a star code! ;)
One of the cool tricks I added to my a star cost function was a penalty to any nodes that were at an edge of the walkable area. This is done by simply penalizing walking into any node that doesn't have all 8 valid neighbors. This tends to keep the enemies from hugging walls and bumping into corners. I temporarily took out true walk-checking from version of the navigation system, which I will add tomorrow now that I have the new capsule collision code.
Here is a shot of the path found and the closed list ( all of the nodes checked ).
Here is a shot of my temple level, with a round pool of water, which was made with the new hemisphere morph tool.