A Flash Developer Resource Site

Page 3 of 4 FirstFirst 1234 LastLast
Results 41 to 60 of 62

Thread: Fast Flash Pathfinding Example

  1. #41
    Junior Member
    Join Date
    Apr 2005
    Posts
    3
    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.

  2. #42
    Actionscript Developer KigD's Avatar
    Join Date
    Jan 2003
    Location
    georgia
    Posts
    597

    Psychopath

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

    -Danny
    K2xL - My games, tutorials, message boards, and experiments.
    Blog

  3. #43
    CostomJunky Xploder's Avatar
    Join Date
    Jun 2003
    Location
    Canada
    Posts
    635
    wow, that's amazing... really addicting... must... play it...

  4. #44
    doItLikeThis
    Join Date
    Jan 2004
    Location
    :noitacoL
    Posts
    1,080
    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.
    -Aditya

  5. #45
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    >> 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.

  6. #46
    doItLikeThis
    Join Date
    Jan 2004
    Location
    :noitacoL
    Posts
    1,080
    Nice! Add-->Favorites
    -Aditya

  7. #47
    The Flashman earl223's Avatar
    Join Date
    Sep 2000
    Location
    Marikina City, Philippines
    Posts
    876
    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?
    i eat actionscripts for breakfast

  8. #48
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    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.

  9. #49
    The Flashman earl223's Avatar
    Join Date
    Sep 2000
    Location
    Marikina City, Philippines
    Posts
    876
    hey yeah... i guess thats it. thanks!
    i eat actionscripts for breakfast

  10. #50
    Junior Member
    Join Date
    Jul 2006
    Posts
    3

    Where!

    Where do I get the FLA's?

  11. #51
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    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.

  12. #52
    Junior Member
    Join Date
    Jul 2006
    Posts
    3

    Please, Please...

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

  13. #53
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    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

  14. #54
    Junior Member
    Join Date
    Jul 2006
    Posts
    3
    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.

  15. #55
    Junior Member
    Join Date
    Mar 2006
    Posts
    1
    please release the source..
    i dont car if it is in AS1
    i would be very grateful if you would release the source

  16. #56
    M.D. mr_malee's Avatar
    Join Date
    Dec 2002
    Location
    Shelter
    Posts
    4,139
    use flashDreamer's blog, its got some good links to pathfinding code

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

    pimpin the FK blogs baby
    lather yourself up with soap - soap arcade

  17. #57
    SaphuA SaphuA's Avatar
    Join Date
    Oct 2002
    Location
    The Netherlands
    Posts
    2,182
    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.

  18. #58
    Junior Member
    Join Date
    Mar 2007
    Posts
    2
    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

  19. #59
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    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?

  20. #60
    Junior Member
    Join Date
    Mar 2007
    Posts
    2
    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •  




Click Here to Expand Forum to Full Width

HTML5 Development Center