A Flash Developer Resource Site

Page 2 of 4 FirstFirst 1234 LastLast
Results 21 to 40 of 62

Thread: Fast Flash Pathfinding Example

  1. #21
    Yes we can tomsamson's Avatar
    Join Date
    Sep 2001
    Location
    Team Titan Secret Lair
    Posts
    4,666
    hey there,cool stuff,congrats
    sorry for the rather short feedback but i just came home after a 12 work day (deadline stress..),will look into it longer on weekend =).
    you mind if i add the thingy in my editor?

  2. #22
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    Thanks, I'm glad you like it. I recommend the "AI Game Programming Wisdom" book to anyone trying to do this sort of thing.

    You said:
    you mind if i add the thingy in my editor?
    What editor? I'm sure it would be ok, I'm just curious. Thanks!

  3. #23
    Yes we can tomsamson's Avatar
    Join Date
    Sep 2001
    Location
    Team Titan Secret Lair
    Posts
    4,666
    i already read several threads,articles and books (also) discussing pathfinding but thanks for the mention,i think i´ll order that one too =)

    the ed is v3 of my tile ed,it features (multilayer) topdwon and iso map creation and has drawing tools for drawing (filled)rectangles/lines and circles of tiles and importing tilesets.
    you can also load and save the mapoutput in any filetype (hence its a standalone app).

  4. #24
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!

  5. #25
    Senior Member tonypa's Avatar
    Join Date
    Jul 2001
    Location
    Estonia
    Posts
    8,223
    Thank you for explaining the saved paths array. Thats very clever

    Now I understand what you mean by saying the calculation of paths can take long time (I know, its not real-time, only has to be done once), you find every single path from every tile to all the other tiles.

    I wonder if its worth to divide map into grids, lets say 3x3 tiles and only save the paths array for each grids center tile. This could reduce the amount of memory (size of the game) quite a lot.

  6. #26
    Senior Member mr_shotgun_2000's Avatar
    Join Date
    Jun 2002
    Posts
    204
    this sounds so cool webgeek! I cant wait to see the article!

  7. #27
    Yes we can tomsamson's Avatar
    Join Date
    Sep 2001
    Location
    Team Titan Secret Lair
    Posts
    4,666
    Originally posted by webgeek
    Sure you can add it into the editor. Send me an email and I can hook you up with what you need. Thanks!
    coolies,thanks,i´ll do that (but i won´t have time to get into it before weekend).
    i discussed using run length encoding for the map data with pred recently,we haven´t implemented it for the mapdata yet (as our maps aren´t that big and i had to do other parts of the ed first),but wouldn´t it be possible to use run length encoding on the generated pathdata so that it shrinks dramatically in filesize?

  8. #28
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    Yup, that would work perfectly I can't tell you how much effeciency it would gain though as I don't know how many repeats would come up. Thanks!

  9. #29
    Member
    Join Date
    Apr 2001
    Posts
    37
    Is this article still around?

    Sounds like what I am looking for....

    Was the source ever released for this?

  10. #30
    self-portrait Kianis's Avatar
    Join Date
    Feb 2004
    Location
    Stockholm, Sweden
    Posts
    425
    Sorry for diging up an old thread

    This is just amazing ^^ So incredibly fast. :O

    So what you actually save in your precomputed array - is that the list of "parents" you get when running dijkstra's algorithm?

    ( For each node; you go through the whole list of nodes and gather information and saving this info in an array - like cost, and previous node (or parent node). Is this what you're saving? :P )

    Please excuse my crappy english.. : P
    // Mazapán, my portfolio

  11. #31
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    I'm sorry, I don't quite understand the question?

  12. #32
    self-portrait Kianis's Avatar
    Join Date
    Feb 2004
    Location
    Stockholm, Sweden
    Posts
    425
    haha, sorry, I don't completly understand what I wrote either..

    But you said that your array looked something like this
    path[currentPosition][endingPosition] = {x: x, y: y};

    Well, how do you populate this array? I mean how does the precalculation work?
    When you use for instance dijkstra's algorithm (isn't that the one you use?) you cycle through every node and sets its previousNode = currentNode..
    So when you've found the path you'd have an huge array with all the nodes' previousNodes. Using these you can backtrack to the starting node and thus get your path, right?

    And this is the very same array that you save If I've understood it right. It should be... :/
    (of course you'd have to repeat this whole proccess for every node)

    Haha, sorry, not sure if I'm making myself any clearer.. It's actually a stupid question, I'll go experiment a bit and hopefully I'll find out on my own ^^
    Last edited by Kianis; 09-15-2004 at 05:05 PM.
    // Mazapán, my portfolio

  13. #33
    Junior Member
    Join Date
    Nov 2004
    Posts
    5
    Originally posted by webgeek
    That's 390k of RAW data. It will compress down pretty dramatically.
    Very sorry for bringing up a very old thread, but can you explain what you mean here? Is there some way to compress the data to something smaller than 390k but still make it usable for Flash ?

    Thank you

  14. #34
    n00b LeechmasterB's Avatar
    Join Date
    May 2004
    Location
    Switzerland
    Posts
    1,067
    Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not .


    EDIT:

    Woohoo it is faster

    here the proof:
    http://www.flashdev.ch.vu/tutorials/...e/twotoone.zip
    Last edited by LeechmasterB; 11-21-2004 at 09:32 PM.
    I do stuff that does stuff...

    J-Force

  15. #35
    self-portrait Kianis's Avatar
    Join Date
    Feb 2004
    Location
    Stockholm, Sweden
    Posts
    425
    Originally posted by LeechmasterB
    Cool, but wouldn't it be faster using a 1 dimensional array instead? I guess its not .
    edit:
    Last edited by Kianis; 08-11-2006 at 06:52 AM.

  16. #36
    n00b LeechmasterB's Avatar
    Join Date
    May 2004
    Location
    Switzerland
    Posts
    1,067
    The more optimized things are the better it is.
    So my answer would be no , if you really ask for it. If you make big games, every ms can count. Because if you have lots of things that take 10 ms it gets slower too.
    Using a 1 dimensional array is almost double as fast on small arrays (50-100x50-100 elements). And still faster using big arrays 1000x1000).
    I do stuff that does stuff...

    J-Force

  17. #37
    Junior Member
    Join Date
    Apr 2005
    Posts
    3
    This works out great if the path can't be blocked. What if you have more than one object and the second object is blocking the other's way? Do you have to save ALL possible paths to get from one tile to another? I suppose a way around this is to implement a standard A* procedure that you can fall back on in this situation, but is there a different way you had in mind in this case?

  18. #38
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    I've gone ahead and updated the link to the tutorial in the first post. You can click this too if you want:
    http://www.electrotank.com/junk/mike...hTutorial.html

    LeechmasterB: Using 1 array might be a way to make it slightly faster (going from 5ms to like 3) but to be honest, the drop in readablity and the complexity increase in array creation doesn't really warrant the change unless you REALLY need it. This is a perfect example of premature optimization. Don't dirty things up to make things faster when you don't know if this is the problem in the first place. It's best to make it, then make it work, then make it work fast.

    Plecostomus: This technique only works for STATIC maps. It's not designed to be used with dynamic maps. As such, it simply gives the shortest path. It's designed to not care if there are 10 other ways to get there, it only saves the absolute shortest. If there is no way from A to B, it will simply return nothing. Currently that's a bug in my example I never got around to fixing. I'm not sure if that answers your question though, so please let me know if I missed your point.

  19. #39
    Junior Member
    Join Date
    Apr 2005
    Posts
    3
    Yes, this did answer my question. I was hoping this technique was applicable in project, but do to this fallback it is not. Thanks anyways.

  20. #40
    Senior Member webgeek's Avatar
    Join Date
    Sep 2000
    Posts
    1,356
    It sounds like you simply need to use something like A*. It's terrain aware, flexible and pretty fast. Jobe Makar's game books have an excellent A* implementation.

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