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:
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
|
