Map-solving script

[php_joe]

Ok, I have a database with x/y coordinates, like a grid.

 

 

I'm trying to write a script that will find the shortest path from one point to another on the grid.

 

For example, if I remove some of the paths to make it look like this:

 

 

Then the scrip might come up with something like this:

 

 

I'm just getting started on this, so any suggestions are appreciated

[php_tom]

How big is your map going to be? If it's reasonably small (maybe a 10 x 10 grid or so), you could just try all possible paths, tally their lengths, and pick the shortest one. But for a big map this is unfeasible, you would need graph theory and stuff. I only know a bit about this... check out the links below:

http://en.wikipedia.org/wiki/Graph_theory

http://en.wikipedia.org/wiki/Shortest_path_problem

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

Please post back with details of what exactly you're trying to do.

[dbo]

God I had to do this crap in a CS class once!

[php_joe]

php_tom:

Eventually it will be getting pretty large.

 

I have considered using that method, and breaking the map down into areas. I could have the shortest route through each area preset, so the script would only have to find the shortest route out of the starting area and to the final point in the final area.

 

I was just hoping that there was a better way. 

[dbo]

php_tom gave some good advice. There is a lot of theory and proven algorithms to solve this exact problem. I wouldn't attempt to reinvent the wheel if I were you and leverage one of the existing algorithms.

[php_tom]

I was just hoping that there was a better way. 

 

If you find one, you can probably get at least a masters degree at your pick of Ivy League graduate schools . (I.e., probably not easy to come up with a better solution).

 

Are you implementing a game? If you're trying to figure out the optimal path for scoring, maybe it's easier to come up with a better scoring scheme... it's just an idea.

[php_joe]

I'm looking at tom's pages now. I have no desire to re-invent so much as a screw. 

 

This is for an RPG that I'm trying to build. It's a simple grid layout and I want the characters to have the ability to click on a point and walk there.

[php_joe]

Please post back with details of what exactly you're trying to do.

 

I play a game called Dark Swords (see my sig), which I like and I'd like to make one that is similar (but not a copy, I'm not a thief).

 

The game is a 2-D game with a map layed out as a block-style grid. you can walk around by pressing the arrow keys on your keyboard or "auto-walk" to a distant location by double-clicking on that square on the map.

 

I think that I can figure out how do duplicate most of the game's functions using PHP and JavaScript, but I'm having trouble figuring out their auto-walk feature...

[btherl]

If your map is as simple as a grid (with equal weights on every edge), then you could use some heuristics to improve your path finding algorithm.  For example, if you find a path which never moves away from the destination at any step, then you have a shortest path.  This is not true in general, only for the example map you showed.

 

Similarly, you might want to check a straight line first, hoping that there is no need to run a full path-finding algorithm

 

Once you have different costs associated with particular steps (such as different terrain), all bets are off.  But you may be ok with a "shortest path" which is not necessarily the fastest path.

[cooldude832]

The answer your question is nothing to do with sql (well it does, but anyways) it is all mathmatics.  The idea is a simple linear progression where at each point it runs a check. 

 

You start at (0,0) and you are moving to (5,6) for say.  Each possible move is either X+1 or Y+1.  Therefore you set up a script to say first get your start point then check what that for each possible move gets you.  If there is only one choice it accepts that, if there are 2 you say pick 1 and store it in the array as ($pick[]= "$X"._."$Y" so incase you reach a dead end and have to make a choice you see if one of the choices is a pick you have made already.  If so make one that isn't.  Eventually you will find as a result all possible paths from Point A-Point B since you are logging each attempt as a new array ($path[][]) you say foreach($path[] as $value){ $path_lengths[] = count($value);}  then simply find the smallest value in the array $path_lengths and you have the shortest path.  It is a bit of work, but can be done.  For a 10x10 grid your premutations is somewhere around 100-100000 depdendning on the number of aviable paths and choices at each point.

[php_joe]

Thanks for the great posts guys, you've given me a lot to work with.

 

now if I can just manage to wrap my brain around it :-\ (why do I always pick such difficult projects???)

[cooldude832]

Don't think of it too linearly and physically, but more conceptially.  Use the power of the comptuer not to find the best route, but all routes (store the route in an array $paths[][] and then count the number of steps in each $paths[] and since the weighted value of each individual step is equal to the weight value of any other step its the net integration of the sums of those weighted values that determines the length of the path.  Therefore its a simple minimization based on calculus you could write alogrthims that might suggest the shortest path.  Also you can build in a function that thinks in a more logical idea in which it knows what the minimal number is if all paths exsitist and then start working off that so called optimal situation and find the closet path to this so called ideal path.  This is a bit more complex, but if the permutations of paths is greater than 1000 it might save you a great deal of time in  testing.  This would require some complicated metric geometry and object oriented calculus, but needless to be said it can be done.  In all cases the programing end it will be best to recreate the map in some sort of array and then off that you might be able to rationalize some things based on the number of possible paths in each X/Y row that gets from Point A to Point B.  For example if we need to get from (1,1) to (5,5) but on the line y=4 there is only one point (1,4) then we know the only possible path is one in which it goes through (1,4) so we can work out in a more linear pattern from it (since 1,4 only connects to 2,4 1,5 and 1,3)  Just some ideas to throw out there.  A lot of it is probably way to mathematical to really grasp, but its there.

[php_tom]

Hey, I'm thinking that since you are using a square map, here's an algorithm that might work:

1) You start somewhere, say, (x_i, y_i).

