Thread: SPF Algorythm?

    #1
  1. Come to the door. . .
    Devshed Novice (500 - 999 posts)

    Join Date
    Mar 2004
    Location
    Ohio
    Posts
    814
    Rep Power
    197

    SPF Algorythm?


    Is there some sort of standard "shortest-path" algorythm strategy games use to move around obsticles?
    The first dog icon I've EVER used!
  2. #2
  3. No Profile Picture
    Contributing User
    Devshed God 1st Plane (5500 - 5999 posts)

    Join Date
    Oct 2000
    Location
    Back in the real world.
    Posts
    5,966
    Rep Power
    191
    Originally Posted by adorablepuppy
    Is there some sort of standard "shortest-path" algorythm strategy games use to move around obsticles?
    Yes, it's called "A*".

    There is a mathematical proof somewhere out there that says it produces the shortest path possible within a given time ... or so.... (sorry, no sources available right now)

    Use it!

    M.
  4. #3
  5. Psycho Canadian
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Jan 2001
    Location
    Canada
    Posts
    4,846
    Rep Power
    635
    Ya it doesn't always work though , at least in the older games and some newer ones.
  6. #4
  7. No Profile Picture
    what do I know about diamonds?
    Devshed Novice (500 - 999 posts)

    Join Date
    Jul 2003
    Location
    ON, Canada
    Posts
    950
    Rep Power
    175
    am i the only one confused?

  8. #5
  9. Devshed Newbie (0 - 499 posts)

    Join Date
    Mar 2006
    Posts
    264
    Rep Power
    124
    There are a few, but I've read only about Dijkstra's. Wikipedia has a list here http://en.wikipedia.org/wiki/Shortest_path.
  10. #6
  11. Periodically energetic Perler
    Devshed Regular (2000 - 2499 posts)

    Join Date
    May 2005
    Location
    Dublin, Ireland
    Posts
    2,265
    Rep Power
    538
    Hi,

    Heres the Perl AI::Pathfinding::Astar module up on CPAN, having a look at the perl source will explain the algo.
    Heres a Link to an A* tutorial. And heres some general links to Game Pathfinding sites/info

    Hope this helps.
    Displeaser
    Last edited by displeaser; June 21st, 2006 at 02:48 AM.
    Vi Veri Veniversum Vivus Vici.
  12. #7
  13. Psycho Canadian
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Jan 2001
    Location
    Canada
    Posts
    4,846
    Rep Power
    635
    Originally Posted by displeaser
    Hi,

    Heres the Perl AI::Pathfinding::Astar module up on CPAN, having a look at the perl source will explain the algo.
    Heres a Link to an A* tutorial. And heres some general links to Game Pathfinding sites/info

    Hope this helps.
    Displeaser
    nice thanks
  14. #8
  15. Periodically energetic Perler
    Devshed Regular (2000 - 2499 posts)

    Join Date
    May 2005
    Location
    Dublin, Ireland
    Posts
    2,265
    Rep Power
    538
  16. #9
  17. Psycho Canadian
    Devshed Demi-God (4500 - 4999 posts)

    Join Date
    Jan 2001
    Location
    Canada
    Posts
    4,846
    Rep Power
    635
    Btw displeaser I added both your posts to the resources thread
  18. #10
  19. No Profile Picture
    Registered User
    Devshed Newbie (0 - 499 posts)

    Join Date
    Jun 2006
    Posts
    8
    Rep Power
    0
    If you can get hold of the Games Programming Gems series from Charles River (they are a bit pricey tho'), have a look at the index for Vol.4, there are 30 entries for Path Finding over the 4 volumes - doesn't cover vol. 5 which is out now.

    If you like printed books - check out a good bookstore under Game Programming and Game AI - I think I remember seeing a series called something like Games AI or Games AI Gems last time I was in Waterstones that look pretty cool - and pretty expensive as well.

IMN logo majestic logo threadwatch logo seochat tools logo