What about the competition?
Ofcourse, there are some other really good Flash-Astar-implementation out there. I’ve heard from a lot of people that Zeh’s implementation is about the fastest implementation on the Internet. Logically, I put the two up for a little speed test…
The file is very basic so that the flash player doesn’t waste any time on graphics. (No, the fact that I can’t design has nothing to do with it 
).
[kml_flashembed movie=”http://dauntless.be/blog/wp-content/uploads/2006/04/The_Competition.swf” height=”240″ width=”240″ /]
Click anywhere on the map to set the startPoint and click again to set the endPoint.
If you click around a bit, you’ll notice that Zeh’s is faster most of the times. Zeh’s implementation is faster on the short paths, while mine is a little faster on the tougher paths.
So… I made a map with a little more spice to it. I let Flash create a 40×40 map with all random costs from 0 (wall) to 4 (highest cost).
[kml_flashembed movie=”http://dauntless.be/blog/wp-content/uploads/2006/04/The_Competition1.swf” height=”460″ width=”400″ /]
As you can see here, my A* is way faster then Zeh’s . I’m not saying his implementation is bad (not at all!), it just depends on what you are going to use it for. If all your maps are small and low-cost, you should take his A*. If your maps are larger and more CPU intensive, you’re probably better off using mine.
On a side-note: There’s also a little difference in what the implementations are capable off. Zeh’s supports Clipping and No-Clipping while mine supports Clipping, Semi-clipping and no-clipping. If you fill in a wrong value in my A*, you’ll get an error message (trace), while Zeh’s returns ‘null’ as the path. (This may look like nothing, but every conditional in the engine costs more microseconds!). My A* also supports a different cost for going diagonal and going vertical/horizontal. (edit: Zeh’s implementation also supports a different cost for diagonal and vertical/horizontal. They are defined as constants inside the prototype. Sorry for this mistake)
Finally: Zeh’s implementation is a lot older and still written in AS 1.0 while mine is AS 2.0. This means you can easilly extend the Tile class (which has a built in ‘notify()’ method when the tile is in the found path) and you can quite easily addapt it to your personal needs. (The source files will be published shortly).
April 10th, 2006 at 9:18 pm
Very nice! I tought it would lagg, when im on an such pc. But it is very nice an it doesnt lagg at all. Great work
April 10th, 2006 at 10:36 pm
hahah that showed tonypa lol
April 11th, 2006 at 12:35 pm
Hahaha
, Jeroen you are the best 
Have they already seen this ?
Greetz Michiel
April 11th, 2006 at 12:46 pm
I HAVE posted it on flashkit AND kirupa :).
April 11th, 2006 at 1:17 pm
Hey - congrats on this… well done.
I’ve also had a go at A*, and whilst I’m very sure that I’m not up to the standard that I see on your site, I just thought I’d show it off.
The paths that mine finds are not always the most pretty… it seems to hug the walls a bit. Any suggestions here would be great.
So - have a quick read through the instructions and then have a go. Hope my web host can handle a few extra visitors
my A* attempt
Cheers, and thanks again…
MB
April 11th, 2006 at 2:27 pm
Perfect dauntless! That’s all I can say(unless you think that fantastic is better then perfect)!
April 12th, 2006 at 10:58 am
Well done! It really impressed me.
The numbers that you show (Dauntless: Zehn: )
Is it the delay time in miliseconds? Or am I wrong?
April 12th, 2006 at 1:39 pm
You’re right, Davy: The time behind the name is the number of miliseconds it took to find the path.
May 1st, 2006 at 12:31 am
Dude, the name’s Zeh, not Zehn.
Where did you get that from?
Anyways, good class. In this day and age, a proper AS2-drive A* class is way better than using prototype-based stuff.
Two things, though, regarding my code:
1. The code returns ‘null’ when a path isn’t possible because it’s its way of pointing the error. You need a real-time way to know what’s going on with the path, more than a trace() that would only be used when debugging. I’m not sure what you’re pointing at when saying an IF costs more, but I think one IF to see if there’s actually a valid path when asking for one is something mandatory on any case.
2. The code takes different diagonal and h/v costs. It’s just that they’re used as constantes - they’re on the code itself. There’s a few options on the code itself (ie, whether it should actually go diagonally) so you shouldn’t see my code as a do-it-all class but rather as code that can be modified for different needs. Even the parameter input (a table) isn’t the best thing for everybody - in fact, most people will need A* classes deeply tied to their own code, not something completely separated.
One last detail: my class goes from tracing the path from the origin point to the destination. Some A* implementations trace it from both the start point and the end point at the same time - it’s faster on most times because it will take way less ramifications on larger and ‘less limited’ areas, like your second example. I don’t know if that’s what you’ve done on your implementation, but if so, it’s fundamentally the best A* approach. If not, it’d make your code even faster.
All in all, though, like I said, AS2 (and now specially AS3) is the right approach to these things (don’t forget my code is quite old).
May 1st, 2006 at 9:36 am
Sorry about your name Zeh, I’ll edit it right away !
About point 1: In my next release, I’m planning on seperating the search process over several frames. That way, I can also use the EventDispatcher and dispatch an ‘onError’ or ‘onComplete’ . That way, it’s up to the developer if he wants to use those errors in his game or not.
About point 2: What do you suggest to be the most flexibel way to fill the map ? (I’ve also edited my post about going diagonal / h - v ).
And about point 3: I don’t have a 2-directional search but I’m planning on putting it in. I just have to do some research about how it works exactly :p
And Zeh, how did you find this place ?
May 2nd, 2006 at 4:51 am
Events like that would be great; good insight. Having this kind of immediate path retrieval (on one single loop) is not good for big maps so having the ability to split it between frames would be really smooth for real (and bigger) games. I don’t know how it’s implemented on your current class version, but my point was that the null thing was the way my code used to acknowledge that there’s no available path - not exactly an error, but a choice.
2 -> Fill the map, as in the map parameter? I don’t know. This is a decision that comes down to how each developer is taking your solution - the way I did my code was for one very specific solution, thinking “well, I’ll make this thing public so anyone can just change it to fit their needs”. As in, I expected people to change the way it actually reads the data.
Now, with a real class, things should be a bit smoother (at least syntactically) and more abstract, so it comes down to thinking on how each person can integrate your solution to their code seamlessly without creating this huge interface between them that would only slow thingsa down. How? I don’t know, I’ve honestly never thought about the subject much. In my case, I figured people would just get the core of the thing and reuse.
And I found the place because I was reading the referrals for newsfeed.fatorcaos.com.br. I had actually seen your site before but not that specific post. Good blog.
May 2nd, 2006 at 4:51 am
Oh, and thanks for the fixes.
May 3rd, 2006 at 8:42 pm
Your welcome :).
And chances are you have never seen my site before… This is one of the default WordPress themes… So there are probably a few thousand sites like mine …
As soon as I find a designer willing to help me, i’m changing it ;).