A* Pathfinding. - pr0gger - 06-26-2005
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
A* Pathfinding. - Agamemnus - 06-26-2005
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...
A* Pathfinding. - pr0gger - 06-27-2005
Now, there's the root of my problem-- there's pretty much nothing I can do to fix this. :-?
--j_k
A* Pathfinding. - Sisophon2001 - 06-27-2005
Quote: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
A* Pathfinding. - Agamemnus - 06-27-2005
With that fix it does not seem to actually work anyway.. I set up a barrier and it seemed to ignore it..
A* Pathfinding. - Torahteen - 06-28-2005
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.
A* Pathfinding. - Torahteen - 07-03-2005
Hey, have you made any progress? If so, join us at the "My Try At A*" post in the FB projects forum.
A* Pathfinding. - pr0gger - 07-06-2005
Quote:pr0gger Wrote: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
A* Pathfinding. - pr0gger - 07-06-2005
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
|