Alright, that path caching bug would probably explain the mysterious teleporting dwarf.
If you look at future plans it's not as high a priority because I prefer to add new features than fixed bugs. It's still a very important part of the system because it has to support this kind of update for it to work continuously.
By the looks of things, smoothed waypoint paths are generally pretty good, although it does depend on waypoint placement a bit. They definitely visit less nodes than A* even when the path is suboptimal, and it will only pull farther ahead on a larger map.
Yeah it's generally very good though I need to improve checking ends of lines . Yesterday I made it try one more node when path is blocked but I didn't update the website (changed line 1816
). it made it take care of "teeth" better.
What's the efficiency of the smoothing algorithm?
Line drawing is O(n) with fast ops (no mult,div,mod,sqrt) while the walker is also O(n) so it is at most O(n
2) but i think it's closer to a O(n
2/2) because I couldn't find a worst case for O(n
2). It keeps shooting lines from size 2 to n until it's blocked or blocked twice then it will advance forward to the node at the end of that line and try again. so It's about the sum of counting numbers which converge to n(n+1)/2 .
I also tested the runtime using chrome.
my reference click is toggle node which does a complex "redraw".
I used this
maze :
t dt
toggle 32 0
a* 271 239
smooth 40 8
wp search 38 6
wp smooth 138 106
As you see it's generally not too bad. Javascript is still pretty bad for profiling stuff because it's slow. it has to interpet or runtime compile stuff and some complex operations like sqrt, multiply and divide take a lot less than their overhead while in reality . You'll still see that A* is a monster compared to path smoothing and wp search. The wp smooth seems a little excessive I do double smoothing (might not be necessary when I update code) when wp search is done. When I try that step by step ,wp search,smooth1 , smooth2, I get dt of 13+12+22 = 47ms respectively .
As I said the results are not great because it's a scripting language ... Yesterday I successfully killed my DF's FPS in a simple experiment by putting a few clowns in a very large cage .I approximate the complexity was 20*O( min(k^n,100000) ) I manged to get the game to 50fps at the very beginning.
This
example can show how waypoint based path caching can lower complexity . While the stored path is not optimal the smoothing algorithm fixes the path to be optimal. A* visits 472 nodes while waypoint path visits 30 that's a factor of 15.7~. A* has to do complicated stuff on each visit so reducing it's complexity would have great yield on FPS.
The main fix I think that would help DF is controlling worst case( no path to target) and even a waypoint can inform the pathfinder there is no path to any other waypoint which is enough for it to give up before killing your CPU in a node explosion search to nowhere.