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

Page 1/2
| 2

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

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

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

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.

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.

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:

norakomi: are you up to some new project again?

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

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.

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

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

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

Page 1/2
| 2