BASIC

Author Topic: A* path finder (with diagonals)  (Read 1843 times)

Offline Wampus

  • Prof. Inline
  • *****
  • Posts: 1004
    • View Profile
A* path finder (with diagonals)
« on: 2011-May-26 »
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  ;)


Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2416
    • View Profile
Re: A* path finder (with diagonals)
« Reply #1 on: 2011-May-27 »
Impressive, well done!  :good:
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 3942
    • View Profile
    • Portfolio
Re: A* path finder (with diagonals)
« Reply #2 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?

Offline matchy

  • Prof. Inline
  • *****
  • Posts: 1537
    • View Profile
Re: A* path finder (with diagonals)
« Reply #3 on: 2011-May-27 »
Very interesting and a good reference for starting on precision path finding.  8)

Offline Wampus

  • Prof. Inline
  • *****
  • Posts: 1004
    • View Profile
Re: A* path finder (with diagonals)
« Reply #4 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.  :)

Offline dreamerman

  • Mr. Polyvector
  • ***
  • Posts: 123
    • View Profile
    • my personal website
Re: A* path finder (with diagonals)
« Reply #5 on: 2017-Jan-21 »
*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) 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.
« Last Edit: 2017-Jan-26 by dreamerman »
Check my source code editor for GLBasic - link

Offline WPShadow

  • Administrator
  • Prof. Inline
  • *******
  • Posts: 1630
    • View Profile
    • http://lostrevenant.blogspot.com
Re: A* path finder (with diagonals)
« Reply #6 on: 2017-Jan-24 »
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.
AMD X2 4600, 2 GB Ram, ATI X1950 XTX, XP PRO SP2: GLB Premium 10.beta_dingsi, <(´.´<) Kirby Dance (>`.`)>
http://lostrevenant.blogspot.com
alea iacta est

Offline dreamerman

  • Mr. Polyvector
  • ***
  • Posts: 123
    • View Profile
    • my personal website
Re: A* path finder (with diagonals)
« Reply #7 on: 2017-Jan-26 »
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.
« Last Edit: 2017-Feb-09 by dreamerman »
Check my source code editor for GLBasic - link

Offline bigsofty

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 2416
    • View Profile
Re: A* path finder (with diagonals)
« Reply #8 on: 2017-Jan-27 »
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:
« Last Edit: 2017-Jan-27 by bigsofty »
Cheers,

Ian.

“It is practically impossible to teach good programming style to students that have had prior exposure to BASIC.  As potential programmers, they are mentally mutilated beyond hope of regeneration.”
(E. W. Dijkstra)

Offline dreamerman

  • Mr. Polyvector
  • ***
  • Posts: 123
    • View Profile
    • my personal website
Re: A* path finder (with diagonals)
« Reply #9 on: 2017-Jan-29 »
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 :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:
Code: GLBasic [Select]
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...
« Last Edit: 2017-Feb-09 by dreamerman »
Check my source code editor for GLBasic - link

Offline erico

  • Community Developer
  • Prof. Inline
  • ******
  • Posts: 3942
    • View Profile
    • Portfolio
Re: A* path finder (with diagonals)
« Reply #10 on: 2017-Feb-01 »
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?

Offline dreamerman

  • Mr. Polyvector
  • ***
  • Posts: 123
    • View Profile
    • my personal website
Re: A* path finder (with diagonals)
« Reply #11 on: 2017-Feb-12 »
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.
Check my source code editor for GLBasic - link