|
Title: Pathfinding Algorithm Post by: Cortez on May 03, 2004, 01:28:00 pm Does anyone have a correct pathfinding routine? (no matter which language)
Title: Pathfinding Algorithm Post by: bEn on May 03, 2004, 02:40:08 pm The (rather famous) A* algorithm can be found here:
http://www.gamedev.net/reference/articles/article2003.asp Saw this post too late to have a look at my algorithm book but this one should work fine and is explained rather well (with much background info and actual code). A spanish and french version can be found here: http://www.policyalmanac.org/games/aStarTutorial.htm It is said to be the best but a rather expensive algorithm - can't say much as till this day this is just second hand knowledge as I had no chance to have a algorithms/AI course yet (tho I have a AI course now). Another (maybe more simple/less expensive) algorithm should be the Dijkstra's Algorithm - more information on that one can be found at: http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml http://ciips.ee.uwa.edu.au/~morris/Year2/PLDS210/dijkstra.html Title: Pathfinding Algorithm Post by: nick on May 12, 2004, 08:50:57 pm i agree.. A* is the best to use... it's quite simple and tends to find any goal path in a reasonable time.
Title: Pathfinding Algorithm Post by: Zylokh on May 13, 2004, 07:53:31 am I still have to implement this in Shining Odyssey some time soon...
Title: Pathfinding Algorithm Post by: Cortez on May 14, 2004, 09:56:13 am But actually, I've found that it's not a perfect method, ie it doesn't handle all situations. For instance:
(movement from Source to Destination) Code:
I guess this is why player prefers weird & incorrect paths in some games (eg StarCraft, Diablo). However, it's quite fast. Title: Pathfinding Algorithm Post by: bEn on May 14, 2004, 12:53:09 pm Mhhh it doesn't? Isn't the solution to that problem that if you reach a dead end you put the current square to the closed list, call the last one current (maybe delete it from the closed list) and take the best sqare that is not on the closed list.
I guess there are many variations that deal with this problem. |