A* Pathfinding.

[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. :/

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)

    DIM OpenList(1 TO 1) AS PathListElement
    DIM ClosedList(1 TO 1) 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
    DIM LowestFR AS INTEGER, LowestFC AS INTEGER, i AS INTEGER

    CurrentR = StartR
    CurrentC = StartC
    'PRINT OpenList(1).r; OpenList(1).C
    pathAddToList OpenList(), CurrentR , CurrentC           'Add starting square to open list
    'PRINT OpenList(1).r; OpenList(1).C
    
    DO UNTIL UBOUND(OpenList) = 1 OR pathIsInList(OpenList(), EndR, EndC)
PRINT "Top"': Sleep                  
        pathRemoveCoordsFromList(OpenList(), CurrentR, CurrentC)  'Drop current node from open list        
        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
                                    
        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 NOT pathIsInList(ClosedList(), r, c) THEN   'Make sure we can go there, and that we're not on the closed list
                    IF NOT pathIsInList(OpenList(), r, c) 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))
                        f(r, c) = g(r, c) + h(r, c)
                        
                    ELSE
                                            
                    END IF
                END IF
            NEXT
        NEXT
PRINT "Before"
        pathSortByCost OpenList(), f()

PRINT "After";
PRINT pathIsInList(OpenList(), EndR, EndC)': Sleep                
      
        CurrentR = OpenList(1).r
        CurrentC = OpenList(1).c
        
        pathDrawMap(startR, StartC, EndR, EndC, OpenList(), ClosedList())
        LOCATE CurrentR, CurrentC: PRINT "X"
    LOOP

  
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)
    FOR i = 1 TO listElements
        IF i > index THEN
            List(i - 1) = List(i)
        END IF
    NEXT
    REDIM PRESERVE List(0 TO listElements - 1)
    ListElements = 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)
    List(ListElements).c = c
    List(ListElements).r = r
    'PRINT listElements; List(1).r; List(1).c: sleep
    
    REDIM PRESERVE List(0 TO listElements + 1)
    
    
END SUB

SUB pathSortByCost(list() AS pathListElement, cost() AS INTEGER)
    DIM i
    DIM j
    DIM top = UBOUND(list) - 1
    PRINT "Checkpoint 1"; top
    FOR i = 1 TO top
        FOR j = 1 TO top
            PRINT "Checkpoint 2: "; list(i).r; list(i).c
                IF cost(list(i).r, list(i).c) > cost(list(j).r, list(j).c)  THEN
                    PRINT "Checkpoint 3: "; i; j; top
                    SWAP list(i), list(j)
                END IF
        NEXT
    NEXT
    PRINT "Checkpoint 4" ':SLEEP
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

See all the "checkpoints" in pathSortByCost() ? That was me, trying to errorcheck.

Here's a screenshot:



The problem is highlighted in red: Those numbers are supposed to tell what dimensions the program should look at in an array, so obviously that generates an error. Where are they coming from!? Some memory-mistake?

The strange thing is that sometimes those numbers are different (leading me to believe that the problem is with the OS, not with the compiler).

*mutters*

--j_k