AS3 A* Pathfinding Engine (v1.0)
She ain’t much to look at, but she sure do work. Honestly, I’m not exactly sure how it works. A recursive function is a fierce and fickle mistress.
Actually, I do know how it works; I was just startled at how fast it came together. There are a lot of great resources on the subject, as well. Here’s the one I used:
And if you’d like to play around with it, just click the image.
The real problem I have with it is that it’s pretty short-sighted. Units don’t see a wall until they’re right on top of it. Obviously this makes sense for a lot of units- sometimes you don’t know where you’re going until you get there. But I think I’m going to try some smoothing algorithms to remove some waypoints and get those paths a little more natural-looking.
Tags: , A*, Actionscript, Pathfinding
March 22nd, 2008 at 10:20 am
That’s a pretty cool little algorithm. It seems to find a fairly efficient algorithm. It takes awhile, though. Won’t that really bog down a computer when you’ve got 50 guys trying to find a path at once? Perhaps you should analyze if there are some wasted operations. Even if there’s just an addition or a small loop–inside a recursive algorithm, it adds execution time quick.
March 25th, 2008 at 3:20 pm
Unfortunately, smoothing it out will take even longer. I’m thinking about spreading execution out across multiple frames. That way it shouldn’t freak if fifty guys do try to pathfind at the same time.
If I can ever incorporate your raycast thing, the smoothing would be a walk in the park.
March 27th, 2008 at 1:57 pm
That would be pretty cool. You could also have them follow one another–though a single file line of soldiers isn’t much use when you’re trying to surround an enemy… I can do a quick raycasting write-up if you’d like.
March 27th, 2008 at 4:45 pm
They probably will end up following each other to some extent, just because they’ll all find similar paths from nearby locations. I’m thinking of introducing “Formations”, though. You’ll select several units and click a destination, and they’ll just find their own way there (single-file, perhaps) and assemble back into their formation when they get there.
June 13th, 2009 at 1:41 am
(I know, I’m responding to an old post)
You’re finding a path on a finely divided grid and then smoothing the path. Unless your grid spaces have varying movement costs, you’re wasting a lot of time in A*.
Note that all the paths will go around corners. One way to speed up A* on your maps is to store only the corner positions as A* nodes. Reducing the number of nodes not only greatly reduces the amount of work A* has to do, your paths will also be smoother — they will go directly from corner to corner.
It can be a lot of work to reduce the map graph in this way, but if you have lots of paths to find, you can save plenty of time by preprocessing in this way.
I have a little bit about this topic written here: http://theory.stanford.edu/~amitp/GameProgramming/MapRepresentations.html