A* Pathfinding. - Printable Version +- Qbasicnews.com (http://qbasicnews.com/newforum) +-- Forum: Qbasic "like" compilers/interpreters (http://qbasicnews.com/newforum/forum-5.html) +--- Forum: FB Discussion & Programming Help (http://qbasicnews.com/newforum/forum-15.html) +--- Thread: A* Pathfinding. (/thread-7591.html) Pages:
1
2
|
A* Pathfinding. - pr0gger - 06-23-2005 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. 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] A* Pathfinding. - DrV - 06-23-2005 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. A* Pathfinding. - pr0gger - 06-24-2005 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 A* Pathfinding. - dumbledore - 06-24-2005 dunno if this is a bug too but Quote:pathREMoveFromList = MID$(List$, 1, i - 1) + MID$(List$, i + 8)gets turned into a smiley... A* Pathfinding. - pr0gger - 06-24-2005 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 A* Pathfinding. - Agamemnus - 06-24-2005 :| 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. A* Pathfinding. - pr0gger - 06-24-2005 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 A* Pathfinding. - Anonymous - 06-24-2005 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 A* Pathfinding. - pr0gger - 06-26-2005 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 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 A* Pathfinding. - dumbledore - 06-26-2005 try compiling with the -ex flag? dunno... unfortunately error checking atm doesn't support array-out-of-bounds... |