A* Pathfinding.

[pr0gger]

This is the error I get with the -ex tag (I compiled and ran it using a batch file).

Code:

C:\Freebasic>path2.exe

Aborting program due to runtime error 4 (out of memory)

C:\Freebasic>pause
Press any key to continue . . .

--j_k

[Agamemnus]

You have an array out of bounds error that quickly becomes an out of memory error because of bad numbers. The reason why they are different? Probably something accessed outside the program...

[pr0gger]

Now, there's the root of my problem-- there's pretty much nothing I can do to fix this. :-?

--j_k

[Sisophon2001]

That's helpful

So I rewrote the code using arrays, but I've come across a bug that I can't fix. It seems to be a memory problem in the OS itself. :/

<snip>

--j_k

Hi:

You are re-dimensioning a local variable that is not declared as dynamic. I am not sure of QB or FB syntax rules here, but I would not have coded it like this, and if you make your arrays dynamic then it does not crash.

Try:
redim OpenList(1 to 1) as PathListElement
redim ClosedList(1 to 1) as PathListElement

Have fun.

Garvan

[Agamemnus]

With that fix it does not seem to actually work anyway.. I set up a barrier and it seemed to ignore it..

[Torahteen]

Well... Back to your original Q, I read the tut. I've even started my own A* project, hehe. Sorry. Anyway...

What you need to do, is take the G Score of the square you are checking. Next, add the G Cost of that square (How much it will cost to move to that square) to the current G Score of your "Current" square. If the sum is less than the G Score of the square you are checking, then this way is faster and hence the better way to go. Change the parent square of the square you are checking to the "current square.

Look at the diagram in the Tutorial. They are very helpful. If you don't get it still, then ask.

[Torahteen]

Hey, have you made any progress? If so, join us at the "My Try At A*" post in the FB projects forum.

[pr0gger]

That's helpful

So I rewrote the code using arrays, but I've come across a bug that I can't fix. It seems to be a memory problem in the OS itself. :/

<snip>

--j_k

Hi:

You are re-dimensioning a local variable that is not declared as dynamic. I am not sure of QB or FB syntax rules here, but I would not have coded it like this, and if you make your arrays dynamic then it does not crash.

Try:
redim OpenList(1 to 1) as PathListElement
redim ClosedList(1 to 1) as PathListElement

Have fun.

Garvan

It works :o Thank you.

Torahteen: Thanks, I'll check it out.

--j_k

[pr0gger]

Right, so here's the new code. Before, the parenting wouldn't work; now it does. All I have to do now is the backtracking (looking at a squares parent, then looking at that squares parent, etc).

Code:

DEFINT A-Z

TYPE pathListElement
    r AS INTEGER
    c AS INTEGER
END TYPE


DECLARE SUB pathFind (StartR, StartC, EndR, EndC)
DECLARE FUNCTION pathIsWalkable(r, c)
DECLARE SUB pathDrawMap(startR, StartC, EndR, EndC, OpenList() AS pathListElement, ClosedList() AS pathListElement)
DECLARE SUB pathRemoveFromList(list() AS pathListElement, index AS INTEGER)
DECLARE SUB pathAddToList(list() AS pathListElement, r AS INTEGER, c AS INTEGER)
DECLARE SUB pathSortByCost(list() AS pathListElement, cost() AS INTEGER)
DECLARE FUNCTION pathIsInList(list() AS pathListElement, r, c)
DECLARE SUB pathRemoveCoordsFromList(list() AS pathListElement, r AS INTEGER, c AS INTEGER)

DIM SHARED MapW AS INTEGER, mapH AS INTEGER

READ MapH, MapW
DIM SHARED Map(MapH, MapW) AS INTEGER

SCREEN 0

FOR R = 1 TO MapH
    FOR C = 1 TO MapW
        READ Map(R, C)
    NEXT
NEXT

pathFind (4, 3, 4, 7)

SLEEP

END

