A* path finder (with diagonals)

[erico]

Yep. Awesome stuff!

[dreamerman]

From what I remember my standard A* has some issues, and JPS wasn't perfect.. With proper usage this could handle hundreds of moving units, and not interactive maps can use region based optimizations. hm.. better benchmark is needed, with proper map view like in rts games and moving units.. I will revisit this for my upcoming project :-)

ps. any one knows some nice free sprites (not rip-offs) that could be used in next benchmark/showcase project?

[dreamerman]

Word about that JPS, code looks ok, but it all goes to pre-calculation and proper use of jump flags, for maze maps it will be good but for large maps with many open spaces region/HPA would be still better. In this update I've added better visual representation of real case path finding - map view like in old 2d rts games with moving objects that represents units, using my A* routines (by default it's DarkColony map + 1000 units). This can give some idea what are possibilities, and remember that this is simplest implementation - not optimized, specially drawing stuff. Also path finding can be further optimized with features specific for game, mostly it goes to JPS and other map pre calculation techniques. Proper 'found paths' manager should be also written, so it would cache or store paths for futher use if possible and so on.

Beside that project includes benchmark-ing function with start-target pairs - *scen files, details described in source.
btw. I compared results from GLB with my original source in FreeBasic and they are quite similar so even such implementation isn't useless ;]

Probably further changes that I will make in source will be specific to my project, so I'm not sure if any major update will be posted.
ps. press 'Tab' to switch draw mode.. results from screenshot are with BinaryHeap A*, region based is faster...

[SnooPI]

Thanks Dreamerman.

For the moment it is not the case, but later it could help me for a project in progress.
That day I will not forget to send you my version if I ever improve it or find bugs 

[dreamerman]

Fixed bug in my region based pathfinding, some small changes in few functions, so main functions are stable.
Current benchmarks:

Code: (time in miliseconds) [Select]

AcrosstheCape 32room_000 maze512-1-0
start-goal pairs 294 pairs 213 pairs 241 pairs
FINDPATH 90310 7067 55384
Advanced_FindPath 86456 44920 28732
FloodFill 6364 3199 10365
A* BH 4119 1251 20267
JPS-4Way 1255 314 3013
JPS-SD 450 127 703
Regions 448 316 1586
As for now I was looking for best choice for partial changing maze style map, something between rooms/maze - like in dungeons / roqulike based games. So I made some changes in JPS function - using 1D array and focused on target kind of maps - it's called JPS-SD.

There are some interesting concepts, but generally, higher/more expensive pre-calculation = better final solving speed. Yet such pre-calculation sometimes make it harder / more expensive when used on dynamic or part-dynamic maps - one path may be currently blocked by obstacles - for example closed doors and so on.. In general for not-changeable maps with JPS You can use pre-calculated jump length so no need to check all tiles during jumping, BinaryTree code could be also little altered specially for region based pathfinding. Maybe in GLB some better code can be written, but to have even better results pure C++ should be used with pointers and other sorting algorithms like combination of buckets and fast lists. Still this should be sufficient for most use cases.
If any one is interested in additional info You can check links included in source, and one really interesting implementation is this: https://mikolalysenko.github.io/l1-path-finder/www/  JS code, but it's really fast, yet it isn't easy to read. It's using 'landmarks', some kind of similar to regions but more advanced.

@SnooPI
Feel free to change anything, and I'm curious to see any additional pathfinding algorithms :-) All other implementations, tricks and optimizations are welcome.

[SnooPI]

Very interesting, thks for the update.