Sorry your browser is not supported!

You are using an outdated browser that does not support modern web technologies, in order to use this site please update to a new browser.

Browsers supported include Chrome, FireFox, Safari, Opera, Internet Explorer 10+ or Microsoft Edge.

Code Snippets / [DBP] - A-star with path simplification

Author
Message
noobnerd
8
Years of Service
User Offline
Joined: 30th Nov 2010
Location:
Posted: 24th Mar 2013 15:55 Edited at: 24th Mar 2013 18:28
Hi there, i wrote this A* like pathfinding system recently and it features a simple system that reduces the amount of waypoints by removing unnecessary ones. its pretty fast and has a modifier that defines how fast or slow (unnaccurate vs accurate) the function will run. the demo needs a2plugin and maybe matrix plugin. it works with very big and convoluted maps assuming you dont have the detail setting too low (lower number = more accurate )



real A-star is probably faster and more accurate but this is what i came up with (based on previous knowledge of A-star)

[edit]
improved the code substantially, it now reports the true fastest route very often and quite quickly. The grid in the image is a 160x120 grid and it has very unusual and quite A* unfriendly geometry. the path took 2.2ms to find and it is the fastest possible one in that grid. suboptimal paths (2% slower) can be found at 1.8ms. the path spans a length of 206 units (diagonals count as 1.415) while it only consists of 66 waypoints.

Attachments

Login to view attachments
Phaelax
DBPro Master
16
Years of Service
User Offline
Joined: 16th Apr 2003
Location: Metropia
Posted: 29th Mar 2013 07:34
A fairly small amount of code for what appears to be fast and effective pathfinding. Nice work.

"You're all wrong. You're all idiots." ~Fluffy Rabbit
noobnerd
8
Years of Service
User Offline
Joined: 30th Nov 2010
Location:
Posted: 1st Apr 2013 14:47
thank you

Login to post a reply

Server time is: 2019-10-19 10:39:24
Your offset time is: 2019-10-19 10:39:24