A Flash Developer Resource Site

Results 1 to 11 of 11

Thread: Need Fast pathfinder

  1. #1
    Junior Member
    Join Date
    Mar 2008
    Posts
    23

    Need Fast pathfinder

    Hello !

    I am trying to make a simple "tower defense" game, where you put towers on a tile-based map to stop bad guys from going through.

    I tried understanding pathfinding from what I found on the internet... and it is too much for me right now I think.

    So I was wondering, do you people know where I could get a fast and simple pathfinder ?

    Terrain has no different costs and map size is about 25x40 btw.

    Thx alot.


    P.S. I know this has probably been posted before, but I couldn't find anything... sorry...

  2. #2
    Junior Member
    Join Date
    Jan 2007
    Location
    New York
    Posts
    16
    here's the best link that i know of..think you can even download some source code and run it


    http://jobemakar.blogspot.com/2008/0...thfinding.html

  3. #3
    Developer dVyper's Avatar
    Join Date
    Oct 2008
    Location
    UK
    Posts
    168
    This might help;
    Mochiland tutorial

  4. #4
    Junior Member
    Join Date
    Mar 2008
    Posts
    23
    A* and Dijkstra are both slow and very accurate, to what I have read around the web...

    But I am talking about 5-20 units serching path on a dynamic map with no terrain cost... so A* seems like a bad choice.

    I just read about "tracing", "robust tracing" and such... anyone could give me information about those ?

  5. #5
    Senior Member
    Join Date
    Nov 2005
    Posts
    192
    Could just have one unit find the path at the start of the round, then the rest of the units use waypoints. then in the movement function, you could have each unit check if they encounter a wall between 2 waypoints in case the tower builder placed a tower after the path was found.

    otherwise, just disable the builder from building while the units are moving.

  6. #6
    Student
    Join Date
    Apr 2001
    Location
    -
    Posts
    4,756
    look in the flashkit movie section or somewhere else where there is a simple and plain fla example.

    I recently had to dig up this topic as well to write a pathfinding that is very fast (+60 units computing every few seconds) on quite complex terrain.

    In the past I experimented alot with node based pathfinding which usually requires manually or half automated node placement- but on very large and detailed maps it did not worked out well for me.
    This time I experimented with a dynamic grid that is placed over a image (greyscale) or movieClip and check within that grid wich cells are acessable

    Usually in A* you try to find multiple ways and sort them at the end based on their effectness- but I found a way to do a quick and dirty pathfinding searching basicly only 1 path. It works for 80% of the cases I had- and in case it fails it walks at least as far as possible.

    I might release a as3 class at some time but not this year

  7. #7
    Junior Member
    Join Date
    Mar 2008
    Posts
    23
    Quote Originally Posted by Flyingcow
    Could just have one unit find the path at the start of the round, then the rest of the units use waypoints. then in the movement function, you could have each unit check if they encounter a wall between 2 waypoints in case the tower builder placed a tower after the path was found.
    That is the way I thought I'd do it, but I can't figure out how to make it work when the player adds towers...

    And lets say he adds a whole lot of them, wouldn't that mess up the path completly if you don't search for a new one ? Or maybe I'm just not understanding how you'd do it...

    If I can't find anything, I'll probably just make it impossible to build towers during waves.

  8. #8
    Funkalicious TOdorus's Avatar
    Join Date
    Nov 2006
    Location
    Nijmegen, Netherlands
    Posts
    697
    Just go through all the paths of the troops currentl on screen, and check if it goes through the cell that a new tower has been placed on. If so, recalculate the route. You might be able to shave something off, by only making a route which connects the two pieces of the original route and stuff it in between.

  9. #9
    Senior Member Pazil's Avatar
    Join Date
    Sep 2006
    Location
    Ontario, Canada
    Posts
    913
    First off, A* and Dijkstra's algorithms are both the same, except that A* is an optimization of Dijkstra's by doing a priority first search. And A* will usually only find one way, just it starts searching several, but then only completes one...

    The best way I would suggest is to do the algorithm (I'm not sure if there's even an exact name for it or not) that find a path as long as it's not convex, but then just have the baddy check if a)it's visited the same square before, and b) if it's going in the same direction as it had already before...

    Render, that looks like a pretty neat thing you've got going there...but it seems as though your algorithm can't handle convex (u-turns) shapes? Just the example you posted doesn't have any areas like that, but the only one you really had in there was at the beginning, and it seems as though you valued x movement over y? Am I wrong? Just wondering, since if I am wrong, your algorithm is truly amazing!

    P.
    WIP-ZOMBIES

    I love vegetarians! More meat for the rest of us!

  10. #10
    Senior Member Pazil's Avatar
    Join Date
    Sep 2006
    Location
    Ontario, Canada
    Posts
    913
    Sorry...Double post...computer locked up for a second...
    WIP-ZOMBIES

    I love vegetarians! More meat for the rest of us!

  11. #11
    Knows where you live
    Join Date
    Oct 2004
    Posts
    944
    Whenever you have a graph search problem, A* is generally the best solution. As well as always producing an optimal path, it is very efficient compared to other methods.

    Tracing and robust tracing will either fail or produce very unnatural paths.

    From what I can see in render's post it performs a naive search in the direction of the target and then smooths the path.

    Since the start and end tile are always the same you can take some pretty serious liberties in your pathfinding as well. In all truthfulness, the chances are that you will only have to calculate the path once after each tower is built and reuse that path for each unit.
    The greatest pleasure in life is doing what people say you cannot do.
    - Walter Bagehot
    The height of cleverness is to be able to conceal it.
    - Francois de La Rochefoucauld

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