DATA 7, 9
DATA 0, 0, 0, 0, 0, 0, 0, 0, 0
DATA 0, 0, 0, 0, 0, 0, 0, 0, 0
DATA 0, 0, 0, 0, 1, 0, 0, 0, 0
DATA 0, 0, 0, 0, 1, 0, 0, 0, 0
DATA 0, 0, 0, 0, 1, 0, 0, 0, 0
DATA 0, 0, 0, 0, 0, 0, 0, 0, 0
DATA 0, 0, 0, 0, 0, 0, 0, 0, 0

SUB pathFind (StartR, StartC, EndR, EndC)

    REDIM OpenList(0 TO 0) AS PathListElement
    REDIM ClosedList(0 TO 0) AS PathListElement
    
    DIM f(MapW, MapH) AS INTEGER
    DIM g(MapW, MapH) AS INTEGER
    DIM h(MapW, MapH) AS INTEGER

    DIM ParentR(MapW, MapH) AS INTEGER
    DIM ParentC(MapW, MapH) AS INTEGER
    
    DIM r1 AS INTEGER, r2 AS INTEGER, c1 AS INTEGER, c2 AS INTEGER
    DIM CurrentR AS INTEGER, CurrentC AS INTEGER, r AS INTEGER, c AS INTEGER
    DIM gAdd AS INTEGER, cr as integer, cc as integer
    DIM LowestFR AS INTEGER, LowestFC AS INTEGER, i AS INTEGER


    'PRINT OpenList(1).r; OpenList(1).C
    pathAddToList OpenList(), StartR , StartC           'Add starting square to open list
    
    
    DO UNTIL UBOUND(OpenList) = 0 or pathIsInList(OpenList(), EndR, EndC)

        pathSortByCost OpenList(), f()
        CurrentR = OpenList(1).r
        CurrentC = OpenList(1).c

        pathRemoveFromList OpenList(), 1
        pathAddToList(ClosedList(), CurrentR, CurrentC)  'Add current node to closed list

        r1 = CurrentR - 1 : c1 = CurrentC - 1       'Checking adjacent squares
        r2 = CurrentR + 1 : c2 = CurrentC + 1
        
        'OpenList(1).r = OpenList(UBOUND(openList)+1).r
        'OpenList(1).c = OpenList(UBOUND(openList)+1).c
        IF r1 < 1 THEN r1 = 1                       'Clipping, so we don't check squares that don't exist (that are off the map, literally)
        IF c1 < 1 THEN c1 = 1
        IF r2 > mapH THEN r2 = mapH
        IF c2 > mapW THEN c2 = mapW
        FOR r = r1 TO R2
            FOR c = c1 TO c2
                IF pathIsWalkable(r, c) AND pathIsInList(ClosedList(), r, c) = 0 and not (CurrentR = r and CurrentC = c) THEN   'Make sure we can go there, and that we're not on the closed list
                    IF pathIsInList(OpenList(), r, c) = 0 THEN          'Make sure we're not already on the open list

                        pathAddToList(OpenList(), r, c)  'Add node to open list

                        ParentR(r, c) = currentR
                        ParentC(r, c) = currentC
                        
                        IF R = CurrentR OR C = CurrentC THEN
                            gAdd = 10
                        ELSE
                            gAdd = 14
                        END IF

                        g(r, c) =  g(CurrentR, CurrentC) + gAdd
                        h(r, c) = 10 * (ABS(EndR - r) + ABS(EndC - c)) - 10
                        f(r, c) = g(r, c) + h(r, c)
                        
                    ELSEIF pathIsInList(OpenList(), r, c) <> 0 THEN
                        IF R = CurrentR OR C = CurrentC THEN        'Check to see if this path is better
                            gAdd = 10
                        ELSE
                            gAdd = 14
                        END IF
                        tempG =  g(CurrentR, CurrentC) + gAdd
                        locate 10,1: print currentR; currentC
                        locate 11,1: print r; c
                        locate 12,1: print tempG; g(r, c)
                        
                        if tempG < g(r, c) and NOT (CurrentR = r and CurrentC = c) then
                            'LOCATE 13, 1: PRINT "blah": sleep
                            ParentR(r, c) = CurrentR
                            ParentC(r, c) = CurrentC
                            g(r, c) = tempG
                            h(r, c) = 10 * (ABS(EndR - r) + ABS(EndC - c)) - 10
                            f(r, c) = g(r, c) + h(r, c)
                        end if
                    END IF
                END IF
            NEXT
        NEXT
        pathSortByCost OpenList(), f()

        'print CurrentR, CurrentC: sleep
        pathDrawMap(startR, StartC, EndR, EndC, OpenList(), ClosedList())
        LOCATE CurrentR, CurrentC: PRINT "X"
        
        locate 10,1: print OpenList(1).r; OpenList(1).c
        'for n = 1 to UBOUND(OpenList)
        '    r = OpenList(n).r
        '    c = OpenList(n).c
        '    PRINT r; c; "("; f(r, c); ")";
        'next
        'sleep
        
    LOOP
    'sleep
    LOCATE 10,1:
    for r = 1 to MapH
        for c = 1 to MapW
            LOCATE  r + 10, C * 9 -8
            COLOR 15: PRINT r; c;
            COLOR 7: PRINT ParentR(r, c); ParentC(r, c);
        next
        
    next

