A* pathfinding stress test
Community Forums/Showcase/A* pathfinding stress test
| ||
| Hi ! I've been playing with A* pathfinding the last few days. I know that there are several entries in the code archives but I wanted to write my own to understand it well and eventually make further improvment in the future. So it's A* pathfinding written in Blitz3d, using Manhattan lenght heuristic, basically, the simplest. I tried euclidian heuristic lenght too but it appears to be slower in most cases. The whole pathfinding stands in only one function and some declared variables/tables to make it easy to use as a library, I'll share it when it's completed. I wanted to show some screenshots of a "stress test" to show capabilities and limits. The areas in blue are all the pixels that have been computed to find the path. So, the "pathfinding time" is only valid when they are not displayed as the drawing function of these blue pixels are in the pathfinding function. As you can see, the map/level is 512*512 cells/pixels, wich is quite big for such an algorythm. First test, a huge and complicated maze. Lots of cells are computed but I've been surprised by the calculation time.   Second test, large barriers between start and end point. This is the weakness of the algorythm, especially if "curves" face the start point.   But in this case, if I reverse the algorythm (switching start and end points), it is way faster. If only we could know when to reverse... Maybe with precomputed passes, I'll see that later.   Third test, hmm just a random one, but it shows that the algorythm doesn't find the shorter way (dashed line, approximatively), it finds the fastest way to compute. I didn't test euclidian heuristic in this case yet, or another approach but it's probably the reason, Manhattan lenght is approximative (but fast).   I don't know at all if it's faster than other entries, but i'm quite satisfied with it. My CPU is an I7-3770 wich is quite fast thought. Now it's time to implement "jump point search", wich is a method to make A* pathfinding faster by reducing drastically the number of cells to compute. Sorry for my english and the amount of ("some") screenshots ;) |
| ||
| Well done ! :) You may be interested in this discussion : http://www.blitzbasic.com/Community/posts.php?topic=97751 |
| ||
| Interesting! |
| ||
| Here is a little video to see it in motion : http://www.youtube.com/watch?v=OQbRFFZd6h8 Thanks for the link RemiD, some ideas will be useful to decrease the CPU cost for "realtime" applications. BlitzSupport, thank you for Blitz3D, it's very useful and powerful. |
   |