Huhu zusammen!
Ich habe nach wie vor große schwierigkeiten mit dem Pathfinding, jedoch habe ich was gefunden, was für jeden interessant sein könnte, und allen das Leben etwas einfacher macht
Die Lib hier bringt alles mit und ist gut Dokumentiert, jedoch NICHT von mir geschrieben.
Gefunden hier:
http://www.policyalmanac.org/g...torial.htm
Author:
Patrick Lester
Lib:
BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN]
.declareVariables
Global tileSize = 50, mapWidth = 16, mapHeight = 12
Dim walkability(mapWidth+1,mapHeight+1) Dim openList(mapWidth*mapHeight+2) Dim whichList(mapWidth+1,mapHeight+1) Dim openX(mapWidth*mapHeight+2) Dim openY(mapWidth*mapHeight+2) Dim parentX(mapWidth+1,mapHeight+1) Dim parentY(mapWidth+1,mapHeight+1) Dim Fcost(mapWidth*mapHeight+2) Dim Gcost(mapWidth+1,mapHeight+1) Dim Hcost(mapWidth*mapHeight+2) Global onClosedList = 10 Const notfinished = 0, notStarted = 0, found = 1, nonexistent = 2 Const walkable = 0, unwalkable = 1
Function FindPath(unit.unit,targetX,targetY)
startX = Floor(unit\xLoc/tileSize) : startY = Floor(unit\yLoc/tileSize) targetX = Floor(targetX/tileSize) : targetY = Floor(targetY/tileSize)
If startX = targetX And startY = targetY And unit\pathLocation > 0 Then Return found If startX = targetX And startY = targetY And unit\pathLocation = 0 Then Return nonexistent
If walkability(targetX,targetY) = unwalkable Then Goto noPath
If onClosedList > 1000000 Dim whichList(mapWidth,mapHeight) : onClosedList = 10 End If onClosedList = onClosedList+2 onOpenList = onClosedList-1 unit\pathLength = notstarted unit\pathLocation = notstarted Gcost(startX,startY) = 0
numberOfOpenListItems = 1 openList(1) = 1 openX(1) = startX : openY(1) = startY
Repeat
If numberOfOpenListItems <> 0 Then
parentXval = openX(openList(1)) : parentYVal = openY(openList(1)) whichList(parentXval,parentYVal) = onClosedList
numberOfOpenListItems = numberOfOpenListItems - 1 openList(1) = openList(numberOfOpenListItems+1) v = 1 Repeat u = v If 2*u+1 <= numberOfOpenListItems 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 Fcost(openList(u)) >= Fcost(openList(2*u)) Then v = 2*u End If End If If u<>v temp = openList(u) openList(u) = openList(v) openList(v) = temp Else Exit End If Forever
For b = parentYVal-1 To parentYVal+1 For a = parentXval-1 To parentXval+1
If a <> -1 And b <> -1 And a <> mapWidth And b <> mapHeight
If whichList(a,b) <> onClosedList If walkability(a,b) <> unwalkable 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 whichList(a,b) <> onOpenList
newOpenListItemID = newOpenListItemID + 1 m = numberOfOpenListItems+1 openList(m) = newOpenListItemID openX(newOpenListItemID) = a : openY(newOpenListItemID) = b
If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 Else addedGCost = 10 End If Gcost(a,b) = Gcost(parentXval,parentYVal)+addedGCost Hcost(openList(m)) = 10*(Abs(a - targetx) + Abs(b - targety)) Fcost(openList(m)) = Gcost(a,b) + Hcost(openList(m)) parentX(a,b) = parentXval : parentY(a,b) = parentYVal While m <> 1 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
whichList(a,b) = onOpenList
Else If Abs(a-parentXval) = 1 And Abs(b-parentYVal) = 1 Then addedGCost = 14 Else addedGCost = 10 End If tempGcost = Gcost(parentXval,parentYVal)+addedGCost If tempGcost < Gcost(a,b) Then parentX(a,b) = parentXval parentY(a,b) = parentYVal Gcost(a,b) = tempGcost
For x = 1 To numberOfOpenListItems If openX(openList(x)) = a And openY(openList(x)) = b Then FCost(openList(x)) = Gcost(a,b) + HCost(openList(x)) m = x While m <> 1 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 Exit End If Next
End If
End If End If End If End If End If Next Next
Else path = nonExistent : Exit End If
If whichList(targetx,targety) = onOpenList Then path = found : Exit
Forever
If path = found pathX = targetX : pathY = targetY Repeat tempx = parentX(pathX,pathY) pathY = parentY(pathX,pathY) pathX = tempx unit\pathLength = unit\pathLength + 1 Until pathX = startX And pathY = startY ResizeBank unit\pathBank,(unit\pathLength+1)*4
pathX = targetX : pathY = targetY cellPosition = unit\pathLength*4 While Not (pathX = startX And pathY = startY) PokeShort unit\pathBank,cellPosition,pathX PokeShort unit\pathBank,cellPosition+2,pathY cellPosition = cellPosition - 4 tempx = parentX(pathX,pathY) pathY = parentY(pathX,pathY) pathX = tempx Wend PokeShort unit\pathBank,0,startX PokeShort unit\pathBank,2,startY
End If
Return path
.noPath unit\xPath = startingX unit\yPath = startingY Return nonexistent
End Function
Function ReadPath(unit.unit) unit\xPath = ReadPathX(unit.unit,unit\pathLocation) unit\yPath = ReadPathY(unit.unit,unit\pathLocation) End Function
Function ReadPathX#(unit.unit,pathLocation) If pathLocation <= unit\pathLength x = PeekShort (unit\pathBank,pathLocation*4) Return tileSize*x + .5*tileSize End If End Function
Function ReadPathY#(unit.unit,pathLocation) If pathLocation <= unit\pathLength y = PeekShort (unit\pathBank,pathLocation*4+2) Return tileSize*y + .5*tileSize End If End Function
Function CheckPathStepAdvance(unit.unit) If (unit\xLoc = unit\xPath And unit\yLoc = unit\yPath) Or unit\pathLocation = 0 If unit\pathLocation = unit\pathLength unit\pathStatus = notstarted Else unit\pathLocation = unit\pathLocation + 1 ReadPath(unit) End If End If End Function
|