Last post talks about a stupid tris game and while I was writing that code I've thought about a way to create a better script (more intelligent).
Since tris game, as many others, is based on a grid, I've looked for one A * JavaScript implementation but hey, I didn't find them !
I remember Alessandro did a path finder for ActionScript and as you know AS is ECMA and its A Star implementation should work on JavaScript too.
However, Flash has a dedicated virtual machine (Flash Player) and its source is byteencoded, then AStar is fast enought but not so fast used with JavaScript.
That's why I've decieded to create a generic AStar function quite optimized for JavaScript (but it probably should be better too) and usable with ActionScript 1.0 too.
Here there's a simple application example while in this page you can read about the function and view the source code too.
Example uses a MemTronic version to reduce AStar size into 1,4 Kb.
Finally, this is the "old" Alessandro implementation where you can find more informations about A Star algorithm :)
behind the design
My JavaScript book is out!
Don't miss the opportunity to upgrade your beginner or average dev skills.
It's just another information:
ReplyDeletemy AStar implementation works about 4 times faster than Alessandro prototype with Flash too but my AStar implementation doesn't work with ActionScript 1.0 and Player 6 (I need to do more debug), works correctly with AS 2.0 and player 7 or greater while Alessandro prototype works correctly with AS 1 and Player 6 too :)
And now, Go ahead with D* :
ReplyDeletehttp://www.frc.ri.cmu.edu/~axs/
only when web will be a tridimensional interface :D
ReplyDeleteOk guys ... AStar function is now final version.
ReplyDelete1 - compatible with Flash MX and AS 1.0 too
2 - faster with JavaScript and with AS1.0 too
3 - optimized for crunchers or compressors
4 - about 5x faster with ActionScript 2.0 and its dedicated strict version:
http://www.devpro.it/as2_id_138.html
Hello :)
ReplyDeleteI've done another example using AS2.0 version:
http://www.devpro.it/examples/astar/flash.html
Now Flash developers have another fast function, and not "only this one"
http://www.gskinner.com/blog/archives/2004/05/pathfinder_enha.html
( I didn't find other AStar fast implementations :( )
Hi to everyone! I've been trying out things with this astar implementation and it works really well. I was however wondering if there is someone who has used this code and extended it with weighted paths? To clarify what I mean: Say that all the squares in the grid have a weight that can differ and the search will try to find a successful path from point A to point B that has the least weight value based on the weights of the squares. Think of it as a game where movement on roads costs less than movement in mountains? Maybe there is another type of algorithm that is more suitable, so if anyone can provide some input to point me in the right direction I would be ever so thankful.
ReplyDeleteIs this implementation deterministic? If I run it twice can I expect the exact same path back???
ReplyDeleteyep, if the system (grid) is the same, each path will be found in the same way so twice same result
ReplyDeleteThanks...
ReplyDeleteI am using your algorithm in an HTML5 game I wrote... http://www.adityaravishankar.com/projects/games/command-and-conquer/
I am trying to debug some stuff where my game is going out of sync during multiplayer, and I just wanted to make sure this isn't the source of the difference :)
latest version here
ReplyDeleteHey Andrea,
ReplyDeleteI thought you would like to know that your name and this algorithm are now in this book... :)
www.adityaravishankar.com/pro-html5-games/
Congrats and thank you!!!