best path detection... solving this riddle...

Page 1/2
| 2

By norakomi

Paladin (961)

norakomi's picture

15-10-2007, 09:12

Hello people !!

I'm having some problems determinating a best path.
I'll explain in more detail by giving some examples

mapdata:
db 1,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,9,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0

this is my map, where 0 is land (you can just walk on it), 1 is the position of the player, and 9 is the position where you click with the mouse.
As soon as you click with the mouse the best/shortest path is displayed with an X on the screen, like this:

mapdata:
db 1,0,0,0,0,0,0,0,0,0
db 0,x,0,0,0,0,0,0,0,0
db 0,0,x,0,0,0,0,0,0,0
db 0,0,9,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0

In this situation the best path is DR(downright), DR, D
How is this calculated ?
The computer first looks at the starting postion (0,0) and then at the ending position (2,3)
then the computer looks at dx (2-0). is this positive then the first step should be to the right.
then the computer looks at dy (3-0). is this positive then the first step should be down.
so the first step should be down and right. DR.

ok, now comes the hard part, lets take this example:
mapdata:
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,0,0,T,0,0,0,0,0
db 0,0,1,0,T,9,0,0,0,0
db 0,0,0,0,T,T,T,T,T,T

in this situation the player start at (2,4) and has to go to (5,4), but there are some obstacles T(rees) the player cant walk through.
Now my question is... how do we let the computer come up with the best solution to walk from startpoint to endpoint ??

and what about this example:
mapdata:
db 0,0,0,T,0,0,0,9,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,T,T,T,T,T,T,0,0
db 0,0,0,1,0,0,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

thanx for your help....

Login or register to post comments

By snout

Ambassador (14859)

snout's picture

15-10-2007, 09:13

(off-topic) So, euhm, with Space Manbow just 'out there' you are already working on your next project? I like! ^_^

By [D-Tail]

Ascended (8210)

[D-Tail]'s picture

15-10-2007, 10:29

norakomi: try the wave propagation algorithm. Its performance is not really good (O[n^2]), but it will give you 100% correct and optimal result, all of the time. It works like this:

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,T,T,T,T,T,T,0,0
db 0,0,0,S,0,0,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

I used your example, replaced '1' with 'S(ource)' and '9' with 'D(estination)'. Well now. the wave propagation algorithm works as follows; starting from S:

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,T,T,T,T,T,T,0,0
db 0,0,1,S,1,0,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,0,0,0,0,0,0,0,0,0
db 0,0,T,T,T,T,T,T,0,0
db 0,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,0,0,0,0,0,0,0,0,0
db 0,3,T,T,T,T,T,T,0,0
db 3,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0
db 0,4,0,0,0,0,0,0,0,0
db 4,3,T,T,T,T,T,T,0,0
db 3,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 0,0,0,T,0,0,0,D,0,0
db 0,5,0,T,T,T,T,T,T,0
db 5,4,5,0,0,0,0,0,0,0
db 4,3,T,T,T,T,T,T,0,0
db 3,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 0,6,0,T,0,0,0,D,0,0
db 6,5,6,T,T,T,T,T,T,0
db 5,4,5,6,0,0,0,0,0,0
db 4,3,T,T,T,T,T,T,0,0
db 3,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

db 7,6,7,T,0,0,0,D,0,0
db 6,5,6,T,T,T,T,T,T,0
db 5,4,5,6,7,0,0,0,0,0
db 4,3,T,T,T,T,T,T,0,0
db 3,2,1,S,1,2,T,T,T,T
db T,T,T,T,T,T,T,T,T,0

And so on...

So, if there is a path between S and D, an optimal path will ALWAYS be found. After that, it's just a matter of following increasing nodes towards D. Alternative approaches to this algorithm is an increasing wave front on Euclidian distance (when your character is allowed to move diagonally) instead of Manhattan distance (which I plotted above). You can also simultaneously start from D and work towards S - and you know the right path when the wave fronts collide.

By Manuel

Ascended (10030)

Manuel's picture

15-10-2007, 10:31

By jltursan

Paragon (1880)

jltursan's picture

15-10-2007, 10:31

One of the most used and well-known path finding algorithms is the A*. You can find a easily understandable guide here.
The only problem that comes to my mind is that most of those modern algorithms are pretty heavy for a humble Z80.

By ARTRAG

Enlighted (4675)

ARTRAG's picture

15-10-2007, 10:38

Dijkstra is also a good choice, and it's implementation, if metrics are all equal,
is close to wave propagation, but only the "good" fronts advance:

http://en.wikipedia.org/wiki/Dijkstra%27s_algorithm

By wolf_

Ambassador_ (9471)

wolf_'s picture

15-10-2007, 10:46

norakomi: are you up to some new project again?

btw, I'd rather try a workaround than A* on a Z80/3.58MHz .. Hannibal

By [D-Tail]

Ascended (8210)

[D-Tail]'s picture

15-10-2007, 11:53

A* is also pretty simple, easy to understand (intuitive); But I think it might be too exhaustive for MSX. Because, what happens when some variable obstacle blocks the path the character's currently moving on? That'd mean that the path search algorithm should be dynamically called. Pretty resource-consuming.

By wolf_

Ambassador_ (9471)

wolf_'s picture

15-10-2007, 11:56

Unless a map is rebuilt every moment, I'd use waypoints.., e.g. in a fixed map like Metal Gear/SD-Sn./anyRPG.

By norakomi

Paladin (961)

norakomi's picture

15-10-2007, 12:59

norakomi: try the wave propagation algorithm. Its performance is not really good (O[n^2]), but it will give you 100% correct and optimal result, all of the time. It works like this:

db 0,0,0,T,0,0,0,D,0,0
db 0,0,0,T,T,T,T,T,T,0.......................

And so on...

So, if there is a path between S and D, an optimal path will ALWAYS be found. After that, it's just a matter of following increasing nodes towards D. Alternative approaches to this algorithm is an increasing wave front on Euclidian distance (when your character is allowed to move diagonally) instead of Manhattan distance (which I plotted above). You can also simultaneously start from D and work towards S - and you know the right path when the wave fronts collide.Thanks a lot D-tail !!
This is perfect and will work for me.
I guess it will also be fast enough....

By norakomi

Paladin (961)

norakomi's picture

15-10-2007, 13:00

norakomi: are you up to some new project again?. Hannibalah, just playing a little bit...
coding for fun

Page 1/2
| 2
My MSX profile