Is there some sort of standard "shortest-path" algorythm strategy games use to move around obsticles?
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.
Ya it doesn't always work though :), at least in the older games and some newer ones.
am i the only one confused?
There are a few, but I've read only about Dijkstra's. Wikipedia has a list here http://en.wikipedia.org/wiki/Shortest_path.
Hi,
Heres the Perl AI::Pathfinding::Astar (http://search.cpan.org/~acdalton/AI-Pathfinding-AStar-0.06/AStar.pm) module up on CPAN, having a look at the perl source will explain the algo.
Heres a Link (http://www.policyalmanac.org/games/aStarTutorial.htm) to an A* tutorial. And heres some general links to Game Pathfinding sites/info (http://www.gameai.com/pathfinding.html)
Hope this helps.
Displeaser
Hi,
Heres the Perl AI::Pathfinding::Astar (http://search.cpan.org/~acdalton/AI-Pathfinding-AStar-0.06/AStar.pm) module up on CPAN, having a look at the perl source will explain the algo.
Heres a Link (http://www.policyalmanac.org/games/aStarTutorial.htm) to an A* tutorial. And heres some general links to Game Pathfinding sites/info (http://www.gameai.com/pathfinding.html)
Hope this helps.
Displeaser nice thanks
Here's a few more.
Amits thoughts on pathfinding and A* (http://theory.stanford.edu/~amitp/GameProgramming/)
Path Finding - A* Algorithm (http://www.edenwaith.com/products/pige/tutorials/a-star.php)
A* pathfinding for begineers (http://www.gamedev.net/reference/articles/article2003.asp)
Begineers Guide to Pathfinding Algorithms (http://ai-depot.com/Tutorial/PathFinding.html)
Displeaser
Btw displeaser I added both your posts to the resources thread (http://forums.devshed.com/game-development-141/game-development-resources-361509.html#post1530984)
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.