A* (A-Star) Wegfindung optimieren

[Makke]

Hallo,

für diverse Testprojekte habe ich den A* Algo in PB umgesetzt (haben bestimmt schon viele). Um flexibel zu sein, wird zuerst die Map (was auch immer für eine) Initialisiert, das dauer je nach Auflösung der A* Knoten eine Zeitlang.

Danach kann man mit einer weiteren Procedur den Weg heraussuchen, der per ID abgespeichert wird (und später über Splines abgelaufen werden kann). Das Problem ist die A* Prozedur, ich habe dort alles was meiner Meinung nach verzichtbar ist (für eine simple Wegfindung) herausgelassen, alles wozu der Rechner länger braucht und was möglich ist, habe ich vorher berechnen lassen.

Trotzdem ist der je nach Auflösung (Beispiel: 1 A* Quadrat ist 8x8 Welteinheiten) sehr langsam. Ich suche Tips, wie ich den flotter bekomme. Zumeist wissen die Cracks schon wo man dieses oder jenes besser ist, ich hatte hier mal irgendwo gelesen, das For..Next schneller sein soll als While..Wend, deswegen habe ich das eingebaut usw. trotzdem ist der bei sehr kleinen Auflösungen langsam.

Hier mal der Code nur von der Procedure, solltet ihr den mal "in Aktion" sehen wollen, dann müsste ich ein Beispiel dazu schreiben, also bitte sagen:

Code: Alles auswählen

