Fast Flash Pathfinding Example

I wrote a functional pathfinding routine for easy implementation in my flash games. It handles horizontal, vertical, and diagonal motions just fine, but you know how A* pathfinding ends up while trying to utilize 1200 tiles in Flash MX. To move around obstacles it can take the computer 8.5 seconds to move one object from one extremity of the map to the other. And just imagine what moving 20 objects at once is like! I had another idea about moving the pathfinding commands into a VB6 program implementing the Shockwave Flash activeX component for more speed, but it still gets clunky when trying to move multiple objects.
Thanks for the idea, but I got that one covered.

You guys might be interested in my game:
www.k2xlgames.com/games/psychopath

-Danny

wow, that's amazing... really addicting... must... play it...

Since this thread is up, I wanted to know, is it possible if this kind of pathfinding can be implemented in art based games? Just curious as I saw that it was grid based, being mentioned in the starting.

>> I wanted to know, is it possible if this kind of pathfinding can be implemented in art based games?

Yup, easily. The original model for this was created using manually located nodes. You just dropped some nodes down, drew some connecting lines, and then precalculated the data. Works great and actually takes a LOT less data to pre-compute.

Nice! Add-->Favorites

Question: Let's say i have a character and when i click on it, it highlights all the possible paths he could take assuming he could walk 10 spaces in any direction... like in tactics arena? Will i also use path finding for this? how will i implement it, if path finding requires a destination?

Quote:

---

Originally Posted by earl223

Question: Let's say i have a character and when i click on it, it highlights all the possible paths he could take assuming he could walk 10 spaces in any direction... like in tactics arena? Will i also use path finding for this? how will i implement it, if path finding requires a destination?

---

It can be done similar to pathfinding, but of course you need to count the steps:

*start from current node
*add all neighbour nodes to checklist if number of steps is <10 and they are not checked yet
*take next node out from checklist
*continue until checklist is empty

Unless you mean all 10 steps must be in same direction, say 10 steps left and no changing direction.

hey yeah... i guess thats it. :) thanks!

Where do I get the FLA's?

Man, this thread just keep scoming back ;)

Sorry, I never did release source. This thing was written in AS1 ages ago. It needs to be re-written before I'd consider releasing it. Sorry.

Some advice then?...I have no problem in read the FLA in AS1.
Please, please, please...

Pretty much everything necessary to recreate the code is discussed on the first page or two of this thread. To be completely honest, AS3 might make this whole approach a moot point. For the average Flash game, I suspect AS3 is fast enough to use A* directly. In commercial games, this is used on gargantuan maps with thousands of tiles to a side. Where even something like A* in C++ will be too slow. Unless you plan on making something like that, I'd suggest trying out AS3.

Hmmm. Maybe I'll play with A* in AS3 to see how fast it really is ;)

Quote:

---

Originally Posted by webgeek

Pretty much everything necessary to recreate the code is discussed on the first page or two of this thread. To be completely honest, AS3 might make this whole approach a moot point. For the average Flash game, I suspect AS3 is fast enough to use A* directly. In commercial games, this is used on gargantuan maps with thousands of tiles to a side. Where even something like A* in C++ will be too slow. Unless you plan on making something like that, I'd suggest trying out AS3.

Hmmm. Maybe I'll play with A* in AS3 to see how fast it really is ;)

---

The point is that an A* won't work for me. I haven't dynamic maps and precalculated pathfinding will be the best choice for me (I think). I'm working in AS2 and I don't plan to work in AS3. I work better when I see the FLA and try to understand it, but if you have something to say to me...I read the first pages of this thread but I need more...
Thank you.

please release the source..
i dont car if it is in AS1
i would be very grateful if you would release the source

use flashDreamer's blog, its got some good links to pathfinding code

http://www.freshvision.com.au/blog/

pimpin the FK blogs baby :D

Geez.. stop begging for the source, Webgeek has already said he won't release it. Or ask him for his bank account and send him a litte gift. It's still someone elses work you're asking for.

With larger maps, this approach needs huge amounts of memory. I haven't tested it yet, but if Flash could store 1 Array element in 1 byte (which I don't know), it would need 100 mbyte for a 100*100 grid and 62 gbyte (!) for a 500*500 tile map. So I thought about how to compress this data.

In a map of medium complexity, there will be huge 'areas' inside every tile's array which contain the same information. E.g. a tile which is surrounded by walls at 8 sides, will have an array consisting of mapH*mapV items of the same value (e.g. "go up" if the only exit is above the tile). Why not compress this?

I first thought of using binary trees to describe rectangular accumulations of same-value-items, but as I'm not a pro in programming,... well, then I had the idea of using jPeg bitmaps to store and compress the tile data. I think they use smart methods to compress images with large areas of the same colour. The perfect implementation to store as much info as possible in a pixel, would be possibly to split the hexadecimal code of the 24 bit jPeg pixel (like '0xFF057D') into 6 4-bit values each representing the direction towards one specific target tile (i.e. 6 tiles per pixel each havin 16 possible states, like 'F' = up, '3' = right, '4' =right and 1/4 down...).

Unfortunately, I simply don't know whether creating jPegs out of bitmapData is actually possible, how to load, read, and dispose them, or, for the future, how to save them together with the map data on hd (will probably require screenweaver).

regards, stefan

I don't know if it's in this thread or not, but as I've posted before this is NOT the ultimate use of the technique. It's really intended to be used in maps where the nodes can be placed as needed rather then on a grid. I used the grid as simply a way to show people how it would work.

Also, you are assuming every node must always be connected to every other node. You can use varying levels of grids to get the same effect at much less memory usage. Or, even better, use different searching techniques as needed. For instance, use a fine-detail A* algo to find your way to the door of a room and use this to find your way from room to room. Make sense?

Hi webgeek! Thanks for the reply. I see your point that the technique suits far better for dungeon games or adventures. I was just thinking of an implementation in an RTS game in which there is just one single map and the grid is nescessary to allow fast interaction between agents and to allow every unit to go anywhere on the map, not just to predefined nodes. Anyway, maybe the idea is weird, but I'll try and post the memory usage results, because no other approach can be that fast at runtime.

Quote:

---

Originally Posted by mr_malee

use flashDreamer's blog, its got some good links to pathfinding code

http://www.freshvision.com.au/blog/

pimpin the FK blogs baby :D

---

Hehe must of missed that one, thanks for the pimp :P, in the middle of re designing the blog so if your after the resources post its split up under the topic resources. Blog should be done soon. Thanks for the props and sorry for the hijack

Wow, it's the recursive zombie topic. :scared::shhh: :zombie: :eek:

Anyways. Path finding, I need to learn that. Maybe I should learn how to use tiles first...