I've recently gotten into path finding (especially via A* and Dijkstra's algorithm, which is essentially A* without a heuristic) and I find it very interesting and fun! My first implementation was extremely buggy and slow. I've gone to make it work correctly first, and now I'm optimizing it to work for extremely large areas. This is as far as I've gotten: 1) using an std::multiset of scored nodes for the open nodes list. Ideally, if a node is already open with a worse score, one should remove it and add the version with the better score (or just update the score and parent node). However, this means that the node needs to be found in the open list first, which involves at least a binary search. Therefore, I just add the node without considering whether it might be in the list already - if it has a better score, then it'll be processed first and then closed, so when the duplicate with the worse score gets processed, it'll already be closed and therefore skipped. 2) dropping the closed list idea and replacing it with a cache of the graph (as a hashmap or an array) with two states - unknown, and closed. Checking whether a node is closed then becomes O(1), and so does closing the node. There is no need to check if a node is open because of 1), it only matters if the node is closed or not. Instead of creating/destroying or clearing this cache every time I find a path, I just increment a counter variable for the closed state on every call. For example, this call has 1=closed, 0=unclosed. The next call will have 2=closed, <anything other than 2>=unclosed. This will overflow after 4294967296 path-find calls, which is when we can clear the cache and start over. 3) dropping the score lists. The F score is just G + H, so no need to store it. The G score is just the parent's G score + 1 (or whatever the cost is to move to the current node). The H score is just the heuristic. 4) currently using an std::map for node->parent. I think this can be optimized by keeping the parent inside the node itself, therefore removing the search for the parents (even if it's O(log n) or O(1)) Any comments/suggestions/discussions? Stuff that can be done differently, your own experiences, etc. Discuss. (heuristics for A* are a whole other topic, but free to mention them as well) Edit: I just read about the flood-fill optimization to avoid worst-case scenarios, it's a very neat trick. However, I'm mainly interested in optimizations given that there is a path from start to finish.

If you're working on optimizations for situations when paths are know to be possible, then you definitely should be using A* rather than Dijkstra. Multiply your heuristic by a constant factor to speed things up a bit in the best case; it "drags" the search towards the target basically. The second biggest speed up you'll get is by using a hierarchy.

You can use a std::heap to maintain a sorted list. The standard implementation is more than adequate. Avoid anything like extra lookups and hash maps, and try to maximize objects that remain in memory, e.g. by storing all the data together like parent node. Also see if you can get your hands on the evaluation version of VTune or some other profiler.


There's loads of C++ a star code on the internets that's really fast. Do you know about AI Wisdom and Game Programming Gems?

[Edited by - alexjc on December 28, 2009 3:10:15 AM]

Quote:Original post by alexjc
If you're working on optimizations for situations when paths are know to be possible, then you definitely should be using A* rather than Dijkstra.

Of course, Dijkstra explores too much in open spaces.

Quote:Multiply your heuristic by a constant factor to speed things up a bit in the best case; it "drags" the search towards the target basically.

Yup, this is called tie breaking, right? My only problem is that using a tie breaker > 1 makes the heuristic non admissible, and the paths around simple objects don't really look as good (complex paths don't really show the error). Does using a tie breaker < 1 also have speed benefits?

Quote:
You can use a std::heap to maintain a sorted list. The standard implementation is more than adequate.

Ah, yes, I looked into that but haven't tried it, yet - currently I'm just using a multiset.

Quote:Avoid anything like extra lookups and hash maps, and try to maximize objects that remain in memory, e.g. by storing all the data together like parent node. Also see if you can get your hands on the evaluation version of VTune or some other profiler.

Got it.

Quote:Do you know about AI Wisdom and Game Programming Gems?

Now I do [wink]