Determining which choice is closer to another

[valkk]

Ok so my script is nearing completion. You guys have been a great help and I hope to call upon your services once again . This one might be a little more challenging, well at least it seems to me .

As I have said in some of my other posts, I'm making a pathfinder script. It takes your current position, takes your target position and finds the path to follow according to a list of preset points until you reach your destination. It's kinda neat and was interesting to program to say the least :">. I learned quite a lot, with your help of course.

Here's a more detailed description of the 3 functions and the ini.

pos.ini

A list of coordinates, numerically listed. Starts with X,Y and any number following that is the point# corresponding to one or more of the other points in the list which connect with this one. This is how the script knows which way to go. Notice most of the coordinates are negative, I just wanted to stick to one quadrant if I could and quadrant 3 having both a negative x and y integer, makes it the best place to find bugs .

findneardest()

Reads all available pre-set points from a ini file and determines which of the points is the closest one to your destination

findnearcurr()

Almost exactly similar to findneardest(), but this one determines which of the points is closest to your current location

selectpoints()

This is where the magic happens. It takes the closest point to your destination and makes it your starting point. Then it reads this point's # from the ini to determine which points it connects to. If there is only one option, it's forced to go to it. *However, if there are multiple connections the script picks the closest one to the destination to make sure it's going in the right direction.* Make sure to take note of what I said in that last sentense . This is how the script moves from one point to the next. The script cannot backtrack. If at point#2 and given 3 ways to go, one of which is the last point it was at, it will not check that previous point whether it's closer to the destination then the rest. The script continues until it reaches the final point closest to your destination.

PART THAT'S GIVING PROBLEMS

The script works suprisingly well, I thought I had it until this bug popped up. Lucky for me the grid points I have made up for testing range from every angle and position possible, well that's the point to find the bugs .

The bug I speak of is best described with a visual representation. Take a look at this.

This is a visual representation of all the points taken form the ini file. As you can see the path is all over the place. I wanted to make sure to test every turn, angle and position to squash all the bugs. It's been tricky, but I'm suprised I got this far . Notice points 1-4,31 have coordinates, x,y. Point 1 is simply where you start, points 2-4 is where the problem occurrs and point 31 is your destination. Whenever I look at something like this, I see PointA to PointB as a triangle. The horizontal and vertical differences are the width and height, with the distance being the hypotenuse. All the distances are pointed out in the picture above so you don't have to calculate that . The distance you calculate between one point and Point#31 differs from what the script returns because the script is calculating the distance to the destination, not the distance to the point nearest the destination. Since the destination is so close to point#31, it doesn't matter. Let's just say it's Point#31 to make things easy lol.

OK down to the problem. You'll see something interesting happen when you run the script you are currently at point#2. The script will look at point#3 and point#4 and determine which of the choices is a better way to reach your destination. When we look at the picture, it's pretty freaking obvious the answer is #3. However, the method I've been using to determine which one is best faults right here in this very example. The method, to calculate the hyptenuse and see which of the points checked has the smallest distance to the destination. This has been working well, but obviously I didn't expect this. Both of the points are going in the opposite direction then the destination. Point#31(destination) is South-East, while Point #4 is going North and Point#3 is going West. If you measure the distance, or hypotenuse, you'll see that Point#4 actually has a shorter distance to Point#31 than Point#3....DOH!!!! So here is where my method fails and I need to come up with something new .

This post is getting rather large, so instead of posting my ini and script I have linked to them. For some reason I couldn't attach them, even the script. Find it strange that an .au3 extension is not allowed lol. When you start the script, the current and destination are set as I have described, so straight from the start you'll have a problem. If you want to see the script miracleously work, enter the destination as indicated in one of the top lines of the script. I have made sure to add msgboxes to follow your current position and which points it's checking. When and "IF" the script finishes, reaching your destination, it will return ALL the points you have gone through. It's best to look at the picture and follow the operation of the script so you understand what the heck is going on lol .

