Thread: Path-Finding Algorithms

Page 1 of 2 12 LastLast
Results 1 to 10 of 18
  1. #1 Path-Finding Algorithms 
    Java/C++ Programmer

    Join Date
    Jun 2008
    Age
    27
    Posts
    1,377
    Thanks given
    203
    Thanks received
    387
    Rep Power
    815


    Look at that video.

    Which algorithm (doesn't have to be on at that video) do you think is best fit for RS2?

    Also, don't give me the bullshit that Dijkstra's algorithm is better than AStar and that AStar is slow as hell. I've tweaked my AStar to run complicated RS2 paths in ~5ms. AStar is in fact a derivation of Dijkstra's algorithm except that it uses heuristics to perform better. If you don't know what that is, the video demonstrates the behaviors of some algorithms.

    On top of what algorithm is best fit, I'd also like to ask if we should implement bi-directional searching, an idea that Maxi gave me. Bi-directional searching is demonstrated in the video. It can be applied to any path-finding algorithm we want.
    Reply With Quote  
     

  2. #2  
    Renown Programmer and Respected Member
    Maxi's Avatar
    Join Date
    Jun 2008
    Posts
    3,197
    Thanks given
    281
    Thanks received
    1,095
    Rep Power
    1366
    Dijkstra is good when you don't know the location of your destination. For example:

    You want to go to the McDonalds but there are like 4 in town and you don't know their locations. Dijkstra will find the nearest much quicker than Astar but in rsps we actually know the location hence why the use of heuristics improves the algorithm to find the shortest path quicker.

    Rsps pathfinding could use bidirectional pathfinding which in most cases will lower the amount of checked tiles before a path is found making it quicker. Also the general astar could be improved by using a different approach on heuristics etc.
    Reply With Quote  
     

  3. Thankful user:


  4. #3  
    Registered Member

    Join Date
    Feb 2009
    Age
    27
    Posts
    2,861
    Thanks given
    127
    Thanks received
    226
    Rep Power
    700
    AStar definitely, Dijkstra would take too long, as say there is a distance of 20 tiles between you and your target, Dijkstra would search up to 60 tiles (probably wrong, correct me) before finding it whereas AStar is a lot quicker.
    Reply With Quote  
     

  5. #4  
    Registered Member Anthony-|'s Avatar
    Join Date
    Jan 2008
    Posts
    749
    Thanks given
    103
    Thanks received
    46
    Rep Power
    58
    AStar seems to be really fast in finding the path. So I would say A*.
    Reply With Quote  
     

  6. #5  
    Path-Finding Algorithms



    Scu11's Avatar
    Join Date
    Aug 2007
    Age
    30
    Posts
    16,307
    Thanks given
    7,215
    Thanks received
    12,308
    Rep Power
    5000
    Quote Originally Posted by Jarba View Post
    AStar definitely, Dijkstra would take too long, as say there is a distance of 20 tiles between you and your target, Dijkstra would search up to 60 tiles (probably wrong, correct me) before finding it whereas AStar is a lot quicker.
    How would it 'take too long'? Pali uses the method ripped out of the rs2 client which is dijkstra's, and its fairly fine.

    Attached image
    Reply With Quote  
     

  7. #6  
    Hi.

    'Mystic Flow's Avatar
    Join Date
    Nov 2007
    Posts
    7,146
    Thanks given
    256
    Thanks received
    1,252
    Rep Power
    3714
    It seems like Dijk's is the way to go when it comes to complicated paths but A* finds simple paths way faster, but in the end it seems like A* works just as efficient, and I don't really know about the Bi-Directional, seems too costly for simple paths but great for complicated paths like Dijk's



    Reply With Quote  
     

  8. #7  
    Renown Programmer

    Join Date
    Dec 2010
    Posts
    2,876
    Thanks given
    508
    Thanks received
    1,898
    Rep Power
    5000
    A* works fine, although you could alternate between A* and Dijk's method depending on the amount of objects in the region.
    never talk to me or my wife's son ever again
    Reply With Quote  
     

  9. #8  
    Member
    Boomer's Avatar
    Join Date
    Sep 2006
    Posts
    1,282
    Thanks given
    309
    Thanks received
    795
    Rep Power
    1111
    Quote Originally Posted by Nihil View Post
    A* works fine, although you could alternate between A* and Dijk's method depending on the amount of objects in the region.
    I don't get it.. in all cases A* was faster.. so why even bother?


    Osiris ||| FightScape | InnerFantasy | PkIsle | Paragon | Enkrona | 2006Scape
    Reply With Quote  
     

  10. #9  
    Hi.

    'Mystic Flow's Avatar
    Join Date
    Nov 2007
    Posts
    7,146
    Thanks given
    256
    Thanks received
    1,252
    Rep Power
    3714
    Quote Originally Posted by Boomer View Post
    I don't get it.. in all cases A* was faster.. so why even bother?
    A* was the slowest when it came to a complicated path



    Reply With Quote  
     

  11. #10  
    Renown Programmer and Respected Member
    Maxi's Avatar
    Join Date
    Jun 2008
    Posts
    3,197
    Thanks given
    281
    Thanks received
    1,095
    Rep Power
    1366
    Quote Originally Posted by 'Mystic Flow View Post
    A* was the slowest when it came to a complicated path
    Must be a lucky guess and is because of the way the algorithms work. A-star is a heuristic driven algorithm where Dijkstra will start searching in all directions. Dijkstra is good to find the closest node of one kind when you don't know its location.

    If in your benchmark Dijkstra was faster for calculating a complicated path (which to sounds just as a coincidence and when repeated will give a different result) it will be because in a complicated situation both algorithms checked an equal amount of nodes (or close to). The whole idea of a heuristic driven routefinding algorithm is that it is faster because it has a guess in which way to start checking nodes and is able to find a path (in most cases) knowing it's the shortest without having checked upon all nodes. Dijkstra will expand its search in al directions and check upon all tiles within a set range and take the shortest route but this makes it much more resource demanding.

    The clients routefinding is terrible. It fits the job because it doesn't have to that high performance as it's just calculating routes for one player but if you have server sided routefinding you have to take care of hundreds of players and their paths sometimes. The only reason why I could think of a Dijkstra's implementation in a server is if you want to have a seperate system to have players walk to a certain object (ground item, object, npc w/e) without knowing which one is the closest. Although Dijkstra should never replace location known routefinding.
    Reply With Quote  
     

  12. Thankful users:


Page 1 of 2 12 LastLast

Thread Information
Users Browsing this Thread

There are currently 1 users browsing this thread. (0 members and 1 guests)


User Tag List

Similar Threads

  1. [614] Finding path
    By lukas265 in forum Help
    Replies: 1
    Last Post: 11-30-2010, 10:48 PM
  2. [PI] Noclipping , Path-Finding?
    By Vegas in forum Help
    Replies: 6
    Last Post: 10-08-2010, 09:07 PM
  3. Path-Finding (ALL) *Clipped Following*
    By Nintendo in forum Snippets
    Replies: 15
    Last Post: 09-06-2010, 05:35 PM
Posting Permissions
  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •