07-06-2005, 05:16 AM
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).
--j_k
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
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]