The issue with JPS is proper/optimal implementation, and this is real task, this algorithm is highly dependent on array reading/writing speed. Some GLB / C++ optimization expert would write this code better, with proper byref / alias / pointer usage, as I don't know where it would get most of it. I've looked at several JPS sources in JS/C++, but it's hard to determine how fast they really are as mostly they don't have proper testing routines on normal maps...
For example JPS+GoalBounding
, everything looks nice, yet included maps are only 100x100, and output results times are strange, to compare with anything and it requires map preprocessing (analyzing that SC map that's included with my source was 4hours long and final file is 30MB
). Other algorithms could be interesting, but many of them requires some map preprocessing, or significantly much more system memory for precomputed values.
It would be nice to be able to compare results from our routines with other codes. That's why added little benchmarking function, it's using *scen files (movingai.com / HOG2) so this is some kind standardized way to benchmark path finding functions (result printed as StdOut).
Nonetheless I did some changes in BinaryHeap, ALIAS used in few places and other simple optimizations, those are test with GLB generated 1000 pairs start-goal at medium-long distance on SC_map, times in seconds:
previous - * - current version
350.0 - Classic - bugged
55.0 - Flood - 24.0
25.0 - BH - 15.6
2.9 - Region - 2.4
34.0 - JPS - ~34.0
So there is still much to improve without inline stuff.
I've also added modified version of JPS - 4 way (horizontal + vertical movement) optimized for mazes (so also room maps) but can be used also on other maps, it requires a little preprocessing (it's fast as only calculate basic jump-stop points), and during run function is mostly doing simple checks like 'stop here?' no, ok jump to next tile. To test it, it's best to move only starting point, as target point need to be neighbor for some blocked tile, as this algorithm is mostly bouncing from walls.
It would be nice to see if anyone has some other path finding algorithm implementations, so we could do gather all of them in one place :-)
Attached project includes also previous version of functions, sorry for not polished code and ugly comments :]
ps. Oh yes DarkColony was great game, sad that it wasn't so popular as other rts games from that time...