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

Paragon (1150)

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

Aangemeld of registreer om reacties te plaatsen

Van snout

Ascended (15187)

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! ^_^

Van [D-Tail]

Ascended (8263)

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.

Van Manuel

Ascended (19688)

15-10-2007, 10:31

You might want to check Google

Van jltursan

Prophet (2619)

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.

Van ARTRAG

Enlighted (6979)

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

Van wolf_

Ambassador_ (10135)

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

Van [D-Tail]

Ascended (8263)

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.

Van wolf_

Ambassador_ (10135)

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.

Van norakomi

Paragon (1150)

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

Van norakomi

Paragon (1150)

15-10-2007, 13:00

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