Hi,
i've got a little problem with this A* pathfinding library ( http://www.next-dimension.org/downloads/download.php?download=a_star.rar ). I want to write a "not connected list" for this code. (like in 3D-pathfinding the connected list). But this code is very compact, and i tryed for days now, but i'm not able to write this not connected list.
Has anyone maybe an idea how i could get this thing working or hay maybe someone written already such an not connected list?
thank you for your answers
(and excuse my bad english ;)
ps: i asked the author of this code already, but he told me, that he doesn't code anymore with this code, and i shall ask here
or here the code:
i've got a little problem with this A* pathfinding library ( http://www.next-dimension.org/downloads/download.php?download=a_star.rar ). I want to write a "not connected list" for this code. (like in 3D-pathfinding the connected list). But this code is very compact, and i tryed for days now, but i'm not able to write this not connected list.
Has anyone maybe an idea how i could get this thing working or hay maybe someone written already such an not connected list?
thank you for your answers
(and excuse my bad english ;)
ps: i asked the author of this code already, but he told me, that he doesn't code anymore with this code, and i shall ask here
or here the code:
Type ai_unit Field ID, xLoc#, yLoc#, speed#, sprite Field pathAI, pathStatus, pathLength, pathLocation, pathBank, xPath, yPath Field targetX, targetY, target.ai_unit End Type ;DECLARE VARIABLES ;Adjust these variables to match your map dimensions (see "setup" above) Global tileSize = 50, mapWidth = 16, mapHeight = 12 ;Create needed arrays Dim walkability(mapWidth+1,mapHeight+1) ;array that holds wall/obstacle information Dim openList(mapWidth*mapHeight+2) ;1 dimensional array holding ID# of open list items Dim whichList(mapWidth+1,mapHeight+1) ;2 dimensional array used to record ;whether a cell is on the open list or on the closed list. Dim openX(mapWidth*mapHeight+2) ;1d array stores the x location of an item on the open list Dim openY(mapWidth*mapHeight+2) ;1d array stores the y location of an item on the open list Dim parentX(mapWidth+1,mapHeight+1) ;2d array to store parent of each cell (x) Dim parentY(mapWidth+1,mapHeight+1) ;2d array to store parent of each cell (y) Dim Fcost(mapWidth*mapHeight+2) ;1d array to store F cost of a cell on the open list Dim Gcost(mapWidth+1,mapHeight+1) ;2d array to store G cost for each cell. Dim Hcost(mapWidth*mapHeight+2) ;1d array to store H cost of a cell on the open list ;Declare constants Global onClosedList = 10 ;openList variable Const notfinished = 0, notStarted = 0, found = 1, nonexistent = 2; pathStatus constants Const walkable = 0, unwalkable = 1; walkability array constants ;========================================================== ;FIND PATH: This function finds the path and saves it. Non-Blitz users please note, ;the first parameter is a pointer to a user-defined object called a ai_unit, which contains all ;relevant info about the ai_unit in question (its current location, speed, etc.). As an ;object-oriented data structure, types are similar to structs in C. ; Please note that targetX and targetY are pixel-based coordinates relative to the ;upper left corner of the map, which is 0,0. Function FindPath(ai_unit.ai_unit,targetX,targetY) ;1. Convert location data (in pixels) to coordinates in the walkability array. startX = Floor(ai_unit\xLoc/tileSize) : startY = Floor(ai_unit\yLoc/tileSize) targetX = Floor(targetX/tileSize) : targetY = Floor(targetY/tileSize) ;2. Quick Path Checks: Under the some circumstances no path needs to ;be generated ... ;If starting location and target are in the same location... If startX = targetX And startY = targetY And ai_unit\pathLocation > 0 Then Return found If startX = targetX And startY = targetY And ai_unit\pathLocation = 0 Then Return nonexistent ;If target square is unwalkable, return that it's a nonexistent path. If walkability(targetX,targetY) = unwalkable Then Goto noPath ;3. Reset some variables that need to be cleared If onClosedList > 1000000 ;occasionally redim whichList Dim whichList(mapWidth,mapHeight) : onClosedList = 10 End If onClosedList = onClosedList+2 ;changing the values of onOpenList and onClosed list is faster than redimming whichList() array onOpenList = onClosedList-1 ai_unit\pathLength = notstarted ;i.e, = 0 ai_unit\pathLocation = notstarted ;i.e, = 0 Gcost(startX,startY) = 0 ;reset starting square's G value to 0 ;4. Add the starting location to the open list of squares to be checked. numberOfOpenListItems = 1 openList(1) = 1 ;assign it as the top (and currently only) item in the open list, which is maintained as a binary heap (explained below) openX(1) = startX : openY(1) = startY ;5. Do the following until a path is found or deemed nonexistent. Repeat ;6. If the open list is not empty, take the first cell off of the list. ;This is the lowest F cost cell on the open list. If numberOfOpenListItems <> 0 Then ;Pop the first item off the open list. parentXval = openX(openList(1)) : parentYVal = openY(openList(1)) ;record cell coordinates of the item whichList(parentXval,parentYVal) = onClosedList ;add the item to the closed list ;Open List = Binary Heap: Delete this item from the open list, which ;is maintained as a binary heap. For more information on binary heaps, see: ;http://www.policyalmanac.org/games/binaryHeaps.htm numberOfOpenListItems = numberOfOpenListItems - 1 ;reduce number of open list items by 1 openList(1) = openList(numberOfOpenListItems+1) ;move the last item in the heap up to slot #1 v = 1 Repeat ;Repeat the following until the new item in slot #1 sinks to its proper spot in the heap. u = v If 2*u+1 <= numberOfOpenListItems ;if both children exist ;Check if the F cost of the parent is greater than each child. ;Select the lowest of the two children. If Fcost(openList(u)) >= Fcost(openList(2*u)) Then v = 2*u If Fcost(openList(v)) >= Fcost(openList(2*u+1)) Then v = 2*u+1 Else If 2*u <= numberOfOpenListItems ;if only child #1 exists ;Check if the F cost of the parent is greater than child #1 If Fcost(openList(u)) >= Fcost(openList(2*u)) Then v = 2*u End If End If If u<>v ;if parent's F is > one of its children, swap them temp = openList(u) openList(u) = openList(v) openList(v) = temp Else Exit ;otherwise, exit loop End If Forever ;7. Check the adjacent squares. (Its "children" -- these path children ;are similar, conceptually, to the binary heap children mentioned ;above, but don't confuse them. They are different. Path children ;are portrayed in Demo 1 with grey pointers pointing toward ;their parents.) Add these adjacent child squares to the open list ;for later consideration if appropriate (see various if statements ;below). For b = parentYVal-1 To parentYVal+1 For a = parentXval-1 To parentXval+1 ;If not off the map (do this first to avoid array out-of-bounds errors) If a <> -1 And b <> -1 And a <> mapWidth And b <> mapHeight ;If not already on the closed list (items on the closed list have ;already been considered and can now be ignored). If whichList(a,b) <> onClosedList ;If not a wall/obstacle square. If walkability(a,b) <> unwalkable ;Don't cut across corners (this is optional) corner = walkable If a = parentXVal-1 If b = parentYVal-1 If walkability(parentXval-1,parentYval) = unwalkable Or walkability(parentXval,parentYval-1) = unwalkable Then corner = unwalkable Else If b = parentYVal+1 If walkability(parentXval,parentYval+1) = unwalkable Or walkability(parentXval-1,parentYval) = unwalkable Then corner = unwalkable End If Else If a = parentXVal+1 If b = parentYVal-1 If walkability(parentXval,parentYval-1) = unwalkable Or walkability(parentXval+1,parentYval) = unwalkable Then corner = unwalkable Else If b = parentYVal+1 If walkability(parentXval+1,parentYval) = unwalkable Or walkability(parentXval,parentYval+1) = unwalkable Then corner = unwalkable End If End If If corner = walkable ;If not already on the open list, add it to the open list. If whichList(a,b) <> onOpenList ;Create a new open list item in the binary heap. newOpenListItemID = newOpenListItemID + 1; each new item has a unique ID # m = numberOfOpenListItems+1 openList(m) = newOpenListItemID ;place the new open list item (actually, its ID#) at the bottom of the heap openX(newOpenListItemID) = a : openY(newOpenListItemID) = b ;record the x and y coordinates of the new item ;Figure out its G cost If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 ;cost of going to diagonal squares Else addedGCost = 10 ;cost of going to non-diagonal squares End If Gcost(a,b) = Gcost(parentXval,parentYVal)+addedGCost ;Figure out its H and F costs and parent Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) ; record the H cost of the new square Fcost(openList(m)) = Gcost(a,b) + Hcost(openList(m)) ;record the F cost of the new square parentX(a,b) = parentXval : parentY(a,b) = parentYVal ;record the parent of the new square ;Move the new open list item to the proper place in the binary heap. ;Starting at the bottom, successively compare to parent items, ;swapping as needed until the item finds its place in the heap ;or bubbles all the way to the top (if it has the lowest F cost). While m <> 1 ;While item hasn't bubbled to the top (m=1) ;Check if child's F cost is < parent's F cost. If so, swap them. If Fcost(openList(m)) <= Fcost(openList(m/2)) Then temp = openList(m/2) openList(m/2) = openList(m) openList(m) = temp m = m/2 Else Exit End If Wend numberOfOpenListItems = numberOfOpenListItems+1 ;add one to the number of items in the heap ;Change whichList to show that the new item is on the open list. whichList(a,b) = onOpenList ;8. If adjacent cell is already on the open list, check to see if this ;path to that cell from the starting location is a better one. ;If so, change the parent of the cell and its G and F costs. Else; If whichList(a,b) = onOpenList ;Figure out the G cost of this possible new path If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14;cost of going to diagonal tiles Else addedGCost = 10 ;cost of going to non-diagonal tiles End If tempGcost = Gcost(parentXval,parentYVal)+addedGCost ;If this path is shorter (G cost is lower) then change ;the parent cell, G cost and F cost. If tempGcost < Gcost(a,b) Then ;if G cost is less, parentX(a,b) = parentXval ;change the square's parent parentY(a,b) = parentYVal Gcost(a,b) = tempGcost ;change the G cost ;Because changing the G cost also changes the F cost, if ;the item is on the open list we need to change the item's ;recorded F cost and its position on the open list to make ;sure that we maintain a properly ordered open list. For x = 1 To numberOfOpenListItems ;look for the item in the heap If openX(openList(x)) = a And openY(openList(x)) = b Then ;item found FCost(openList(x)) = Gcost(a,b) + HCost(openList(x)) ;change the F cost ;See if changing the F score bubbles the item up from it's current location in the heap m = x While m <> 1 ;While item hasn't bubbled to the top (m=1) ;Check if child is < parent. If so, swap them. If Fcost(openList(m)) < Fcost(openList(m/2)) Then temp = openList(m/2) openList(m/2) = openList(m) openList(m) = temp m = m/2 Else Exit ;while/wend End If Wend Exit ;for x = loop End If ;If openX(openList(x)) = a Next ;For x = 1 To numberOfOpenListItems End If ;If tempGcost < Gcost(a,b) Then End If ;If not already on the open list End If ;If corner = walkable End If ;If not a wall/obstacle cell. End If ;If not already on the closed list End If ;If not off the map. Next Next ;9. If open list is empty then there is no path. Else path = nonExistent : Exit End If ;If target is added to open list then path has been found. If whichList(targetx,targety) = onOpenList Then path = found : Exit Forever ;repeat until path is found or deemed nonexistent ;10. Save the path if it exists. Copy it to a bank. If path = found ;a. Working backwards from the target to the starting location by checking ;each cell's parent, figure out the length of the path. pathX = targetX : pathY = targetY Repeat tempx = parentX(pathX,pathY) pathY = parentY(pathX,pathY) pathX = tempx ai_unit\pathLength = ai_unit\pathLength + 1 Until pathX = startX And pathY = startY ;b. Resize the data bank to the right size (leave room to store step 0, ;which requires storing one more step than the length) ResizeBank ai_unit\pathBank,(ai_unit\pathLength+1)*4 ;c. Now copy the path information over to the databank. Since we are ;working backwards from the target to the start location, we copy ;the information to the data bank in reverse order. The result is ;a properly ordered set of path data, from the first step to the ;last. pathX = targetX : pathY = targetY cellPosition = ai_unit\pathLength*4 ;start at the end While Not (pathX = startX And pathY = startY) PokeShort ai_unit\pathBank,cellPosition,pathX ;store x value debuglog pathx PokeShort ai_unit\pathBank,cellPosition+2,pathY ;store y value debuglog pathy cellPosition = cellPosition - 4 ;work backwards tempx = parentX(pathX,pathY) pathY = parentY(pathX,pathY) pathX = tempx Wend PokeShort ai_unit\pathBank,0,startX ;store starting x value PokeShort ai_unit\pathBank,2,startY ;store starting y value End If ;If path = found Then ;11. Return info on whether a path has been found. Return path; Returns 1 if a path has been found, 2 if no path exists. ;12.If there is no path to the selected target, set the pathfinder's ;xPath and yPath equal to its current location and return that the ;path is nonexistent. .noPath ai_unit\xPath = startingX ai_unit\yPath = startingY Return nonexistent End Function ;========================================================== ;READ PATH DATA: These functions read the path data and convert ;it to screen pixel coordinates. Function ReadPath(ai_unit.ai_unit) ai_unit\xPath = ReadPathX(ai_unit.ai_unit,ai_unit\pathLocation) ai_unit\yPath = ReadPathY(ai_unit.ai_unit,ai_unit\pathLocation) End Function Function ReadPathX#(ai_unit.ai_unit,pathLocation) If pathLocation <= ai_unit\pathLength x = PeekShort (ai_unit\pathBank,pathLocation*4) Return tileSize*x + .5*tileSize ;align w/center of square End If End Function Function ReadPathY#(ai_unit.ai_unit,pathLocation) If pathLocation <= ai_unit\pathLength y = PeekShort (ai_unit\pathBank,pathLocation*4+2) Return tileSize*y + .5*tileSize ;align w/center of square End If End Function ;This function checks whether the ai_unit is close enough to the next ;path node to advance to the next one or, if it is the last path step, ;to stop. Function CheckPathStepAdvance(ai_unit.ai_unit) If (ai_unit\xLoc = ai_unit\xPath And ai_unit\yLoc = ai_unit\yPath) Or ai_unit\pathLocation = 0 If ai_unit\pathLocation = ai_unit\pathLength ai_unit\pathStatus = notstarted Else ai_unit\pathLocation = ai_unit\pathLocation + 1 ReadPath(ai_unit) ;update xPath and yPath End If End If End Function