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 Expand

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.

[dreamerman]

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

Bump cause of the above reason, needed some side project to take a breath from a 'proper' game project so I played with this a little and made a showcase video in popular 'Shorts' format:

[SnooPI]

Awesome Dreamerman! 
A good idea would be to use Warcraft 2 Sprites for your next demo 
I really believe in the potential of RTS games in a retro 2D style.

[nabz32]

That looks really performant, very nice job dreamerman👍.
Would love to experiment with this algorithm myself too, I think I`ll take a look at it tomorrow as well

[Kitty Hello]

Try to run the code in parallel, when you have 10000 units. Search for "hawkthreads". It's built into GLBasic, and there's a wrapper for the API.

[dreamerman]

That was just a short side project, all calculations done on single thread and still almost 60fps (of course map is small) but it's unachievable for let's say many popular game making solutions Generally standard  A* is good for turn based games, RPG, or when you have few units, as when you introduce proper collisions/tile occupy state there are a lot of problems that you need to take care on. And popular solution is to use regions/portals/waypoints pathfinding globally and fast A* locally when traveling between portals, or when previously calculated path is blocked - so the unit need to find some other way or wait path to clear and so on. And it would be best to do this on separate thread so this also have some requirements - local map data for pathfinding thread... And all that is a 'little' more work that such small project. Hopefully I will revisit pathfinding in this year to tune JPS/regions for proper game.