Phil was kind enough to point out a link on the forums about A* and I also did some extra research, and I realized that obtaining the fastest A* algorithm is a very complicated task that depends on your exact needs. While the core of the algorithm is always the same, the small implementation details and data structures that are used count a lot. So I would have to rewrite everything form scratch and I don't want to do that right now, since my A* optimization was just so that I could fix the issues I talked about last time.
But I did do one more round of optimizations: I optimized the central node container. The recommendation is to use a priority queue but I do not think there is a name for the thing I am using. Anyway, I won't bore you with all the numbers. Suffice to say, that in release mode, with 700x700 maps, the algorithm finds a path in 45-50 ms with any kind of map: empty, maze or just random. Nice improvement. I'll leave it at that. At normal map sizes, it takes at most 10 ms and the average time over the usual distances is 3-4 ms.
This is when I realized that there is a huge bug in my algorithm that has been there from the start. I tried to fix it, but the fixed A* is about 8 times as slow as the broken one. My algorithm shouldn't even work. After some testing and experiments, I think my algorithm degrades to a very quirky version of Dijkstra's algorithm. This is probably why the performance degraded so much when the explorable region was big with my less then optimal container implementation.
I really should prove my conjuncture that my A* degrades to a Dijkstra's, but with the current performance I won't bother with it now. I'll leave it to when I do not have anything else to do.
Hey, if you have an email or anything I can send you some of my A* stuff. It may have something in there you can use.
ReplyDeleteOne thing you could do to add a little more depth is once you start adding "personalities" to your dwarves, you could include some traits like intelligence. (similar to the traits in df like quick to anger, likes gold, etc.) You can then base the heuristic weight of A* on how intelligent they are. Slow witted dwarves (and or enemies) can use a more greedy version of the search algorithm by having a larger heuristic weight. Just an idea.
ReplyDeleteMy version might not be perfect, but it works so fast right now that I won't have any problems until I go 3D. So I won't replace the algorithm this pre-alpha, especially since it must be integrated with IPS.
ReplyDeleteBut I'll gladly look over what you have. It is never too late to learn!
The email is: dwarvesh.development@gmail.com
Is there available a source code or is it a closed source project?
ReplyDeleteHows everything been?
ReplyDeleteTo DierRe:
ReplyDeleteGenerally speaking, it will be closed source.
But I want to release the support library publicly, with headers and compiled libraries.
If anything goes open-source, probably the editor will be first.