Programmablauf zu langsam - Gründe gesucht

moin · Beitrag von **moin** » 11.07.2008 10:14

Hallo,
ich habe ein Programm zur Wegfindung (Pathfinding) geschrieben, welches den A*-Algorithmus verwendet. Leider ist dieses Programm sehr langsam. Woran könnte das liegen???
Könnt Ihr mir die offensichtlichen Zeitbremsen nennen?

Ich sehe folgende mögliche Zeitbremsen:
- keine Verwendung von Pointern, sondern von dem „langsamen“ Befehl „SelectElement()“
- Das ständige „StartDrawing(ScreenOutput())“ , „StopDrawing()“ und „FlipBuffers()“

Euer moin

P.S.: Wenn Ihr das Programm ausprobiert: kleiner Bug
Der Weg kann nicht immer gefunden werden, wenn die x oder y-Koordinate des Suchpfads „0“ beträgt

Code: Alles auswählen

Enumeration
#Font6
#Font9
#Text_1
#Text_2
#Text_3

EndEnumeration

Global Text_1

InitSprite()
InitKeyboard()
InitSprite3D()
InitMouse()
UseJPEGImageDecoder()
UseJPEGImageEncoder()

Feldgroesse_x = 12
Feldgroesse_y = 12

Structure AStern_Feld
	x.l
	y.l
	ParentX.l
	ParentY.l
	f.l
	g.l
	h.l
	cost.b
EndStructure
Global NewList openlist.AStern_Feld()
Global NewList closedlist.AStern_Feld()
;Global NewList CountList.AStern_Feld()


Global Dim Map.b(Feldgroesse_x+1,Feldgroesse_y+1) 
Global Dim Map_belegt.b(Feldgroesse_x+1,Feldgroesse_y+1)
c.s
G_Kosten.l
H_Kosten.l
F_Kosten.l
start_x.l
start_y.l
ziel_x.l
ziel_y.l
aktuellesFeld_x.l
aktuellesFeld_Y.l
aktuellesFeld_x2.l
aktuellesFeld_Y2.l

