| Pages: [1] |  |
Pathfinding Algorithm (Read 62259 times)
May 03, 2004, 01:28:00 pm 
Posts: 20
Logged
Pathfinding Algorithm
Does anyone have a correct pathfinding routine? (no matter which language)
n a world without walls and fences,
who needs windows and gates?
May 03, 2004, 02:40:08 pm 
Posts: 224
Logged
Pathfinding Algorithm
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
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
t's not like I really care
May 12, 2004, 08:50:57 pm 
Posts: 118
Logged
Pathfinding Algorithm
i agree.. A* is the best to use... it's quite simple and tends to find any goal path in a reasonable time.
o yo yo...
May 13, 2004, 07:53:31 am 
Posts: 143
Logged
Pathfinding Algorithm
I still have to implement this in Shining Odyssey some time soon...
hining Odyssey under devlopment: http://mapage.noos.fr/zylokh
May 14, 2004, 09:56:13 am
Posts: 20
Logged
Pathfinding Algorithm
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)
I guess this is why player prefers weird & incorrect paths in some games (eg StarCraft, Diablo). However, it's quite fast.
(movement from Source to Destination)
Code:
000D00
000000
011110
010010
01S010
000010
I guess this is why player prefers weird & incorrect paths in some games (eg StarCraft, Diablo). However, it's quite fast.
n a world without walls and fences,
who needs windows and gates?
May 14, 2004, 12:53:09 pm
Posts: 224
Logged
Pathfinding Algorithm
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.
I guess there are many variations that deal with this problem.
t's not like I really care