Thread Rating:
  • 0 Vote(s) - 0 Average
  • 1
  • 2
  • 3
  • 4
  • 5
A* Pathfinding.
#1
I'm trying to write an A* pathfinding algorithm for a game using this tutorial, but I've run into trouble when he gets to this point:

Quote:If an adjacent square is already on the open list, check to see if this path to that square is a better one. In other words, check to see if the G score for that square is lower if we use the current square to get there. If not, don’t do anything.
On the other hand, if the G cost of the new path is lower, change the parent of the adjacent square to the selected square (in the diagram above, change the direction of the pointer to point at the selected square). Finally, recalculate both the F and G scores of that square. If this seems confusing, you will see it illustrated below.

I don't quite get it. How am I supposed to do that?

Here's my code so far. I'm pretty sure I'm supposed to add the G-cost check down near line 99 (There's a '**** there). I'm using the qbasic syntax tag since there doesn't seem to be a freebasic one yet...

[syntax="qbasic"]DEFINT A-Z

DECLARE function pathFind$(StartR as integer, StartC as integer, EndR as integer, EndC as integer)
DECLARE function pathAddToList$(list$, r as integer, c as integer)
DECLARE FUNCTION pathRemoveFromList$(list$, index as integer)
DECLARE FUNCTION pathRemoveCoordsFromList$(list$, r as integer, c as integer)
DECLARE FUNCTION pathIsWalkable(r as integer, c as integer)
DECLARE FUNCTION pathIsInList(list$, r as integer, c as integer)
DECLARE SUB pathGetValue(list$, index, r as integer, c as integer)
DECLARE SUB DrawMap(startR, StartC, EndR, EndC, mapStatus() as integer)
SCREEN 0

DIM SHARED MapW, MapH
READ MapH, MapW
DIM SHARED Map(1 to MapW, 1 to MapH)

For r = 1 to MapH
for c = 1 to MapW
read map(r, c)
next
next


path$ = pathFind(4, 3, 4, 7)

SLEEP

END

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

function pathFind$(StartR as integer, StartC as integer, EndR as integer, EndC as integer)

LOCATE StartR, StartC: PRINT "S"

LOCATE EndR, EndC: PRINT "E"

DIM f(MapW, MapH) as integer
DIM g(MapW, MapH) as integer
DIM h(MapW, MapH) as integer
DIM MapStatus(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

DIM OpenList AS STRING
dim ClosedList AS STRING

DIM StatusClosed as integer
StatusClosed = -1
Dim StatusOpen as integer
StatusOpen = 1

CurrentR = StartR
CurrentC = StartC

OpenList = pathAddToList (OpenList, CurrentR, CurrentC)
MapStatus(r, c) = StatusOpen


DO UNTIL CurrentR = EndR and CurrentC = EndC

r1 = CurrentR - 1 : c1 = CurrentC - 1
r2 = CurrentR + 1 : c2 = CurrentC + 1

IF r1 < 1 then r1 = 1
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 not (c = currentC and r = currentR) and MapStatus(r, c) <> StatusClosed and pathIsWalkable(r, c) <> 0 then
'if pathIsInList(OpenList, r, c) = 0 then
OpenList = pathAddToList (OpenList, r, c)
MapStatus(r, c) = StatusOpen

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)


'LOCATE 10, 1: PRINT currentR; currentC
'LOCATE 11, 1: PRINT r; c
'LOCATE 12, 1: PRINT g(r, c); h(r, c); f(r, c)
'else

'end if
end if
next
next

OpenList = pathRemoveCoordsFromList(OpenList, CurrentR, CurrentC)

MapStatus(CurrentR, CurrentC) = 0

closedList = pathAddToList (ClosedList, CurrentR, CurrentC)
MapStatus(CurrentR, CurrentC) = StatusClosed

LowestF = 0


for i = 1 to len(OpenList) / 8
pathGetValue OpenList, i, r, c
if f(r, c) <= LowestF OR LowestF = 0 and not (r = currentR and c = currentC) then
LowestFR = r
LowestFC = c
LowestF = f(r, c)
Locate 18, 1: Print currentR; currentC, r1;c1, r2; c2
LOCATE 19, 1: PRINT r;c, f(r, c); g(r, c); h(r, c); LowestF

end if

next

CurrentR = LowestFR
CurrentC = LowestFC
DrawMap startR, StartC, EndR, EndC, MapStatus()
' Locate CurrentR, CurrentC: Print "X"
OpenList = pathRemoveCoordsFromList(OpenList, CurrentR, CurrentC)
MapStatus(CurrentR, CurrentC) = 0

ClosedList = pathAddToList(ClosedList, CurrentR, CurrentC)
MapStatus(CurrentR, CurrentC) = StatusClosed

LOOP

end function