OpenWindow(0,0,0,620,620,"AStar Versuch - Jörn Bartels", #PB_Window_SizeGadget|#PB_Window_MaximizeGadget|#PB_Window_MinimizeGadget|#PB_Window_TitleBar|#PB_Window_SystemMenu)
OpenWindowedScreen(WindowID(0),0, 0,450,450,0,0,0)
ClearScreen($FFFFFF)

AddKeyboardShortcut(0, #PB_Shortcut_1, 99)
AddKeyboardShortcut(0, #PB_Shortcut_S, 100)
AddKeyboardShortcut(0, #PB_Shortcut_E, 101)
AddKeyboardShortcut(0, #PB_Shortcut_Space, 102)

LoadFont(#Font6, "Arial"  ,  6)
LoadFont(#Font9, "Arial"  ,  9)

If CreateGadgetList(WindowID(0))
   TextGadget(#Text_1, 460, 5, 155, 100, "Suchdauer in ms")
   TextGadget(#Text_2,1, 460, 255, 250, "Mauszeiger wird Startpunkt: s"+ Chr(10) +"Mauszeiger wird Endpunkt:  e"+ Chr(10) + "Weg suchen:                        Leertaste"+ Chr(10) +"linke Maustaste: Feld sperren"+ Chr(10) +"rechte Maustaste: Feld freigeben")
 EndIf

StartDrawing(ScreenOutput())
	DrawingMode(#PB_2DDrawing_Outlined|#PB_2DDrawing_Transparent)
  DrawingFont(FontID(#Font9))
	For y = 0 To Feldgroesse_y
		For x = 0 To Feldgroesse_x
			Box(x*32, y*32, 32, 32,$000000) 
			DrawText(10+(x*32),420,Str(x),$0000FF) 
			DrawText(420,10+(y*32),Str(y),$0000FF) 
		Next
	Next
	
	DrawingFont(FontID(#Font6))
	For y = 0 To Feldgroesse_y
		For x = 0 To Feldgroesse_x
	;		DrawText(3+(x*32),2+y*32,"F: "+Str(1234),$0000FF)
	;		DrawText(3+(x*32),13+y*32,"G: "+Str(234),$0000FF) 
	;		DrawText(3+(x*32),21+y*32,"H: "+Str(1000),$0000FF)
		Next
	Next

   StopDrawing()
FlipBuffers()

Repeat ; Start of the event loop
   ;Event = WindowEvent() ; This line waits until an event is received from Windows 
  Event = WaitWindowEvent(1) ; This line waits until an event is received from Windows
  WindowID = EventWindow() ; The Window where the event is generated, can be used in the gadget procedures
  GadgetID = EventGadget() ; Is it a gadget event?
  EventType = EventType() ; The event type

Select Event
    Case #WM_LBUTTONDOWN
          If WindowMouseX(0)/32 < 13 And WindowMouseY(0)/32 < 13
          ;Debug "#WM_LBUTTONDOWN " + Str(EventwParam()) 
          StartDrawing(ScreenOutput())
          Box(WindowMouseX(0)/32*32+1,WindowMouseY(0)/32*32+1, 30, 30,$F0F00F) 
          Map(WindowMouseX(0)/32, WindowMouseY(0)/32) = #True
          Map_belegt(WindowMouseX(0)/32, WindowMouseY(0)/32) = #True
          ;Debug Str((WindowMouseX(0)-0)/32)
          ;Debug Str((WindowMouseY(0)-0)/32)  
          StopDrawing()
          FlipBuffers()
          EndIf
    Case #WM_RBUTTONDOWN
          If WindowMouseX(0)/32 < 13 And WindowMouseY(0)/32 < 13
          ;Debug "#WM_LBUTTONDOWN " + Str(EventwParam()) 
          StartDrawing(ScreenOutput())
          Box(WindowMouseX(0)/32*32+1,WindowMouseY(0)/32*32+1, 30, 30,$FFFFFF) 
          Map(WindowMouseX(0)/32, WindowMouseY(0)/32) = #False
          Map_belegt(WindowMouseX(0)/32, WindowMouseY(0)/32) = #False
          ;Debug Str((WindowMouseX(0)-0)/32)
          ;Debug Str((WindowMouseY(0)-0)/32)  
          StopDrawing()
          FlipBuffers()
          EndIf 
    Case #PB_Event_Menu
        EventMenu = EventMenu()
      Select EventMenu      
        Case 99
          c=""
          For a=0 To 12
           For b=0 To 12
            c = c + Str(Map(b,a))
           Next
           Debug c
           c=""
           
          Next
          
         Case 100   ;Startpunkt setzen
          If WindowMouseX(0)/32 < 13 And WindowMouseY(0)/32 < 13
           Map_belegt(start_x, start_y) = #False
           StartDrawing(ScreenOutput())
           Box(start_x*32+1,start_y*32+1, 30, 30, RGB($FF,$FF,$FF))
           Box(WindowMouseX(0)/32*32+1,WindowMouseY(0)/32*32+1, 30, 30, RGB($33,$99,$00)) 
           StopDrawing()
           FlipBuffers()
           start_x=WindowMouseX(0)/32
           start_y=WindowMouseY(0)/32
           Map_belegt(start_x, start_y) = #True
          EndIf
         Case 101   ;Endpunkt setzen
          If WindowMouseX(0)/32 < 13 And WindowMouseY(0)/32 < 13
           StartDrawing(ScreenOutput())
           Map_belegt(start_x, start_y) = #False
           Box(ziel_x*32+1,ziel_y*32+1, 30, 30, RGB($FF,$FF,$FF))
           Box(WindowMouseX(0)/32*32+1,WindowMouseY(0)/32*32+1, 30, 30,RGB($CC,$00,$00)) 
           StopDrawing()
           FlipBuffers()
           ziel_x=WindowMouseX(0)/32
           ziel_y=WindowMouseY(0)/32
           Map_belegt(start_x, start_y) = #True
      EndIf
   Case 102   ;Wegsuche starten
           StartTime = ElapsedMilliseconds()             ; ermittelt den aktuellen Wert
            Gosub Weg_suchen
            Gosub Weg_anzeigen
            ElapsedTime = ElapsedMilliseconds()-StartTime ; der 'ElapsedTime' Wert sollte ca. 1000 Millisekunden betragen
            SetGadgetText(#Text_1, Str(ElapsedTime)+" ms Suchdauer")
            
         EndSelect              
 EndSelect
  
 Until Event = #PB_Event_CloseWindow
  
End
;###########################################################################################
;Startpunkt auf die ClosedList setzen

;Es fehlt noch die Ränder in der Map = 1 zu setzen
Weg_suchen:
ClearList(openlist()) ;OpenList leeren
ClearList(closedlist())         ;ClosedList leeren

For j=0 To Feldgroesse_x+1
   For I=0 To Feldgroesse_x+1
      Map_belegt(I,j)=Map(I,j)
      StartDrawing(ScreenOutput())
      If Map(I,j)=#True
         Box(I*32+1,j*32+1, 30, 30, $F0F00F)
      Else
          Box(I*32+1,j*32+1, 30, 30, RGB($FF,$FF,$FF))
      EndIf
      
      StopDrawing()
   Next
Next
Map_belegt(start_x,start_y)=#True
;Map_belegt(ziel_x,ziel_y)=#True
StartDrawing(ScreenOutput())
Box(start_x*32+1,start_y*32+1, 30, 30, RGB($33,$99,$00))
Box(ziel_x*32+1,ziel_y*32+1, 30, 30, RGB($CC,$00,$00))
StopDrawing()

AddElement(closedlist())
	closedlist()\x = start_x
	closedlist()\y = start_y
	closedlist()\ParentX = start_x
	closedlist()\ParentY = start_y
	
   aktuellesFeld_x = start_x
	aktuellesFeld_Y = start_y
G_Kosten = 0	
H_Kosten = 0
F_Kosten = 0

;Suchschleife1:
Repeat
;Die Felder um das aktuelle Feld herum werden untersucht
	
;Das Feld rechts von aktuellen Feld wird untersucht
;Es wird überprüft, ob der Rechte Rand erreicht worden ist und ob die Map ein Hindernis vorhersagt

   If aktuellesFeld_x+1<=Feldgroesse_x  And Map_belegt(aktuellesFeld_x+1,aktuellesFeld_Y)=0 
  AddElement(openlist())
  	openlist()\x = aktuellesFeld_x+1
  	openlist()\y = aktuellesFeld_Y
  	openlist()\ParentX = aktuellesFeld_x
  	openlist()\ParentY = aktuellesFeld_Y
  	openlist()\g = G_Kosten + 10
  	openlist()\f= (Abs((aktuellesFeld_x+1)-ziel_x) + Abs(aktuellesFeld_Y-ziel_y))*10
	  openlist()\h= openlist()\g + openlist()\h
	  
	  Map_belegt(aktuellesFeld_x+1, aktuellesFeld_Y) = #True
	  
	  StartDrawing(ScreenOutput())
	  DrawingFont(FontID(#Font6))
	  Box((aktuellesFeld_x+1)*32+1,(aktuellesFeld_Y)*32+1, 30, 30,RGB($3F,$FF,$01)) 
     Box((aktuellesFeld_x+1)*32+1,(aktuellesFeld_Y)*32+1, 2, 30 ,$F000FF) ;Linie links
	  ;Line(aktuellesFeld_x+1*32+1, aktuellesFeld_Y*32+30, 30, 0 ,$F000FF)
	  
     DrawText((3+(aktuellesFeld_x+1)*32+1),21+aktuellesFeld_Y*32,"H: "+Str((Abs((aktuellesFeld_x+1)-ziel_x) + Abs(aktuellesFeld_Y-ziel_y))*10)+" ",RGB($3F,$FF,$01))              ;H-Kosten anzeigen
	  DrawText((3+(aktuellesFeld_x+1)*32+1),13+aktuellesFeld_Y*32,"G: "+Str(G_Kosten + 10)+" ",RGB($3F,$FF,$01))  ;G-Kosten anzeigen
	  StopDrawing()
    FlipBuffers()
EndIf

;Das Feld links von aktuellen Feld wird untersucht
;Es wird überprüft, ob der linke Rand erreicht worden ist und ob die Map ein Hindernis vorhersagt
If aktuellesFeld_x-1>=0  And Map_belegt(aktuellesFeld_x-1,aktuellesFeld_Y)=0 
  AddElement(openlist())
  	openlist()\x = aktuellesFeld_x-1
  	openlist()\y = aktuellesFeld_Y
  	openlist()\ParentX = aktuellesFeld_x
  	openlist()\ParentY = aktuellesFeld_Y
  	openlist()\g = G_Kosten + 10
  	openlist()\f= (Abs((aktuellesFeld_x-1)-ziel_x) + Abs(aktuellesFeld_Y-ziel_y))*10
	  openlist()\h= openlist()\g + openlist()\h
	  
	  Map_belegt(aktuellesFeld_x-1, aktuellesFeld_Y) = #True
	  
	  StartDrawing(ScreenOutput())
	  DrawingFont(FontID(#Font6))
	  Box((aktuellesFeld_x-1)*32+1,(aktuellesFeld_Y)*32+1, 30, 30,RGB($3F,$FF,$01))
     Box((aktuellesFeld_x-1)*32+1+29,(aktuellesFeld_Y)*32+1, 2, 30 ,$F000FF)  ;Feld rechts
	  DrawText((3+(aktuellesFeld_x-1)*32+1),21+aktuellesFeld_Y*32,"H: "+Str((Abs((aktuellesFeld_x-1)-ziel_x) + Abs(aktuellesFeld_Y-ziel_y))*10)+" ",RGB($3F,$FF,$01))              ;H-Kosten anzeigen
	  DrawText((3+(aktuellesFeld_x-1)*32+1),13+aktuellesFeld_Y*32,"G: "+Str(G_Kosten + 10)+" ",RGB($3F,$FF,$01))  ;G-Kosten anzeigen
	  StopDrawing()
    FlipBuffers()	  
EndIf
	
;Das Feld über dem aktuellen Feld wird untersucht
;Es wird überprüft, ob der obere Rand erreicht worden ist und ob die Map ein Hindernis vorhersagt
If aktuellesFeld_Y-1>=0  And Map_belegt(aktuellesFeld_x,aktuellesFeld_Y-1)=0 
  AddElement(openlist())
  	openlist()\x = aktuellesFeld_x
  	openlist()\y = aktuellesFeld_Y-1
  	openlist()\ParentX = aktuellesFeld_x
  	openlist()\ParentY = aktuellesFeld_Y
  	openlist()\g = G_Kosten + 10
  	openlist()\f= (Abs((aktuellesFeld_x)-ziel_x) + Abs(aktuellesFeld_Y-1-ziel_y))*10
	  openlist()\h= openlist()\g + openlist()\h
	  
	  Map_belegt(aktuellesFeld_x, aktuellesFeld_Y-1) = #True
	  
	  StartDrawing(ScreenOutput())
	  DrawingFont(FontID(#Font6))
	  Box((aktuellesFeld_x)*32+1,(aktuellesFeld_Y-1)*32+1, 30, 30,RGB($3F,$FF,$01)) 
	  
     DrawText((3+(aktuellesFeld_x)*32+1),21+(aktuellesFeld_Y-1)*32,"H: "+Str((Abs((aktuellesFeld_x)-ziel_x) + Abs(aktuellesFeld_Y-1-ziel_y))*10)+" ",RGB($3F,$FF,$01))              ;H-Kosten anzeigen
	  DrawText((3+(aktuellesFeld_x)*32+1),13+(aktuellesFeld_Y-1)*32,"G: "+Str(G_Kosten + 10)+" ",RGB($3F,$FF,$01))  ;G-Kosten anzeigen
     Box((aktuellesFeld_x)*32+1,(aktuellesFeld_Y-1)*32+1+28, 30, 3 ,$F000FF)  ;Linie unten
   StopDrawing()
    FlipBuffers()	    
EndIf


;Das Feld unter dem aktuellen Feld wird untersucht
;Es wird überprüft, ob der obere Rand erreicht worden ist und ob die Map ein Hindernis vorhersagt
If aktuellesFeld_Y+1<=Feldgroesse_y And Map_belegt(aktuellesFeld_x,aktuellesFeld_Y+1)=0 
  AddElement(openlist())
  	openlist()\x = aktuellesFeld_x
  	openlist()\y = aktuellesFeld_Y+1
  	openlist()\ParentX = aktuellesFeld_x
  	openlist()\ParentY = aktuellesFeld_Y
  	openlist()\g = G_Kosten + 10
  	openlist()\f= (Abs((aktuellesFeld_x)-ziel_x) + Abs(aktuellesFeld_Y-1-ziel_y))*10
	  openlist()\h= openlist()\g + openlist()\h
	  
	  Map_belegt(aktuellesFeld_x, aktuellesFeld_Y+1) = #True
	  
	  StartDrawing(ScreenOutput())
	  DrawingFont(FontID(#Font6))
	  Box((aktuellesFeld_x)*32+1,(aktuellesFeld_Y+1)*32+1, 30, 30,RGB($3F,$FF,$01)) 
     Box((aktuellesFeld_x)*32+1,(aktuellesFeld_Y+1)*32+1, 30, 2 ,$F000FF)  ;Linie oben
	  DrawText((3+(aktuellesFeld_x)*32+1),21+(aktuellesFeld_Y+1)*32,"H: "+Str((Abs((aktuellesFeld_x)-ziel_x) + Abs(aktuellesFeld_Y+1-ziel_y))*10)+" ",RGB($3F,$FF,$01))              ;H-Kosten anzeigen
     DrawText((3+(aktuellesFeld_x)*32+1),13+(aktuellesFeld_Y+1)*32,"G: "+Str(G_Kosten + 10)+" ",RGB($3F,$FF,$01))  ;G-Kosten anzeigen
	  StopDrawing()
    FlipBuffers()	  
EndIf

;Element mit geringsten F-Kosten suchen
FMin.l = 65000
ForEach openlist()
  If openlist()\f < FMin
    FMin = openlist()\f
    FMin_Index.l = ListIndex(openlist())
  EndIf
Next

;Daten im Debugger anzeigen

;;Debug("Anzahl der Elemente in der openlist / closedlist:")
;;Debug(Str(CountList(openlist()))+" / "+Str(CountList(closedlist( ))))
      ;Debug(Str(CountList(openlist()))+" / "+str8)

;;Debug("Kleinstes Element auf der OpenList ist:")
SelectElement(openlist(), FMin_Index)
;;Debug Str(openlist()\x)+"  "+Str(openlist()\y)+"             "+Str(aktuellesFeld_x)+" & "+Str(aktuellesFeld_Y)
;;Debug("")
      ;Debug Str(openlist()\f)
;Aus der OpenList wird das Element mit den geringsten F-Kosten in die Closed List verschoben
AddElement (closedlist())
closedlist()\x = openlist()\x
closedlist()\y = openlist()\y
closedlist()\ParentX = openlist()\ParentX
closedlist()\ParentY = openlist()\ParentY
closedlist()\g = openlist()\g
closedlist()\f = openlist()\f
closedlist()\h = openlist()\h
;aktuellesFeld_x=openlist()\ParentX
;aktuellesFeld_Y=openlist()\ParentY
aktuellesFeld_x=openlist()\x
aktuellesFeld_Y=openlist()\y

Map_belegt(closedlist()\x , closedlist()\y ) = #True

;Debug "openlist:"+Str(openlist()\x)+"  "+Str(openlist()\y)+"        closedlist"+Str(closedlist()\x)+"  "+Str(closedlist()\y)

If ziel_x=openlist()\x And ziel_y=openlist()\y
ziel_erreicht.l=1
Else
ziel_erreicht.l=0
EndIf

DeleteElement(openlist())

;Zielpunkt berechnen fehlt noch
;D.h. Pointer setzen, die auf das Parent-Feld zeigt
;;Debug("Elemente in der OpenList:")
;;ForEach openlist()
;; Debug Str(openlist()\x)+"|"+Str(openlist()\y)
;;Next
;;Debug ("-----------------------------------")

Until CountList(openlist())=0 Or ziel_erreicht=1

Return

Weg_anzeigen:
Return

STARGÅTE · Beitrag von **STARGÅTE** » 11.07.2008 12:01

richtig die Bremse liegt in den Bereichen:

Code: Alles auswählen

For j=0 To Feldgroesse_x+1 
   For I=0 To Feldgroesse_x+1 
      Map_belegt(I,j)=Map(I,j) 
      StartDrawing(ScreenOutput()) 
      If Map(I,j)=#True 
         Box(I*32+1,j*32+1, 30, 30, $F0F00F) 
      Else 
          Box(I*32+1,j*32+1, 30, 30, RGB($FF,$FF,$FF)) 
      EndIf 
      
      StopDrawing() 
   Next 
Next

besser ist es so:

Code: Alles auswählen

StartDrawing(ScreenOutput()) 
For j=0 To Feldgroesse_x+1 
   For I=0 To Feldgroesse_x+1 
      Map_belegt(I,j)=Map(I,j) 
      If Map(I,j)=#True 
         Box(I*32+1,j*32+1, 30, 30, $F0F00F) 
      Else 
          Box(I*32+1,j*32+1, 30, 30, RGB($FF,$FF,$FF)) 
      EndIf 
      

   Next 
Next 
StopDrawing()

Das solltest du überall machen, wo es schleifen gibt oder mehrfachnennungen

außerdem solltest du während der Berechnung des Weges möglichs nix darstellen, die Darstellung erfolgt immer erst nach der Berechung, so läuft beiden deutlich schneller.