2) You have at most four possible moves; (x_i+1, y_i), (x_i, y_i+1), (x_i-1, y_i), (x_i, y_i-1), or maybe less if the grid is sparse.

3) For each of these four points, calculate the linear distance between it and the destination (using pythagorean theorem) -- abs(x_i - x_f)^2 + abs(y_i - y_f)^2 = d^2.

4) Pick the point with the smallest resulting linear distance.

5) If two or more points have the same linear distance, repeat the algorithm for each point and go with the smallest resulting distance (this could probably be done with a recursive function).

 

The above algorithm will hang... if your map has something like

|-|-|-|-|-|-|  |-|-|-|-|-|O|-|-|-|

|-|-|X|-|-|        |-|-|-|-|-|-|-|-|

|-|-|-|-|              |-|-|-|-|-|-|-|

|-|-|-|-|-|        |-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

(I hope this comes out.)

where X is the beginning and O is the destination... maybe you can add a piece of code that checks if the algorithm is stuck in a corner or whatever (by checking if each possible move takes you FARTHER away from the destination), then starts over again but throws away that path as a possibility.

 

Have fun coding this! I know I would...

[cooldude832]

yeah kinda what i was saying, but you see in the middle there is only one option (the bottom row) you should start from there and find the shortest 2 paths from there (sorta dividing it up) so basically you eventually develop a derivative based on A-B creating this infinite number of points in between A-b (well finite in this case since we are using a grid) And then like I said store each one as an array node and simply count each array to find the shortest path (since each point's weighted value is equal to that of any other)  How to do it in php/mathmaticalls is beyond me, but I can grasb it conceptually.  You might want to look into gradiante vectors as this seems like the idea, but since its such a linear progression you really can skip all the calculus and look at it form a 2 scenario point.

[btherl]

cooldude, I'm a pure mathematician and even I am confused by your posts  ???  Please use paragraphs, and give examples where possible.

 

Regarding the "always move closer" idea, it will need to have backtracking (in some form) to handle dead ends.  An efficient way to do this might be to mark a map location as "dead end", and eliminate it from all further processing.  Then it will never be considered in any further paths.  Then you take a step back, and continue with the same algorithm, but disregarding the locations now marked as "dead end".  In this way, you progressively eliminate dead end locations without having to process each dead end location more than once.

 

Of course there will be some maps for which this performs terribly.. so a lot depends on what the maps actually look like.  Arguably, path finding should not be implemented for mazes, because the user should be solving the maze himself   So in practice I imagine the maps will be simpler than a maze?

[cooldude832]

give me Five minutes and I'll explain, I do mathematical modeling at my university and general people say I can't articulate my ideas very well, but once they can understand it they say it makes perfect sense.

[cooldude832]

okay using the grid made

|-|-|-|-|-|-|  |-|-|-|-|-|O|-|-|-|

|-|-|X|-|-|        |-|-|-|-|-|-|-|-|

|-|-|-|-|              |-|-|-|-|-|-|-|

|-|-|-|-|-|        |-|-|-|-|-|-|-|-|

|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|-|

 

we need to get from the X to the 0.  Now I see from the X you have 4 possibilities (up, down, left, right)  From that We know nothing about which could be the best path.  While we can make a generic assumption that Up/ Right will be your best ideas because that is the general directional derivative from point X to O, however that does not mean it is the best direction in which we should travel because in this sort of model our solution is 100% path dependent.  Although more than 1 fastest path may exist, each point on that path is important and relative to the final solution.  So after realizing this I made the postulate that we must check out all possible paths (with in reason) that could get us from X to O.  Since I realized path is our number one key here the next thing I said well this is a grid so we can assume each possible positioning will have some counting number value for X and Y.  So then What I do is look at all the equations for X=c and Y=c where c is any value between and including x(x,y) and o(x,y).  As I suspect I find that there is one line in which there is only 1 solution for which Y can sustain the value C (its that bottom middle path).  In knowing this I know that my path must navigate through this point to be a valid solution from O-X.  Now knowing this I have 2 smaller paths to solve (I will call this new point & for ease of writing).  I have the path from X-& and the path from &-O.  In which case the number of Good solutions is dramatically less (even adding up both ones) than if I was to say to X-O.  Now its just simple linear progression to find all paths that are within say 5 of the ideal path (which is a straight line from start to end).  Then i can sum up and I have a simple solution that should be the best path.  As you can see we can find more refinements where if there was only 1 choice between &-X then we could have 3 sums of 1 being larger than the other 2.  Now if the case of 1 possibility does not exist than we look for the lowest integer value as our starting point and work out from there (could be 2,3,4 or more possibilities).  My idea is to sub divide the path X-O into smaller paths that have a smaller range of tolerance and then sum up those paths.

[btherl]

Thanks, that makes much more sense   But please, paragraphs!  Paragraphs!  Paragraphs!

 

So after realizing this I made the postulate that we must check out all possible paths (with in reason) that could get us from X to O.

 

It may not always be necessary to check all possible paths for two reasons

- We may be able to accept an approximate solution.

- In the case of a grid with equal weighted edges, any "direct" path is a shortest path (none exists in the example above though).  A "direct" path is any path where all steps are in the direction of the "general directional derivative" from point X to O.  In this example, all steps would have to be up and right, and no direct path exists.

 

So then What I do is look at all the equations for X=c and Y=c where c is any value between and including x(x,y) and o(x,y).  As I suspect I find that there is one line in which there is only 1 solution for which Y can sustain the value C (its that bottom middle path).  In knowing this I know that my path must navigate through this point to be a valid solution from O-X.  Now knowing this I have 2 smaller paths to solve

 

What is the algorithm by which you find this point "&" ?  I agree that it exists, but I don't see any efficient method of finding it.

[cooldude832]

its really point that is the only point on a line x=c or y=c so if we start at (1,3) and we are going to (5,5) its really any point between those points so X can be 1,2,3,4,5 and Y can be 3,4,5 and then if you find a line in which there is only one point then you know you have to go throught there.  Example if i'm at x=4 and i need to end up at x=6 and there is only one possible Y that satisfies x=5 then the only solution is a line through that point.

 

(paragraph 2 )

 

As for the all possible solutions yes you must, but however if you find a solution that is say 10 steps and then you start another check and you get over 10 steps you can break that test because you know its too many steps.  This will throw out a lot of the paths possible.  As for keeping track of them that is a nightmire.

[btherl]

... Example if i'm at x=4 and i need to end up at x=6 and there is only one possible Y that satisfies x=5 then the only solution is a line through that point.

 

Hmm.. so you are checking if there is any x for which there is only one valid y, and vice versa?  That check will be quite fast to do.  I can imagine situations where the check will not succeed even though there is only one path, but that can't be helped.  Eg.

 

|X|-|  |-|O|

|-|    |-|-|

|-|  |-|-|-|

|-|-|-|-|-|

 

Here there is a choke point at the bottom, but it can't be detected by a simple check, because there are 2 valid values of y for each value of x.

 

As for the all possible solutions yes you must

 

Why must we?  I still disagree with this assumption   I think we should forget about checking all paths, and go for an algorithm which gives a "reasonably good" path.

[cooldude832]

Yes I agree the mathematical optimized first run is the best idea, but this asked for best path.  Also in your example it will quickly dead end because in my concept for a point to be considered valid it must have 2 points of continuity You can throw out that top point . Guess I didn't point that out, just thought it was assumed that for a point to be valid you must be able to gain some sort of net displacement otherwise its a meaningless point and can be ignored.

[cooldude832]

You can think of it like that game lightsout if a square is determined to be useless you can ignore it (black it out) and then ignore any path that would invovle traveling through that point.  Eventually the idea is to come up with some sort of optimial situation for x,y in each case based on the paths next to it up,down,left,right and go from there

[php_joe]

yes, except for one or two cases, the maps would be much simpler than mazes.

 

I guess that one solution, that would prevent getting stuck in a corner, would be to:

- first check if a direct route is possible, if not:

- find a route along the edge

- count the steps

- check each possible route, giving up when the step-count exceeds that of the edge route

 

Or if a direct route is not possible you could attempt a direct route, walking around obsticles, and then use that route's step-count to search for a shorter route.

[cooldude832]

we're looking at a more mathmatical solution.  A idea I had is to give a quality rating to each point based on its variance off a straight line and then find the path made of the most high quality points and see how long that is.  Of course you would then need secondary logic that involves checking if its going out of its way.

[btherl]

Also in your example it will quickly dead end because in my concept for a point to be considered valid it must have 2 points of continuity You can throw out that top point

 

What about this case?

 

|X|-|  |-|O|

|-|-|  |-|-|

|-|    |-|-|

|-|  |-|-|-|

|-|-|-|-|-|

 

All points now are connected to at least 2 other points.  The dead end is there, but expanded.