function pathAddToList$(list$, r, c)
pathAddToList = list$ + MKI$® + MKI$©
end function

FUNCTION pathRemoveFromList$(list$, index)
i = (index * 8) - 7

if i = 1 then
pathRemoveFromList = MID$(list$, 9)
elseif i = len(list$) - 7 then
pathRemoveFromList = left$(list$, len(list$) - 7)
else
pathRemoveFromList = MID$(List$, 1, i - 1) + MID$(List$, i + 8 )
end if
end function

FUNCTION pathRemoveCoordsFromList$(list$, r, c)
dim index as integer, a$
index = pathIsInList (list$, r, c)

'LOCATE 10, 1: print r; c, len(list$) / 8

if index <> 0 then
pathRemoveCoordsFromList = pathRemoveFromList(list$, index)
locate 12, 1: print "index <> 0"
else
pathRemoveCoordsFromList = list$
locate 12, 1: print "index == 0"
end if

'LOCATE 11, 1: print len(list$) / 8Confusedleep

end function

FUNCTION pathIsInList(list$, r, c)
dim search$, index as integer, location as integer, done as integer

search$ = MKI$® + MKI$©
start = 1

do
location = inStr(start, list$, search$)

if location = 0 then exit do
if ((location - 1) / 8) = int((location - 1) / 8) then
index = ((location - 1) / 8) + 1
pathIsInList = Index
exit function
else
start = location + 4
if location >= len(list$) then
exit function
end if
end if
loop

end function

FUNCTION pathIsWalkable(r, c)
if map(r, c) = 1 then pathIsWalkable = -1
end function

SUB pathGetValue(list$, index, r, c)
i = (index * 8) - 7
r = CVI(Mid$(list$, i, 4))
i = i + 4
c = CVI(Mid$(list$, i, 4))
end SUB

sub DrawMap(startR, StartC, EndR, EndC, mapStatus())

DIM r as integer, c as integer, text$
DIM statusOpen, statusClosed

statusOpen = 1
statusClosed = -1

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"
elseif pathIsWalkable(r, c) = 0 then
text$ = chr$(219)
end if
if mapStatus (r, c)= StatusOpen then
color 10
elseif mapStatus (r, c)= StatusClosed then
color 11
end if
LOCATE R, C: PRINT text$

next
next

end sub[/syntax]
size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Reply
#2
Hmm, sorry, can't answer your question, but I did notice that there's a geshi bug: "pathREMoveFromList" - the part from REM onwards becomes highlighted as a comment.
Reply
#3
Yeah, I saw that. Just as a general note, folks, I never use REM for comments; if it's there, its part of a word.

--j_k
size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Reply
#4
dunno if this is a bug too but
Quote:pathREMoveFromList = MID$(List$, 1, i - 1) + MID$(List$, i + 8)
gets turned into a smiley...
ttp://m0n573r.afraid.org/
Quote:quote: "<+whtiger> you... you don't know which way the earth spins?" ... see... stupidity leads to reverence, reverence to shakiness, shakiness to... the dark side
...phear
Reply
#5
Hmmm.

Should be

Code:
pathREMoveFromList = MID$(List$, 1, i - 1) + MID$(List$, i + 8)

I'll see if I can change that by adding a space or something...

--j_k
size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Reply
#6
:|

Have you "mastered" the breadth first search yet that I used. :|

The code looks terrible. DATA, strings as integer arrays... not good. :|

Will look. Tomorrow. Maybe.
Peace cannot be obtained without war. Why? If there is already peace, it is unnecessary for war. If there is no peace, there is already war."

Visit www.neobasic.net to see rubbish in all its finest.
Reply
#7
I take it that this is a bad sign.

*throws a shoe* Hey, I've gotta start somewhere. You've gotta remember that most of my, ah, "methods" are holdovers from QB. For example, I used strings because when you REDIM in qb, you'd lose all your data. If there's a list data type in FB, it would solve half my problems.

--j_k
size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Reply
#8
sorry, im really not gonna take the time to try and understand a totaly new concept but, if you wanna redim an array without erasing it, try REDIM PRESERVE aray(indices) as whatever
Reply
#9
That's helpful Smile

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:

[Image: errorss0em.th.jpg]

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
size=9]"To announce that there must be no criticism of the president, or that we are to stand by the president, right or wrong, is not only unpatriotic and servile, but is morally treasonable to the American public." -- Theodore Roosevelt[/size]
Reply
#10
try compiling with the -ex flag? dunno... unfortunately error checking atm doesn't support array-out-of-bounds...
ttp://m0n573r.afraid.org/
Quote:quote: "<+whtiger> you... you don't know which way the earth spins?" ... see... stupidity leads to reverence, reverence to shakiness, shakiness to... the dark side
...phear
Reply


Forum Jump:


Users browsing this thread: 1 Guest(s)