[RESOLVED] VB6.0: I need help debugging A* pathfinding program please.

[Tontow]

I have attached the project to this posting as BuggedPathfindingAttempt.zip .


I can't seem to find the bug. I start at 308,308 with a destination of 300,300 as called in the form_load of form1.
But for some reason it bugs out and suddenly jumps to 615,616 and then again to 1230,1231. I can't figure out how it can make such large jumps in only 20 moves.

Please help me find the bug.





Debug output of the x,y cornet with the lowest F cost. This debug.print can be found in FindAndDrawPath.

308,308
615,616
616,615
616,617
617,616
1230,1231
1229,1232
1232,1229
1231,1230
1233,1230
1230,1233
1232,1231
1231,1232
1232,1233
1233,1232
1231,1234
1234,1231
1234,1233
1235,1232

A bit more on how the program is suppose to work:

I use a binary heap to sort PathOpen()'s .F value so that the lowest .F is always at PathOpen(0).
Binary heap functions are named BinaryHeapRemove and BinaryHeapAdd, but seem to be working correctly as far as I can tell. - Form2 has a text box that displayes the contents of the heap and appears to be sorted correctly.

PathClosed is my closed list. PathClosedList(5000, 5000) is used to quickly check of a node (x,y cordnet) is closed and stores an index number that refers to PathClosed. - PathClosedList will also be used in the yet to be done sub that will be able to quickly trace the path once it has been found.

Sub CheckAndMove checks to see if a node is closed using Function IsPathClosed .
If a node is open then Function CalcGCost calculates the G cost; a cost of 10 if moving straight and a cost of 15 if changing direction. MyEndPoint is going to be used to find the turns when tracing the completed path.
Then the node is added to the heap via Function BinaryHeapAdd.

[Tontow]

After a good nights rest and some coffee I've managed to fix the bug mentioned in the first post. I had a few of my function/subs called with incorrect values.

I have attached the fixed version; I have finished the trace back and line drawing functions. Just click on the form to draw a path to the 300,300 cornet.

But now a new bug has popped up. The lines are supposed to only be drawn horizontally and vertically. But in certain areas one of the lines draws at an angle.

I would be grateful to anyone who helps me track and smash this intermittent bug.

[Tontow]

Still haven't been able to figure out the reason for the bug; I'm just not seeing how its working perfictly from one coordinate, but bugs on another.

I just need help tracking down the reason for the bug; I don't expect someone to completely rewrite it, just point me in the right direction.

[Tontow]

I finally got it right after trying to rewrite the trace back/line drawing part of the code 10 times.

Dim CXY() As MTXY
Dim SXY As MTXY
'set up for frist trace step
ReDim CXY(0) As MTXY

CXY(0).X = tempB(0).X
CXY(0).Y = tempB(0).Y
SXY.X = tempB(0).X
SXY.Y = tempB(0).Y


'Debug.Print PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Px & "," & PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Py
Do
    'below is the correct do until loop, finally figured out how to access the correct point....
    Do Until PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).EndPoint = True
        ReDim Preserve CXY(UBound(CXY()) + 1) As MTXY
        CXY(UBound(CXY())).X = PathClosed((PathClosedList(CXY(UBound(CXY()) - 1).X, CXY(UBound(CXY()) - 1).Y) - 1)).Px
        CXY(UBound(CXY())).Y = PathClosed((PathClosedList(CXY(UBound(CXY()) - 1).X, CXY(UBound(CXY()) - 1).Y) - 1)).Py
        'use the following to call arrowtip
        'Debug.Print PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Px & "," & PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Py
    Loop
    Call ArrowTip(PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Px, PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Py, SXY.X, SXY.Y)
    SXY.X = PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Px
    SXY.Y = PathClosed((PathClosedList(CXY(UBound(CXY())).X, CXY(UBound(CXY())).Y) - 1)).Py
    ReDim Preserve CXY(UBound(CXY()) + 1) As MTXY
    CXY(UBound(CXY())).X = PathClosed((PathClosedList(CXY(UBound(CXY()) - 1).X, CXY(UBound(CXY()) - 1).Y) - 1)).Px
    CXY(UBound(CXY())).Y = PathClosed((PathClosedList(CXY(UBound(CXY()) - 1).X, CXY(UBound(CXY()) - 1).Y) - 1)).Py
Loop Until SXY.X = x1 And SXY.Y = y1

I don't know if that bit of code can be rewritten so that its faster, but I have attached the working project.