As I said, I need to come up with a new method in determining which connection from your current point is a better option in reaching your destination. Currently the method used is determining the shortest distance between the point checked and the destination....is noooooo gooood!!! I'm pretty sure this is the last bug so I feel comfortable posting the whole script now. Save the best bug for the last huh? lol.

I need help, as usual, but umm....I promise not to bug you all for a while after this hehe . Actually, I'm going to take a little break form scripting

Script: PathFinder

Ini: Pos.ini

Image: Points.jpg

Edited August 26, 2004 by valkk

[valkk]

Oops forgot to mention a possible solution, the only one I can come up with, but it might result in more bugs .

I'm thinking completely not to backtrack. Not just to the previous point, but I mean ALL the points visited. If you run the script as it is, you'll see it makes the wrong choice at Point#2, going to Point#4 instead of Point#3. It will continue until it hits a dead end at Point#11. It sits there a couple times and then begins to backtrack. I know it's not suppose to backtrack but it's a flaw in my loop and the prevpoint is reset to the current if it sits at that same point a 2nd time. Once it reaches Point#2 again, it will sit there a couple times and redo the same mistake as before. I'm thinking if I somehow make it so it does not backtrack to any of the points visited and remembers them, lol, then eventually even after checking the wrong paths it will reach the destinatin .

I just thought of another solution after reading what I just wrote hehe. The script cannot backtrack but that ability fails if the script sits at one point twice. The prevpoint is reset to the current, so it will end up checking the previous point it was at although it shouldn't. If I can fix this, and instead of siting at the same point twice, force it to choose the other connection...that should do it right? So it will still initially choose the wrong path but when it comes to point#2 again it will be forced to choose the right one. Although, if I fix this then it might get stuck at dead ends like point#11. Phew, my head is spinning .

Edited August 26, 2004 by valkk

[Nutster]

This is in the class of combinitronics problems nick-named "The Travelling Salesman Problems". I am now wishing I had actually taken that class at university, instead of those stupid computer science and physics classes . Sorry I can not help more.

Edited August 26, 2004 by Nutster

[valkk]

This is in the class of combinitronics problems nick-named "The Travelling Salesman Problems".  I am now wishing I had actually taken that class at university, instead of those stupid computer science and physics classes    .  Sorry I can not help more.

<{POST_SNAPBACK}>

No wonder I can't figure this darn thing out, University is still ahead of me . Now I'm sure to take that course, maybe in a few years I'll finish my script haha . OK maybe I ain't that patient lol. Anyone know how to takle this problem? I'm going to see if I can scoop up some info on the internet about "The Travelling Salesman Problems"

[valkk]

I asked the same thing in the newsgroups and someone suggested to make the script list ALL the possible path options. Sounds difficult but I'm being told it's just a matter of finding the right algorithm.

From my coordinates list, including the path options for that particular point, it's a matter of choosing one of those path options and following it until another set of options is available, where one is chosen again. Eventually it will lead to a dead end, a place you've been before or your destination. That's when you should go back to the last point which had more then 1 path option and this time choose the other, follow it until the same thing happens, dead end, been there before or your destination. This cycle should continue for every point with more then 1 path option. If you are forced to backtrack, that's when the list should end.

Eventually you'll end up with A LOT of path lists ^^. This is probably the easiest part. Check each list for your destination point. The numbers between the start and the destination number of that list is your path. If multipe lists found your destination, the shorter list of points between the start and destination of that list means the shorter the path. Good way for finding the shortest path.

Been working hard trying to finish that pathfinder script; once I start, I have to finish no matter how hard it gets ^^. I have added quite a lot since I posted it here but my methods are never fool-proof, but now it seems I got to try something completely different. Fortunately this method seems like it can't fail so there's some hope. Now onto the part in figuring out how to code this algorithm or whatever you wanna call it.

If anyone in the future wants to work on something similar, this would be how to do it. Just thought I'll let those people know. I'll stop bumping my post now, obviously this is harder then I initially thought, but if anyone wants to lend a hand in figuring out this new method then I'm all ears.

Edited August 27, 2004 by valkk