A* Pathfinding.

[pr0gger]

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:

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$) / 8leep

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]