A* pathfinding demo

[shoehorn]

Many months ago there was some discussion about A* and pathfinding. (Likely there have been discussions since, I haven't been keeping up with this forum.) I've made some minor updates to the A* movie, and put the fla file up for people to have a look at.

You can find it here: http://www.antimodal.com/astar/

[hooligan2001]

I found that A* is speed intencive for Flash games its just so slow sometimes. I know that you can adjust your A* heuristic to approximate more but its to slow. I know that A* is accurate, but its just my opinion.

[mosterdfles_flash]

That's realy nice!

But very complicated :S... i dont get it

[Flecko]

I think you're referring to a question I asked way back then. I did my school science project on comparing the algorithms available, and determined that at least for my application, Dijkstra's algorithm is the best. It's better for fiding the distance to every position within a given range, becuase you need 1 iteration per square anyway and it has the shortest iterations.

I may put my own demo up tonight since the topic has come back, check back later if you want to see it.

[voodoo-wizard]

i found this very interesting and useful

[mosterdfles_flash]

Originally posted by Flecko
I think you're referring to a question I asked way back then. I did my school science project on comparing the algorithms available, and determined that at least for my application, Dijkstra's algorithm is the best. It's better for fiding the distance to every position within a given range, becuase you need 1 iteration per square anyway and it has the shortest iterations.

I may put my own demo up tonight since the topic has come back, check back later if you want to see it.

Like ta see it
________________________________________-



I was was wondering, what does A* (astar) mean anyway???

[jobemjobem]

That's pretty sweet!

Here is my implimentation of A* as applied to an isometric world. This version of it supports multiple terrains.
http://www.electrotank.com/lab/astar_iso.html

The path that he'll walk is between where he is and the highlighted square. You can change the terrain or the object on any square.

What's so cool about A*, in my opinion, is the multi-terrain stuff. The algorithm will actually search for paths around, say, a big pond. If the pond is too big then it will take you through it

Great job on yours!

ps. Hooligan: A* can be sped up. There is an array of 'open' tiles that are being searched. That array can get big. You can force it to never get above a certain size making the algorithm dramatically faster. But with speed you get less accurate results. You will find a path but it may not be the best.

[hooligan2001]

jobemjobem:- Yeah i understand. Great demo. Gotta love the frog. It is a frog right

[jobemjobem]

Yeah, its a frog-alien type of thing

[Flecko]

http://www.flecko.net/flash.php?file...512&height=512

It runs three pathfinding algorithms in this order: Dijkstra's, BFS, and A*. It's displayed as a grid, where the lighter squares cost less. Each algorithm colors the squares it explores so you can see how it moves. (By the way, I should mention that this is not the traditional A*, but a modified version which sacrifices about 10% accuracy for some extra speed). The program should be self-explanatory, but if you can't figure out what the forms mean just hit the 16x16 button.

This was my high school science project. The navy awarded me 50 bucks for it