[ Login | Register ]

The Shining Source

« previous next »
Pages: [1] Print
Pathfinding Algorithm   (Read 20112 times)
Old Post May 03, 2004, 01:28:00 pm
#1
Blahian *

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?


Old Post May 03, 2004, 02:40:08 pm
#2
bEn
Shining Light *

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

t's not like I really care


Old Post May 12, 2004, 08:50:57 pm
#3
Shining Something *

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...


Old Post May 13, 2004, 07:53:31 am
#4
Shining Something *

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


Old Post May 14, 2004, 09:56:13 am
#5
Blahian *

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)
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?


New Post May 14, 2004, 12:53:09 pm
#6
bEn
Shining Light *

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.

t's not like I really care


Pages: [1] Print 
« previous next »
Jump to:  

Powered by SMF 1.1.21 | SMF © 2013, Simple Machines