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

(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:

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

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.

Quote:

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

Quote:

norakomi: are you up to some new project again?.

ah, just playing a little bit...
coding for fun

Glad to be of service. In other news, norakomi: did you receive my e-mail? If so, please reply ^_^

Quote:

Glad to be of service. In other news, norakomi: did you receive my e-mail? If so, please reply ^_^

i have
im trying to reply,
but
This is an automatically generated Delivery Status Notification

THIS IS A WARNING MESSAGE ONLY.

YOU DO NOT NEED TO RESEND YOUR MESSAGE.

Delivery to the following recipient has been delayed:

d-tail@msx.org

this keeps popping up my inbox....

o_O!! Then there must be something wrong with the MRC mailserver. Either that, or SpamAssassin isn't working properly. I'll axe snout. In the meantime, why don't you use my other mail address? You'll find it in my profile. Of course, it should end with '.com' Thanks in advance!

Quote:

norakomi: are you up to some new project again? btw, I'd rather try a workaround than A* on a Z80/3.58MHz ..

I've implemented the A* algorithm in z80 already. You can have a look at it here:
http://www.z88dk.org/wiki/doku.php/library:algorithm

and the source code of the main search function:
http://z88dk.cvs.sourceforge.net/z88dk/z88dk/libsrc/algorithm/AStarSearch/astar_Search.asm?revision=1.1&view=markup

The latter uses a heap data type (again implemented in asm) to implement a priority queue.

All totally untested but my code is always logically correct and quite often works first time :-D I just haven't had time to finish off the documentation and make sure it works. In particular "reading out the found path" can be made more user-friendly.