Procedure.l FindPath(PathfinderID.l, StartUnitX.l, StartUnitZ.l, TargetUnitX.l, TargetUnitZ.l)
  
  Shared      mapWidth, mapHeight, tileSizeD, tileSizeX, tileSizeZ
  Protected.b found = #False
  Protected.l pathfinderElement, startX, startZ, targetX, targetZ, parentX, parentZ, x, z, n, gCost, hCost, fCost, minCost, nextX,nextZ
  Protected.i startTime = ElapsedMilliseconds()
  
  If PathfinderID > 0
    ForEach Pathfinder()
      If Pathfinder()\id = PathfinderID
        pathfinderElement = ListIndex(Pathfinder())
        ClearList(Pathfinder()\waypoints())
        found = #True
        Break
      EndIf
    Next
  EndIf
  
  If Not found
    AddElement(Pathfinder())
    Pathfinder()\id   = ListIndex(Pathfinder()) + 1
    pathfinderElement = ListIndex(Pathfinder())
    PathfinderID      = Pathfinder()\id
  Else
    found = #False
  EndIf
  
  For x = 0 To mapWidth-1
    For z = 0 To mapHeight-1
      PathMap(x,z)\onClosedList = #False
      HideEntity(PathMap(x,z)\entityPath, #True)
    Next
  Next
  
  startX  = ConvertUnitToTileX(StartUnitX)
  startZ  = ConvertUnitToTileZ(StartUnitZ)
  targetX = ConvertUnitToTileX(TargetUnitX)
  targetZ = ConvertUnitToTileZ(TargetUnitZ)
  
  SelectElement(Pathfinder(), pathfinderElement)
  AddElement(Pathfinder()\waypoints())
  Pathfinder()\waypoints()\x = startX
  Pathfinder()\waypoints()\z = startZ
    
  If startX = targetX And startZ = targetZ
    ProcedureReturn PathfinderID;#Path_isStartPoint
  EndIf
  
  If PathMap(targetX,targetZ)\isBlocked
    ProcedureReturn PathfinderID;#Path_isBlocked
  EndIf
  
  parentX = startX
  parentZ = startZ
  
  HideEntity(PathMap(parentX,parentZ)\entityPath, #False)
  
  found = #False
  
  Repeat
    
    PathMap(parentX,parentZ)\onClosedList = #True
    
    n       = 0
    fCost   = 0
    minCost = mapWidth * mapHeight * tileSizeX * tileSizeZ
    
    ;Debug "Parent= x:"+Str(parentX)+", z:"+Str(parentZ)
    
    For z = -1 To 1
      For x = -1 To 1
        
        If PathMap(parentX+x,parentZ+z)\onClosedList = #False And PathMap(parentX+x,parentZ+z)\isBlocked = #False
          
          If x = 0 And z <> 0
            gCost = tileSizeZ
          ElseIf z = 0 And x <> 0
            gCost = tileSizeX
          Else
            gCost = tileSizeD
          EndIf
          
          hCost = Abs(targetX-(parentX+x)) * tileSizeX + Abs(targetZ-(parentZ+z)) * tileSizeZ
          
          fCost = gCost + hCost
          ;Debug "x:"+Str(parentX+x)+", z:"+Str(parentZ+z)+" = "+Str(fCost)
          
          If fCost < minCost
            minCost = fCost
            nextX   = parentX+x
            nextZ   = parentZ+z
          EndIf
          
          n + 1
          
        EndIf
        
      Next
    Next
    
    If n = 0
      SelectElement(Pathfinder(), pathfinderElement)
      ClearList(Pathfinder()\waypoints())
      AddElement(Pathfinder()\waypoints())
      Pathfinder()\waypoints()\x = startX
      Pathfinder()\waypoints()\z = startZ
      ProcedureReturn PathfinderID
    EndIf
    
    ;Debug "Cheapest= x:"+Str(nextX)+", z:"+Str(nextZ)
    
    SelectElement(Pathfinder(), pathfinderElement)
    AddElement(Pathfinder()\waypoints())
    Pathfinder()\waypoints()\x = nextX
    Pathfinder()\waypoints()\z = nextZ
    
    If nextX = targetX And nextZ = targetZ
      found = #True
      Debug "Path found in "+Str(ElapsedMilliseconds()-startTime)+" ms"
    Else
      parentX = nextX
      parentZ = nextZ
    EndIf
    
    HideEntity(PathMap(nextX,nextZ)\entityPath, #False)
    
  Until found = #True
  
  SelectElement(Pathfinder(), pathfinderElement)
  Pathfinder()\notFinished = #True
  
  ProcedureReturn PathfinderID
  
EndProcedure

Danke schonmal für die weiteren Tips.

[CSHW89]

Es wäre, denk ich, gut, wenn du ein lauffähigen Code reinstellen könntest. Dann könnte man auch was ausprobieren. Statt For/Next, ne While-Schleife nehmen, halte ich für nicht vielversprechend. Das spielt sich, wenn überhaupt, im Milli/Nano-Bereich ab. Ich denke, da ist eher was grundlegendes falsch. Z.b. dass du Wege doppelt versuchst, oder sowas. Könnt ich mir zumindest vorstellen.

lg Kevin

edit: hab den Code nochmal überflogen. Da fallen mir direkt einige Punkte auf. Das absolute Nadelöhr wird aber SelectElement sein. Das ist ne absolute Totmann-Procedure für Performance. Einige kleine Dinge würde ich auch noch anders machen, sollten aber nicht so sehr ins Gewicht fallen.
Aber noch zum Algo selbst. Um ehrlich zu sein, sehe ich da nicht so viel vom A*-Algo. Vorallem scheint die OpenList komplett zu fehlen. Und die ist nun mal essenziell für A*. Du solltest dir also nochmal den Algorithmus genau anschauen (z.B. hier http://de.wikipedia.org/wiki/A*-Algorithmus).

edit2: und wenn du Zeit misst, niemals (!!!) mt Debugger. Immer ausschalten, und mit MessageRequester ausgeben.

[Makke]

Hallo,

hier ein Testcode um den A* in Aktion zu sehen:

Code: Alles auswählen

EnableExplicit

#Sprite_Cursor = 0

#Player_Speed = 4

#Mask_None   = 0
#Mask_Ground = 1<<1

#Path_isStartPoint = -1
#Path_isBlocked    = -2
#Path_notAvailable = -3

Structure Vec3
  x.f
  y.f
  z.f
EndStructure

Structure structPlayer
  init.b
  id.l
  Rotate.Vec3
  Move.Vec3
  Target.Vec3
  zoom.l
  splineTarget.i
  entity.i
  entityTarget.i
  camera.i
  nodeMain.i
  nodeCamera.i
  nodeForward.i
EndStructure

Structure structLevel
  entFloor.i
  entCeil.i
  entWallLe.i
  entWallRi.i
  entWallFr.i
  entWallBa.i
  entBlock01.i
  entBlock02.i
  entBlock03.i
  entBlock04.i
  entBlock05.i
  entBlock06.i
  entBlock07.i
  entBlock08.i
  entBlock09.i
  entBlock10.i
EndStructure

Structure structBlockedArea
  startX.f
  startZ.f
  endX.f
  endZ.f
EndStructure

Structure structPathfinderPoint
  x.l
  z.l
EndStructure

Structure structPathfinderMap
  id.l
  startX.f
  midX.f
  endX.f
  startZ.f
  midZ.f
  endZ.f
  isBlocked.b
  onClosedList.b
  entity.i
  entityPath.i
EndStructure

Structure structPathfinder
  id.l
  notFinished.b
  List waypoints.structPathfinderPoint()
EndStructure

Define.b            DoLoop = #True
Define.l            TimeSinceLastFrame, MouseX, MouseY
Define.structPlayer Player
Define.structLevel  Level

Define.l            mapWidth, mapHeight, tileSizeX, tileSizeZ, tileSizeD
Define.f            mapTopX, mapTopZ, mapBottomX, mapBottomZ
Global NewList      Pathfinder.structPathfinder()
Global Dim          PathMap.structPathfinderMap(1,1)

Declare Level_Create()
Declare Player_Create()
Declare Player_Update()

; init
InitEngine3D(#PB_Engine3D_DebugLog)
InitSprite()
InitKeyboard()
InitMouse()

OpenWindow(0,0,0,1024,768,"A* Pathfinding",#PB_Window_SystemMenu|#PB_Window_ScreenCentered)
OpenWindowedScreen(WindowID(0), 0, 0, WindowWidth(0), WindowHeight(0), 0, 0, 0, #PB_Screen_WaitSynchronization)

LoadFont(0, "Wingdings", 20, #PB_Font_HighQuality)
CreateSprite(#Sprite_Cursor, 32, 32)
StartDrawing(SpriteOutput(#Sprite_Cursor))
DrawingMode(#PB_2DDrawing_Transparent)
DrawingFont(FontID(0))
DrawText(0, 0, Chr(235), RGB(0, 255, 0))
StopDrawing()

Level_Create()
Player_Create()

MouseLocate(ScreenWidth()/2, ScreenHeight()/2)
Repeat
 
  While WindowEvent() : Wend
  
  DoLoop = Player_Update()
  
  TimeSinceLastFrame = RenderWorld()
  DisplayTransparentSprite(#Sprite_Cursor, MouseX, MouseY)
  FlipBuffers()
 
Until DoLoop = #False

End

Macro IsBetween(x, a, b)
  (((a) <= (x) And (x) <= (b)) Or ((b) <= (x) And (x) <= (a)))
EndMacro

Procedure.l ConvertUnitToTileX(Unit.f, Initialize.b=#False, Width.f=0)
  Shared      mapTopX, mapBottomX, tileSizeX
  Static.f    absolute
  Protected.l result
  If Initialize
    mapTopX    = Unit
    mapBottomX = Width
    If mapTopX < 0
      absolute = Abs(mapTopX)
    Else
      absolute = 0
    EndIf
  Else
    If Unit < mapTopX Or Unit > mapBottomX
      result = -1
    Else
      result = Int((Unit + absolute) / tileSizeX)
    EndIf
  EndIf
  ProcedureReturn result
EndProcedure

Procedure.l ConvertUnitToTileZ(Unit.f, Initialize.b=#False, Height.f=0)
  Shared      mapTopZ, mapBottomZ, tileSizeZ
  Static.f    absolute
  Protected.l result
  If Initialize
    mapTopZ    = Unit
    mapBottomZ = Height
    If mapTopZ < 0
      absolute = Abs(mapTopZ)
    Else
      absolute = 0
    EndIf
  Else
    If Unit < mapTopZ Or Unit > mapBottomZ
      result = -1
    Else
      result = Int((Unit + absolute) / tileSizeZ)
    EndIf
  EndIf
  ProcedureReturn result
EndProcedure

Procedure InitPathfinding(NumberOfUnits.l, TopLeftPointXInWorldUnits.f, TopLeftPointZInWorldUnits.f, MapWidthInWorldUnits.f, MapHeightInWorldUnits.f, TileSizeXInWorldUnits.l, TileSizeZInWorldUnits.l, List UnwalkableAreas.structBlockedArea())
  
  Shared      PathMap()
  Shared      mapWidth, mapHeight, tileSizeX, tileSizeZ, tileSizeD, mapTopX, mapTopZ
  Protected.l x, z, n, thisX, thisZ, lastX, lastZ
  Protected.i tempTexture1, tempTexture2, tempTexture3, tempMaterial1, tempMaterial2, tempMaterial3, tempMesh
  
  NewList blockedTiles.structPathfinderPoint()
  
  mapWidth  = Round(MapWidthInWorldUnits / TileSizeXInWorldUnits, #PB_Round_Up)
  mapHeight = Round(MapHeightInWorldUnits / TileSizeZInWorldUnits, #PB_Round_Up)
  tileSizeX = TileSizeXInWorldUnits
  tileSizeZ = TileSizeZInWorldUnits
  tileSizeD = Round(Sqr(tileSizeX * tileSizeX + tileSizeZ * tileSizeZ), #PB_Round_Nearest)
  ConvertUnitToTileX(TopLeftPointXInWorldUnits, #True, MapWidthInWorldUnits)
  ConvertUnitToTileZ(TopLeftPointZInWorldUnits, #True, MapHeightInWorldUnits)
  
  CompilerIf Defined(PathMap, #PB_Array)
    FreeArray(PathMap())
  CompilerEndIf
  Global Dim PathMap(mapWidth+1, mapHeight+1)
  
  tempTexture1 = CreateTexture(#PB_Any, 32, 32)
  StartDrawing(TextureOutput(tempTexture1))
  DrawingMode(#PB_2DDrawing_AlphaBlend)
  Line(0, 0, 1, TextureHeight(tempTexture1), RGBA(225, 225, 225, 255))
  Line(0, 0, TextureWidth(tempTexture1), 1, RGBA(225, 225, 225, 255))
  Line(0, TextureHeight(tempTexture1), TextureWidth(tempTexture1), 1, RGBA(225, 225, 225, 255))
  Line(TextureWidth(tempTexture1), 0, 1, TextureHeight(tempTexture1), RGBA(225, 225, 225, 255))
  Box(0, 0, TextureWidth(tempTexture1), TextureHeight(tempTexture1), RGBA(255, 0, 0, 64))
  StopDrawing()
  tempMaterial1 = CreateMaterial(#PB_Any, TextureID(tempTexture1))
  MaterialBlendingMode(tempMaterial1, #PB_Material_AlphaBlend)
  tempTexture2 = CreateTexture(#PB_Any, 32, 32)
  StartDrawing(TextureOutput(tempTexture2))
  DrawingMode(#PB_2DDrawing_AlphaBlend)
  Line(0, 0, 1, TextureHeight(tempTexture2), RGBA(225, 225, 225, 255))
  Line(0, 0, TextureWidth(tempTexture2), 1, RGBA(225, 225, 225, 255))
  Line(0, TextureHeight(tempTexture2), TextureWidth(tempTexture2), 1, RGBA(225, 225, 225, 255))
  Line(TextureWidth(tempTexture2), 0, 1, TextureHeight(tempTexture2), RGBA(225, 225, 225, 255))
  Box(0, 0, TextureWidth(tempTexture2), TextureHeight(tempTexture2), RGBA(0, 0, 255, 64))
  StopDrawing()
  tempMaterial2 = CreateMaterial(#PB_Any, TextureID(tempTexture2))
  MaterialBlendingMode(tempMaterial2, #PB_Material_AlphaBlend)
  tempTexture3 = CreateTexture(#PB_Any, 32, 32)
  StartDrawing(TextureOutput(tempTexture3))
  DrawingMode(#PB_2DDrawing_AlphaBlend)
  Line(0, 0, 1, TextureHeight(tempTexture3), RGBA(225, 225, 225, 255))
  Line(0, 0, TextureWidth(tempTexture3), 1, RGBA(225, 225, 225, 255))
  Line(0, TextureHeight(tempTexture3), TextureWidth(tempTexture3), 1, RGBA(225, 225, 225, 255))
  Line(TextureWidth(tempTexture3), 0, 1, TextureHeight(tempTexture3), RGBA(225, 225, 225, 255))
  Box(0, 0, TextureWidth(tempTexture3), TextureHeight(tempTexture3), RGBA(0, 255, 0, 64))
  StopDrawing()
  tempMaterial3 = CreateMaterial(#PB_Any, TextureID(tempTexture3))
  MaterialBlendingMode(tempMaterial3, #PB_Material_AlphaBlend)
  tempMesh = CreatePlane(#PB_Any, tileSizeX, tileSizeZ, 1, 1, 1, 1)
  
  ForEach UnwalkableAreas()
    For z = UnwalkableAreas()\startZ To UnwalkableAreas()\endZ
      For x = UnwalkableAreas()\startX To UnwalkableAreas()\endX
        thisX = ConvertUnitToTileX(x)
        thisZ = ConvertUnitToTileZ(z)
        If thisX <> lastX Or thisZ <> lastZ
          AddElement(blockedTiles())
          blockedTiles()\x = thisX
          blockedTiles()\z = thisZ
          lastX = thisX
          lastZ = thisZ
        EndIf
      Next
    Next
  Next
  
  For z = 0 To mapHeight-1
    For x = 0 To mapWidth-1
      n + 1
      PathMap(x,z)\id           = n
      PathMap(x,z)\startX       = TopLeftPointXInWorldUnits + x * tileSizeX
      PathMap(x,z)\endX         = TopLeftPointXInWorldUnits + x * tileSizeX + tileSizeX
      PathMap(x,z)\midX         = PathMap(x,z)\startX + tileSizeX / 2
      PathMap(x,z)\startZ       = TopLeftPointZInWorldUnits + z * tileSizeZ
      PathMap(x,z)\endZ         = TopLeftPointZInWorldUnits + z * tileSizez + tileSizeZ
      PathMap(x,z)\midZ         = PathMap(x,z)\startZ + tileSizeZ / 2
      PathMap(x,z)\isBlocked    = #False
      PathMap(x,z)\onClosedList = #False
      PathMap(x,z)\entity       = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial2), 0, 0, 0, #Mask_None)
      PathMap(x,z)\entityPath   = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial3), 0, 0, 0, #Mask_None)
      HideEntity(PathMap(x,z)\entityPath, #True)
      ForEach blockedTiles()
        If blockedTiles()\x = x And blockedTiles()\z = z
          PathMap(x,z)\isBlocked = #True
          FreeEntity(PathMap(x,z)\entity)
          PathMap(x,z)\entity = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial1), 0, 0, 0, #Mask_None)
          DeleteElement(blockedTiles())
          Break
        EndIf
      Next
      MoveEntity(PathMap(x,z)\entity, PathMap(x,z)\midX, 10, PathMap(x,z)\midZ, #PB_Absolute)
      MoveEntity(PathMap(x,z)\entityPath, PathMap(x,z)\midX, 10, PathMap(x,z)\midZ, #PB_Absolute)
    Next
  Next
  
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial1)
  FreeMaterial(tempMaterial2)
  FreeTexture(tempTexture1)
  FreeTexture(tempTexture2)
  
  FreeList(blockedTiles())
  FreeList(UnwalkableAreas())
  
EndProcedure

Procedure.l FindPath(PathfinderID.l, StartUnitX.l, StartUnitZ.l, TargetUnitX.l, TargetUnitZ.l)
  
  DisableDebugger
  
  Shared      mapWidth, mapHeight, tileSizeD, tileSizeX, tileSizeZ
  Protected.b found = #False
  Protected.l pathfinderElement, startX, startZ, targetX, targetZ, parentX, parentZ, x, z, n, gCost, hCost, fCost, minCost, nextX,nextZ
  Protected.i startTime = ElapsedMilliseconds()
  
  If PathfinderID > 0
    ForEach Pathfinder()
      If Pathfinder()\id = PathfinderID
        pathfinderElement = ListIndex(Pathfinder())
        ClearList(Pathfinder()\waypoints())
        found = #True
        Break
      EndIf
    Next
  EndIf
  
  If Not found
    AddElement(Pathfinder())
    Pathfinder()\id   = ListIndex(Pathfinder()) + 1
    pathfinderElement = ListIndex(Pathfinder())
    PathfinderID      = Pathfinder()\id
  Else
    found = #False
  EndIf
  
  For x = 0 To mapWidth-1
    For z = 0 To mapHeight-1
      PathMap(x,z)\onClosedList = #False
      HideEntity(PathMap(x,z)\entityPath, #True)
    Next
  Next
  
  startX  = ConvertUnitToTileX(StartUnitX)
  startZ  = ConvertUnitToTileZ(StartUnitZ)
  targetX = ConvertUnitToTileX(TargetUnitX)
  targetZ = ConvertUnitToTileZ(TargetUnitZ)
  
  SelectElement(Pathfinder(), pathfinderElement)
  AddElement(Pathfinder()\waypoints())
  Pathfinder()\waypoints()\x = startX
  Pathfinder()\waypoints()\z = startZ
    
  If startX = targetX And startZ = targetZ
    ProcedureReturn PathfinderID;#Path_isStartPoint
  EndIf
  
  If PathMap(targetX,targetZ)\isBlocked
    ProcedureReturn PathfinderID;#Path_isBlocked
  EndIf
  
  parentX = startX
  parentZ = startZ
  
  HideEntity(PathMap(parentX,parentZ)\entityPath, #False)
  
  found = #False
  
  Repeat
    
    PathMap(parentX,parentZ)\onClosedList = #True
    
    n       = 0
    fCost   = 0
    minCost = mapWidth * mapHeight * tileSizeX * tileSizeZ
    
    ;Debug "Parent= x:"+Str(parentX)+", z:"+Str(parentZ)
    
    For z = -1 To 1
      For x = -1 To 1
        
        If PathMap(parentX+x,parentZ+z)\onClosedList = #False And PathMap(parentX+x,parentZ+z)\isBlocked = #False
          
          If x = 0 And z <> 0
            gCost = tileSizeZ
          ElseIf z = 0 And x <> 0
            gCost = tileSizeX
          Else
            gCost = tileSizeD
          EndIf
          
          hCost = Abs(targetX-(parentX+x)) * tileSizeX + Abs(targetZ-(parentZ+z)) * tileSizeZ
          
          fCost = gCost + hCost
          ;Debug "x:"+Str(parentX+x)+", z:"+Str(parentZ+z)+" = "+Str(fCost)
          
          If fCost < minCost
            minCost = fCost
            nextX   = parentX+x
            nextZ   = parentZ+z
          EndIf
          
          n + 1
          
        EndIf
        
      Next
    Next
    
    If n = 0
      SelectElement(Pathfinder(), pathfinderElement)
      ClearList(Pathfinder()\waypoints())
      AddElement(Pathfinder()\waypoints())
      Pathfinder()\waypoints()\x = startX
      Pathfinder()\waypoints()\z = startZ
      ;Debug "no path available to point, x:"+Str(targetX)+", z:"+Str(targetZ)+", took "+Str(ElapsedMilliseconds()-startTime)+" ms"
      ProcedureReturn PathfinderID;#Path_notAvailable
    EndIf
    
    ;Debug "Cheapest= x:"+Str(nextX)+", z:"+Str(nextZ)
    
    SelectElement(Pathfinder(), pathfinderElement)
    AddElement(Pathfinder()\waypoints())
    Pathfinder()\waypoints()\x = nextX
    Pathfinder()\waypoints()\z = nextZ
    
    If nextX = targetX And nextZ = targetZ
      found = #True
    Else
      parentX = nextX
      parentZ = nextZ
    EndIf
    
    If IsEntity(PathMap(nextX,nextZ)\entityPath)
      HideEntity(PathMap(nextX,nextZ)\entityPath, #False)
    Else
      ;Debug "no path entity? x:"+Str(nextX)+", z:"+Str(nextZ)
    EndIf
    
  Until found = #True
  
  SelectElement(Pathfinder(), pathfinderElement)
  Pathfinder()\notFinished = #True
  
  EnableDebugger
  
  Debug "Path found in "+Str(ElapsedMilliseconds()-startTime)+" ms"
  
  ProcedureReturn PathfinderID
  
EndProcedure

Procedure.b GetNextWaypoint(PathfinderID.l, *Target.Vec3)
  
  Static.l    lastX, lastZ
  Protected.l pathfinderElement
  
  If ListSize(Pathfinder()) = 0
    ProcedureReturn #False
  EndIf
  
  ForEach Pathfinder()
    If Pathfinder()\id = PathfinderID
      pathfinderElement = ListIndex(Pathfinder())
      Break
    EndIf
  Next
  
  If Pathfinder()\notFinished
    
    PathMap(lastX,lastZ)\isBlocked = #False
    
    SelectElement(Pathfinder(), pathfinderElement)
    FirstElement(Pathfinder()\waypoints())
    *Target\x = PathMap(Pathfinder()\waypoints()\x,Pathfinder()\waypoints()\z)\midX
    *Target\z = PathMap(Pathfinder()\waypoints()\x,Pathfinder()\waypoints()\z)\midZ
    
    lastX = Pathfinder()\waypoints()\x
    lastZ = Pathfinder()\waypoints()\z
    PathMap(Pathfinder()\waypoints()\x,Pathfinder()\waypoints()\z)\isBlocked = #True
    
    DeleteElement(Pathfinder()\waypoints(), 1)
    
    If ListSize(Pathfinder()\waypoints()) = 0
      Pathfinder()\notFinished = #False
    EndIf
    
    ProcedureReturn #True
    
  Else
    ProcedureReturn #False
  EndIf
  
EndProcedure

Procedure Level_Create()
  
  Shared      Level
  Protected.i u, v, c, tempTexture, tempMaterial, tempMesh, cubeSize, cubeSize2, startTime
  NewList     blockedAreas.structBlockedArea()
  
  ; ceiling
  tempTexture = CreateTexture(#PB_Any, 256, 512)
  StartDrawing(TextureOutput(tempTexture))
  Box(0, 0, TextureWidth(tempTexture), TextureHeight(tempTexture), RGB(0, 0, 0))
  For u = 0 To TextureWidth(tempTexture)-1 Step 2
    For v = 0 To TextureHeight(tempTexture)-1 Step 2
      If Random(100) > 98
        c = Random(128)
        Circle(u, v, 1, RGB(c+128, c+128, c+128))
      EndIf
    Next
  Next
  StopDrawing()
  tempMaterial = CreateMaterial(#PB_Any, TextureID(tempTexture))
  MaterialFilteringMode(tempMaterial, #PB_Material_Anisotropic, 8)
  MaterialShadingMode(tempMaterial, #PB_Material_Phong)
  MaterialBlendingMode(tempMaterial, #PB_Material_Add)
  ScrollMaterial(tempMaterial, 0.1, 0.05, #PB_Material_Animated)
  tempMesh = CreatePlane(#PB_Any, 512, 1024, 1, 1, 1, 1)
  Level\entCeil = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_None)
  MoveEntity(Level\entCeil, 0, 40, 0)
  RotateEntity(Level\entCeil, 180, 0, 0)
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial)
  FreeTexture(tempTexture)
  
  ; floor
  tempTexture = CreateTexture(#PB_Any, 64, 64)
  StartDrawing(TextureOutput(tempTexture))
  Box(0, 0, TextureWidth(tempTexture), TextureHeight(tempTexture), RGB(0, 0, 0))
  Box(0, 0, TextureWidth(tempTexture)/2, TextureHeight(tempTexture)/2, RGB(139, 69, 19))
  Box(TextureWidth(tempTexture)/2, TextureHeight(tempTexture)/2, TextureWidth(tempTexture)/2, TextureHeight(tempTexture)/2, RGB(139, 69, 19))
  Box(0, TextureHeight(tempTexture)/2, TextureWidth(tempTexture)/2, TextureHeight(tempTexture)/2, RGB(255, 222, 173))
  Box(TextureWidth(tempTexture)/2, 0, TextureWidth(tempTexture)/2, TextureHeight(tempTexture)/2, RGB(255, 222, 173))
  StopDrawing()
  tempMaterial = CreateMaterial(#PB_Any, TextureID(tempTexture))
  MaterialFilteringMode(tempMaterial, #PB_Material_Anisotropic, 8)
  tempMesh = CreatePlane(#PB_Any, 512, 1024, 1, 1, 8, 16)
  Level\entFloor = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_Ground)
  MoveEntity(Level\entFloor, 0, -10, 0)
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial)
  FreeTexture(tempTexture)
  
  AddElement(blockedAreas())
  blockedAreas()\startX = -256
  blockedAreas()\endX   = 256
  blockedAreas()\startZ = -512
  blockedAreas()\endZ   = -512
  AddElement(blockedAreas())
  blockedAreas()\startX = -256
  blockedAreas()\endX   = 256
  blockedAreas()\startZ = 512
  blockedAreas()\endZ   = 512
  AddElement(blockedAreas())
  blockedAreas()\startX = -256
  blockedAreas()\endX   = -256
  blockedAreas()\startZ = -512
  blockedAreas()\endZ   = 512
  AddElement(blockedAreas())
  blockedAreas()\startX = 256
  blockedAreas()\endX   = 256
  blockedAreas()\startZ = -512
  blockedAreas()\endZ   = 512
  
  ; walls Left & Right
  tempTexture = CreateTexture(#PB_Any, 64, 64)
  StartDrawing(TextureOutput(tempTexture))
  Box(0, 0, TextureWidth(tempTexture), TextureHeight(tempTexture), RGB(0, 0, 0))
  Box(0, 0, TextureWidth(tempTexture)/2, TextureHeight(tempTexture), RGB(128, 128, 128))
  Box(TextureWidth(tempTexture)/2, 0, TextureWidth(tempTexture)/2, TextureHeight(tempTexture), RGB(160, 160, 160))
  StopDrawing()
  tempMaterial = CreateMaterial(#PB_Any, TextureID(tempTexture))
  MaterialFilteringMode(tempMaterial, #PB_Material_Anisotropic, 8)
  tempMesh = CreatePlane(#PB_Any, 1024, 50, 1, 1, 10, 1)
  Level\entWallLe = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_None)
  MoveEntity(Level\entWallLe, -256, 15, 0)
  RotateEntity(Level\entWallLe, 90, 90, 0)
  Level\entWallRi = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_None)
  MoveEntity(Level\entWallRi, 256, 15, 0)
  RotateEntity(Level\entWallRi, 90, 270, 0)
  FreeMesh(tempMesh)
  
  ; walls Front & Back
  tempMesh = CreatePlane(#PB_Any, 512, 50, 1, 1, 5, 1)
  Level\entWallFr = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_None)
  MoveEntity(Level\entWallFr, 0, 15, -512)
  RotateEntity(Level\entWallFr, 90, 0, 0)
  Level\entWallBa = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 0, 0, #Mask_None)
  MoveEntity(Level\entWallBa, 0, 15, 512)
  RotateEntity(Level\entWallBa, 270, 0, 0)
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial)
  FreeTexture(tempTexture)
  
  ; blocks
  cubeSize  = 10
  cubeSize2 = cubeSize/2
  tempTexture = CreateTexture(#PB_Any, 64, 64)
  StartDrawing(TextureOutput(tempTexture))
  Box(0, 0, TextureWidth(tempTexture), TextureHeight(tempTexture), RGB(192, 192, 192))
  StopDrawing()
  tempMaterial = CreateMaterial(#PB_Any, TextureID(tempTexture))
  MaterialFilteringMode(tempMaterial, #PB_Material_Anisotropic, 8)
  tempMesh = CreateCube(#PB_Any, cubeSize)
  
  Level\entBlock01 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), -100, 15, -300)
  ScaleEntity(Level\entBlock01, 4, 1, 2)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock01) - 2 * cubeSize
  blockedAreas()\endX   = blockedAreas()\startX + 4 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock01) - cubeSize2
  blockedAreas()\endZ   = blockedAreas()\startZ + 2 * cubeSize
  
  Level\entBlock02 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 50, 15, -300)
  ScaleEntity(Level\entBlock02, 2, 1, 4)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock02) - cubeSize2
  blockedAreas()\endX   = blockedAreas()\startX + 2 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock02) - 2 * cubeSize
  blockedAreas()\endZ   = blockedAreas()\startZ + 4 * cubeSize
  
  Level\entBlock03 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 15, -200)
  ScaleEntity(Level\entBlock03, 4, 1, 2)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock03) - 2 * cubeSize
  blockedAreas()\endX   = blockedAreas()\startX + 4 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock03) - cubeSize2
  blockedAreas()\endZ   = blockedAreas()\startZ + 2 * cubeSize
  
  Level\entBlock04 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), -50, 15, -200)
  ScaleEntity(Level\entBlock04, 2, 1, 4)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock04) - cubeSize2
  blockedAreas()\endX   = blockedAreas()\startX + 2 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock04) - 2 * cubeSize
  blockedAreas()\endZ   = blockedAreas()\startZ + 4 * cubeSize
  
  Level\entBlock05 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 100, 15, 0)
  ScaleEntity(Level\entBlock05, 4, 1, 2)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock05) - 2 * cubeSize
  blockedAreas()\endX   = blockedAreas()\startX + 4 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock05) - cubeSize2
  blockedAreas()\endZ   = blockedAreas()\startZ + 2 * cubeSize
  
  Level\entBlock06 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), -50, 15, 0)
  ScaleEntity(Level\entBlock06, 2, 1, 4)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock06) - cubeSize2
  blockedAreas()\endX   = blockedAreas()\startX + 2 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock06) - 2 * cubeSize
  blockedAreas()\endZ   = blockedAreas()\startZ + 4 * cubeSize
  
  Level\entBlock07 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 100, 15, 100)
  ScaleEntity(Level\entBlock07, 4, 1, 2)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock07) - 2 * cubeSize
  blockedAreas()\endX   = blockedAreas()\startX + 4 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock07) - cubeSize2
  blockedAreas()\endZ   = blockedAreas()\startZ + 2 * cubeSize
  
  Level\entBlock08 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 0, 15, 100)
  ScaleEntity(Level\entBlock08, 2, 1, 4)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock08) - cubeSize2
  blockedAreas()\endX   = blockedAreas()\startX + 2 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock08) - 2 * cubeSize
  blockedAreas()\endZ   = blockedAreas()\startZ + 4 * cubeSize
  
  Level\entBlock09 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), -100, 15, 200)
  ScaleEntity(Level\entBlock09, 4, 1, 2)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock09) - 2 * cubeSize
  blockedAreas()\endX   = blockedAreas()\startX + 4 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock09) - cubeSize2
  blockedAreas()\endZ   = blockedAreas()\startZ + 2 * cubeSize
  
  Level\entBlock10 = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), 100, 15, 300)
  ScaleEntity(Level\entBlock10, 2, 1, 4)
  AddElement(blockedAreas())
  blockedAreas()\startX = EntityX(Level\entBlock10) - cubeSize2
  blockedAreas()\endX   = blockedAreas()\startX + 2 * cubeSize
  blockedAreas()\startZ = EntityZ(Level\entBlock10) - 2 * cubeSize
  blockedAreas()\endZ   = blockedAreas()\startZ + 4 * cubeSize
  
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial)
  FreeTexture(tempTexture)
  
  startTime = ElapsedMilliseconds()
  DisableDebugger
  InitPathfinding(1, -256, -512, 512, 1024, 16, 16, blockedAreas())
  EnableDebugger
  Debug "Map path creation took "+Str(ElapsedMilliseconds()-startTime)+" ms"
  
  ; done !
  
EndProcedure

Procedure Player_Create()
  
  Shared      Player
  Protected.i tempTexture, tempMaterial, tempMesh
  
  tempTexture = CreateTexture(#PB_Any, 1, 1)
  StartDrawing(TextureOutput(tempTexture))
  Plot(0, 0, RGB(255, 69, 0))
  StopDrawing()
  tempMaterial = CreateMaterial(#PB_Any, TextureID(tempTexture))
  tempMesh     = CreateCylinder(#PB_Any, 5, 30)
  
  With Player
    
    \id = 0
    
    \zoom = 500
    
    \nodeMain    = CreateNode(#PB_Any)
    \nodeCamera  = CreateNode(#PB_Any, 0, \zoom, 0)
    \nodeForward = CreateNode(#PB_Any, 0, 0, -1)
    
    \camera = CreateCamera(#PB_Any, 0, 0, 100, 100)
    RotateCamera(\camera, -90, 0, 0, #PB_Absolute)
    
    \entity = CreateEntity(#PB_Any, MeshID(tempMesh), MaterialID(tempMaterial), -8, 15, -8)
    
    AttachNodeObject(\nodeMain, NodeID(\nodeForward))
    AttachNodeObject(\nodeMain, NodeID(\nodeCamera))
    AttachNodeObject(\nodeCamera, CameraID(\camera))
    
  EndWith
  
  FreeMesh(tempMesh)
  FreeMaterial(tempMaterial)
  FreeTexture(tempTexture)
  
EndProcedure

Procedure.b Player_UpdateControls()
  
  Shared      Level, Player, MouseX, MouseY
  Static.b    clickedL, clickedR
  Protected.l MouseW
  Protected.i pick
  
  If ExamineKeyboard()
    If KeyboardReleased(#PB_Key_Escape)
      ProcedureReturn #False
    EndIf
  EndIf
  
  If ExamineMouse()
    
    MouseX = MouseX()
    MouseY = MouseY()
    
    MouseW = MouseWheel()
    If MouseW
      Player\zoom - MouseWheel() * 10
    Else
      Player\zoom = 0
    EndIf
    
    If MouseButton(#PB_MouseButton_Left)
      If clickedL = #False
        pick = MousePick(Player\camera, MouseX, MouseY, #Mask_Ground)
        If pick >= 0
          clickedL = #True
          Player\Target\x     = PickX()
          Player\Target\y     = PickY()
          Player\Target\z     = PickZ()
          Player\id = FindPath(Player\id, EntityX(Player\entity), EntityZ(Player\entity), Player\Target\x, Player\Target\z)
        EndIf
      EndIf
    Else
      clickedL = #False
    EndIf
    
  EndIf
  
  ProcedureReturn #True
  
EndProcedure

Procedure Player_Update()
  
  Shared         Player, TimeSinceLastFrame
  Static.b       isMoving
  Static.f       movementPhase
  Protected.b    result
  Protected.l    n
  Protected.f    x, z, distance, xStep, zStep
  Protected.Vec3 target
  
  result = Player_UpdateControls()
  
  With Player
    
    If isMoving
      
      movementPhase + (#Player_Speed / TimeSinceLastFrame)
      ComputeSpline(\splineTarget, movementPhase)
      x = SplineX(\splineTarget)
      z = SplineZ(\splineTarget)
      
      MoveEntity(\entity, x, \Target\y, z, #PB_Absolute)
      EntityLookAt(\entity, x, EntityY(\entity), z)
      
      If isMoving And movementPhase > 1
        FreeSpline(\splineTarget)
        \splineTarget = 0
        isMoving = #False
        movementPhase = 0
      EndIf
      
    Else
      
      If GetNextWaypoint(\id, target)
        
        isMoving      = #True
        movementPhase = 0
        
        x        = target\x - EntityX(\entity)
        z        = target\z - EntityZ(\entity)
        distance = Sqr(x * x + z * z)
        xStep    = x / distance
        zStep    = z / distance
        Player\splineTarget = CreateSpline(#PB_Any)
        
        For n = 1 To Int(distance)
          x = EntityX(\entity) + n * xStep
          z = EntityZ(\entity) + n * zStep
          AddSplinePoint(\splineTarget, x, \Target\y, z)
        Next
        AddSplinePoint(\splineTarget, target\x, \Target\y, target\z)
        
      EndIf

    EndIf
    
    If NodeY(\nodeCamera) - \zoom > 40
      MoveNode(\nodeCamera, 0, \zoom, 0, #PB_Relative)
    Else
      MoveNode(\nodeCamera, 0, 40, 0, #PB_Absolute)
    EndIf
    
    MoveNode(\nodeMain, EntityX(\entity), EntityY(\entity), EntityZ(\entity), #PB_Absolute)
    RotateNode(\nodeMain, 0, EntityYaw(\entity), 0, #PB_Absolute)
    
  EndWith
  
  ProcedureReturn result
  
EndProcedure

Wenn ich jetzt den Debugger für die Procedure FindPath() ausschalte, dann geht es schnell. Mit dem Funktionsaufruf:

Code: Alles auswählen

InitPathfinding(1, -256, -512, 512, 1024, 10, 10, blockedAreas())

mit den Parameter 6 und 7 kann man die Auflösung der Pfadfinder-Quadrate beeinflussen. Eine Auflösung von 8 und weniger schafft meine Graka aber ob der zig Entities nicht.

Zur OpenList, wie ich beschrieben hatte, habe ich alle (überflüssigen) Funktionen erstmal herausgenommen, das globale Array fungiert als Open und Close-List. Der Code ist jetzt nicht kommentiert, wenn da noch was nachgereicht werden soll, bitte nochmal melden.

[CSHW89]

Zur OpenList, wie ich beschrieben hatte, habe ich alle (überflüssigen) Funktionen erstmal herausgenommen, das globale Array fungiert als Open und Close-List. Der Code ist jetzt nicht kommentiert, wenn da noch was nachgereicht werden soll, bitte nochmal melden.

Nein tut es definitiv nicht. Als Close-List schon, aber nicht als OpenList. Du gehst ja zu keiner Zeit zu einem schon besuchten Knoten zurück. Wenn der Algorithmus z.B. in eine Sackgasse läuft, würde er nicht mehr rauskommen, oder er merkt auch nicht, dass der Weg, den er gerade geht, nicht gut ist. Er geht immer nur vom jetzigen Knoten zu dem Knoten, der bisher noch nicht besucht wurde, und am nähesten zum Ziel ist. Das ist definitiv nicht A*.

Ein kleines Beispiel. Ich weiß, man kann es nicht sooo gut erkennen. Gehe von s (Start) zu e (Ende). x ist ne Mauer. Die Striche geben die nächste Richtung an. Bei der Markierung (hier) geht auch A* nach halb links unten (ist ja in diesem Moment besser als nach rechts zu gehen). Allerdings merkt er irgendwann beim Umweg, oh das war aber ne falsche Entscheidung, und sucht nochmal von diesem Punkt. Das macht A* kontinuierlich. In jedem Schritt überlegt er, von welchem Knoten ist es nun besser, einen weiteren Schritt zu machen. So wird A* ziemlich schnell merken, dass an der Stelle (hier) der beste Weg nach rechts ist. Das macht dein Algorithmus aber nicht.

Code: Alles auswählen

xxxxxxxxxxxxxx
x  /--xx s   x
x |xxx\x |   x
x |xxx|x |   x
x |xx/x  /   x           <--- hier
x |x/xxx/xx  x
x |x|xx/xx   x
x |xx\-xx    x
x \xxxxx     x
x  ------e   x
xxxxxxxxxxxxxx

lg Kevin

Edit: hier sieht man übrigens sehr schön, dass A* immer irgendwo anders hinspringt. Es ist kein kontinuierlicher Weg, den er geht, sondern fügt immer den besten Nachbarknoten von allen bisher besuchten Knoten hinzu (nicht nur vom letzten).
http://commons.wikimedia.org/wiki/File: ... mation.gif

[Makke]

Stimmt genau das ist nicht vorgesehen. Er geht nur an Hindernissen vorbei. Ich brauche den auch nicht für so komplexe Wegfindungen. Gegner rennt zum Spieler auf einer Straße, er soll nur an Hindernissen vorbei laufen.