END SUB

FUNCTION pathIsWalkable(r, c)
    IF map(r, c) = 0 THEN pathIsWalkable = -1
END FUNCTION

SUB pathDrawMap(startR, StartC, EndR, EndC, OpenList() AS pathListElement, ClosedList() AS pathListElement)
    CLS
    DIM r, c, text$

    FOR r = 1 TO MapH
        FOR c = 1 TO MapW

            COLOR 7: text$ = "."
            'if r = StartR and c = startC then
            '    text$ = "S"
            'elseif r = EndR and c = EndC then
            '    text$ = "E"
            'end if
            IF pathIsWalkable(r, c) = 0 THEN
                text$ = chr$(219)
            END IF
            IF 0 <> pathIsInList(OpenList(), r, c) THEN
                COLOR 10
            ELSEIF 0 <> pathIsInList(ClosedList(), r, c) THEN
                COLOR 11
            END IF
            LOCATE R, C: PRINT text$

        NEXT
    NEXT

END SUB

SUB pathRemoveFromList(list() AS pathListElement, index AS INTEGER)
    DIM i
    DIM listElements
    listElements = UBOUND(list)
    if listElements = 0 then exit sub
    FOR i = 1 TO listElements - 1
        IF i > index THEN
            List(i - 1) = List(i)
        END IF
    NEXT
    REDIM PRESERVE List(0 TO listElements - 1)
END SUB

SUB pathRemoveCoordsFromList(list() AS pathListElement, r AS INTEGER, c AS INTEGER)
    DIM i, index
    DIM listElements
    listElements = UBOUND(list)
    FOR i = 1 TO listElements
        IF r = list(i).r AND c = list(i).c THEN
            index = i
            
            EXIT FOR
        END IF
    NEXT
    IF index = 0 THEN EXIT SUB
    pathRemoveFromList list(), index
END SUB


SUB pathAddToList(list() AS pathListElement, r AS INTEGER, c AS INTEGER)
    
    DIM listElements
    
    listElements = UBOUND(list) + 1
    REDIM PRESERVE List(0 TO listElements)
    List(ListElements).c = c
    List(ListElements).r = r
    
    
END SUB

SUB pathSortByCost(list() AS pathListElement, cost() AS INTEGER)
    DIM i
    DIM j
    DIM top = UBOUND(list) - 1
    FOR i = 1 TO top
        FOR j = 1 TO top
            IF cost(list(i).r, list(i).c) < cost(list(j).r, list(j).c)  THEN
                SWAP list(i), list(j)
            END IF
        NEXT
    NEXT
END SUB

FUNCTION pathIsInList(list() AS pathListElement, r, c)
    DIM i
    DIM top = UBOUND(list) - 1
    FOR i = 1 TO top
        IF list(i).r = r AND list(i).c = c THEN
            pathIsInList = i
            EXIT FOR
        END IF
    NEXT
END FUNCTION

--j_k