Attached is code for an A* path finding algorithm and example test. Although its no match for the speed of FINDPATH it can do diagonals. It also won't violate the edges of blocks like some path finders do. Wrote the code a while ago. Thought someone might like, need or find it interesting.
The example code compares speeds with the FINDPATH command and another pathfinding routine I found on the forum by Kanonet. It runs the path finding algorithms 60 times each before comparing time taken. It then shows the actual paths found on a map as a demonstration.
Sorry the global variables the routine needs aren't separated out more clearly. I'm sure if you want to use it for your own stuff you'll work it out though. Would make a good match with the line of sight code I wrote before ;)
(http://i904.photobucket.com/albums/ac242/wheeethefibble/webpics/astarpath.jpg)
[attachment deleted by admin]
Impressive, well done! :good:
really nice, although I can´t make much out of the code...
Is going by the woods allowed? is there such a thing as a time penalty for non-open terrains?
Very interesting and a good reference for starting on precision path finding. 8)
Quote from: erico on 2011-May-27
really nice, although I can´t make much out of the code...
Is going by the woods allowed? is there such a thing as a time penalty for non-open terrains?
At the time I didn't envision making the code available so its not as clear as it could be. Time permitting, of which I have very little nowadays, I would want release it as part of an open-source turn-based strategy game. I would more carefully comment it in that case.
Going by the woods is allowed but there is a time penalty. It costs twice as much as open ground in the given example, i.e. is twice as slow. Sometimes its worth it to cut corners, other times better to go around. :)
*bump*
I'm porting some of my old routines to GLB, more specifically path finding code that was intentionally written for an rts engine tests. And from curiosity to get some comparison with other algorithms available here I made some changes to my lib to be compatible with Wampus test code.
At now my mini library consist of 2 working path finding functions: FloodFill and A-star with BinaryHeap, there is also classic A-star but it's totally unoptimized for GLB :D
Both functions are little simplified as my project doesn't most of that cost based calculations, yet still you can tweak them to be more effective in that manner, also they do diagonal checking, but you can disable it to get more speed, both functions are using global map arrays but they clean all garbage.
Generally such small map isn't perfect place to test path finding, yet still it can give interesting results ;-) FloodFill is the king of small maps :D especially without diagonals checking - in terms of speed.
For larger maps like 256x256 I had also sector/region based A* version that on average was 10x faster than this BinaryHeap code...
Edit: I needed some app to test routines on larger maps so I modified Kanonet's original code (from HERE (https://www.glbasic.com/forum/index.php?topic=5450)) added Wampus and my code to compare, also nice map2spr loading function, so you can check some things.
I will look into JPS implementations as it would be best for my needs.
Very nice!
I've to test which pathfinding routine is the best for my running project.
I will give you a feedback, when I reached the point to test it.
I've added region based path finding, and very simple version of JPS (yet it isn't finished), generally all functions are useable, so you can compare them on different maps with few settings. That's good start if someone want's to write another custom path finding function.
Beside that there are some changes in main functions, like two variations of randomly generated terrain cost for loaded maps.
Of course in every implementation there is a place for additional optimizations, so results shouldn't be taken as final/definitive.
Goof stuff, always a fan of decent path-finding(Its the basis of so many games) algorithms. Interested to see how JPS makes a difference to the paths and efficiency.
BTW Dreamerman, I see your avatar pic is a Reaper from Dark Colony, one of my all time favourite RTS games. :good:
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 (https://github.com/SteveRabin/JPSPlusWithGoalBounding), 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 :D). 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...
I gave it a go, great work there!
I was always interested in this post and code, quite the thing!
While I don´t have use for a path finding routine, I did a bit of self-finding routines some time ago.
It is different cause the agent has a field of vision and its path must happen within it, he only knows the coords of the goal, not the whole path.
I was researching a way to make agents behave close to humans when they want to get somewhere but have to deal in real time with what is on the way and what they can actually see.
Here is an old video. All GLB...always.
The real action is after 00:20.
http://youtu.be/28qt9K0WUDI
edit: can´t we add videos anymore?
Update. Some little changes, generally fixes/optimizations. BinaryHeap code is much faster now (2-5 times in 10kk sorting elements scenario) yet difference is almost not notable with small open list for most maps. I don't know if there is chance to tweak code to get much better performance in pure GLB, of course for different maps other heuristic may be better, other cost values and so on, but that's 'default' values for normal maps. Real speed gain could be obtained with use of c++ inline, and normal arrays not vector class. But those functions should be sufficient for most scenarios. On small maps speed difference can be unnoticeable, but on real game maps you can easily see advantages of some implementations (either speed, or better smoothed paths) so you have some variety of choice.
@Erico: Yeah, for proper human behaviour simulation path finding code should consider field of view and other restrictions, this could be nice demo app. But there is many issues with that, for example if some agent travels from A to B, he discovers some parts of map, does other agents see what map part were discovered, as from some point and many iterations / start-goal pairs most map would be discovered so depending on choosed implementation path would be similar to standard A*, or treat each path finding task as separate and map tiles should be always marked as undiscovered, and so on.. Many interesting ideas and things could be done with this, yet for most games simple path finding is sufficient, even today most games don't use 'discovered' flag for map tiles as units know from start what path is best, all to simplify/speedup searching, and make game more comfortable to player, so he don't need to select each way point manually.
It would be nice to see some complex path finding demo with many agents made in GLB.
Thanks for the mail, dreamerman! Sadly, your download link seems to be broken?!
Ah yes, forgot about that, forum was move to other hosting last year so many attachments were broken during that or something like this..
Here is working version, checked, compiles with latest GLB, yet some my routines may be not so efficient as they should be, and You need to fix font size, as for some reason it's to large now.. :-)
Top ! :enc: !
Yep. Awesome stuff!
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?
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...
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 ;)
Fixed bug in my region based pathfinding, some small changes in few functions, so main functions are stable.
Current benchmarks: 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.
Very interesting, thks for the update.