Printable View
I’m having a hard time tracking down a bug in my program; under certain conditions the program results in an infinite loop.
Will someone Please help me track down this bug?
The program is suppose to use A-Star path finding to find a path around the image boxes and then draw arrows that indicate the path from where the user clicks to a predetermined point.
The error seems to occur when I click somewhere above the top middle or below the bottom middle images.
I have attached the program below.
Please give me some clue as to how the program is supposed to operate. If I simply click Command1 I (of course) get a Type Missmath error because you aren't converting the textboxes' inputs and if I enter 5 in Text1 and 6 in Text2 and then click Command 1 it runs for a while and then ends with a very uninformative "Error" message.
I'm in no state or inclination to study your code too closely but it seems to crap out on the routes that involve going back on itself... It gets so far and then won't move away from the target only towards and gets itself stuck.
I've only had a go at a routefinder once, it was recursive. It took a stab at the best route using logic and then used results to brute force other routes using the best result so far as the depth.
Sorry for providing insufficient information. I hope the following answers your questions.
Program Details:
Program Goal:
To draw a series of up, down, left, right arrows from point A to point B while avoiding going through the images and taking the fewest turns and taking the shortest path.
Main Methods Used:
This is an A-Star path-finding program. For information on the A-Star (A*) path-finding method, please see http://www.policyalmanac.org/games/aStarTutorial.htm .
This program uses a binary heap to sort PathOpen().F values so that the lowest PathOpen().F value is always located in PathOpen(0). For more information on binary heaps, please see http://www.policyalmanac.org/games/binaryHeaps.htm
Usage:
The left text box is for X cornets, the right text box is for Y cornets. The command button uses the cornets in the text boxes and passes them to the function FindAndDrawPath. Be careful to only use multiples of 5 or the program will most definitely be locked into an infinite loop; if you look in FindAndDrawPath, then you will notice that the program checks only the cornets that are a multiple of 5.
Function Information:Code:Private Sub Command1_Click()
Dim XA As Long
Dim YA As Long
XA = Form1.Text1
YA = Form1.Text2
Call FindAndDrawPath(5000, 5000, XA, YA, False, 40)
End Sub
FindAndDrawPath is the main function of the program; it contains the primary Do loop that calls the rest of the functions.
First it resets the variables.
Then It calls BinaryHeapAdd to add the starting cornet to the Open list ( PathOpen() ).
Now we are in the Do loop.
To avoid errors, it copies PathOpen(0) to tempB(0) so that calling BinaryHeapAdd doesn’t change the next cornet that needs to be checked; PathOpen(0) will always have the lowest .F value and is therefore assumed to be the closest to the target end cornet.
Between the notations “'start debug” and “‘end debug” is code from my failed attempt to trace the error and to exit the Do loop when there is danger of an infinite loop ( MsgBox ("ERROR!!") ).
BinaryHeapRemove is then called to move PathOpen(0) to the closed list ( PathClosed() ).
The following four If IsPathClosed = false statements check to see if the cornets right, down, left, up of the current cornet are on the closed list ( PathClosed() ). If the cornet is not on the closed list, then calculate the F cost and add the cornet to the Open list ( PathOpen() ) via BinaryHeapAdd.
F is F = G + H OR F = Move Cost + Estimated distance to end cornet. Note that I subtract 2 from G once I hit the same X or Y cornet; this influences the final path.
After the target cornet is reached it traces back and draws arrows on the way.
It is called as follows:
Code:Call FindAndDrawPath(End X, End Y, Start X, Start Y, Unused at this time, Unused at this time)
GetallClosed() is the old method I used to avoid lines going through the images; this was incredibly slow so I commented it out and added the check in IsPathClosed.
IsPathClosed() dose 2 searches. First it checks the given cornet to see if it is listed in PathClosed(), returns true if it is.
Then a check is done to see if an image covers the cornet; this check eliminates the need for GetallClosed() and shaves a good deal of time off of finding a path.
ArrowTip() draws a arrow.
BinaryHeapAdd adds a cornet to PathOpen() using the binary heap method. The binary heap is sorted by the value of .F with the lowest value always being at PathOpen(0).
BinaryHeapRemove moves the cornet stored in PathOpen(0) to PathClosed() by copying PathOpen(Ubound(PathOpen())) to PathOpen(0) and then shrinking PathOpen() by 1 ( ReDim Preserve PathOpen(UBound(PathOpen()) - 1) ). It then makes the Binary Heap a valid Binary Heap (see links above on Binary heaps).
CalcGCost returns the G cost of F = G + H . G is plus 10 if moving in a striate line. G is plus 15 if the move is a turn.
FindPoint() returns the next cornet needed to draw an arrow. (see end of FindAndDrawPath)
This sounds like your program has decided a path is closed when it's not. If you are trying to find the best solution to finding a route then personally I would use a recursive function to generate the route, where every depth into the recursion would be the next direction change. I would be happy to have a go at this later (tonight GMT) if you are interested, in fact I might do it even if your not interested :D
Set up a representation of the paths first then process the array http://www.vbforums.com/showthread.p...highlight=path then draw the shortest path determined.
Yes I am interested, thank you.Quote:
Originally Posted by Milk
When you make your attempt remember that it needs to:
-Be fast.
-Move only in the up, down, left, right directions.
-Find the shortest possible path.
-Contain as few direction changes as possible.
-Trace the path with lines or arrows
Thanks for the link, but.Quote:
Originally Posted by leinad31
Isn't that Dijkstra? (F=G instead of the A-Star method of F=G+H)
Dijkstra is faster than A-Star on shorter distances only; however, on longer distances Dijkstra is less efficient and is slower than A-Star.
hmm, I've an algorithm in the making but I need more time. Theory:- Find a route by always choosing the direction that will get me closest, then 2nd closest, then a little bit away, then further away. After every time the route goes back on itself (i.e. away from target) continue until a forward looking node is available then rerun the recursive algorithm between the latest forward looking node and previous nodes (starting with the first). Repeat until best route is found.
I love this sort of thing. I'm not necessarily very good at it :D
http://www.gamasutra.com/features/19...athfinding.htm
Its a very good read, it tells and shows you the stregths and weeknesses of each method discribed.Quote:
Smart Moves: Intelligent Path Finding: This article by Bryan Stout at Gamasutra.com requires registration to read. The registration is free and well worth it just to reach this article, much less the other resources that are available there. The program written in Delphi by Bryan helped me learn A*, and it is the inspiration behind my A* program. It also describes some alternatives to A*.
I also found "Singularis' A* Path Finding Implementation" somewhere on these forums. A decent program, but it bugged on a few mazes that I made.