Wegfindung optimieren

Purebasium · Beitrag von **Purebasium** » 04.05.2014 17:35

Ich habe letztens folgende Wegfindung programmiert:


Global Dim MapDaten(22, 22)
Global Dim wegdaten(22, 22)
Global Dim id(20, 20)



 Structure Eigenschaft

   
  List weg.w()
   
   ;1|2|3
   ;4|0|5
   ;6|7|8 

 EndStructure
 
 Global Dim mensch.Eigenschaft(1) 
 
   
  Procedure vorhanden(xsrechnen,ysrechnen)
    
    If xsrechnen >= 1 And xsrechnen <= 20
       If ysrechnen >= 1 And ysrechnen <= 20
      
      ProcedureReturn  1
      
       EndIf
    EndIf
    
    
  EndProcedure
  
 xstart= 10
ystart= 5
xziel= 2
yziel= 3






  


  
  
neu: 
For Arrayy = 1 To 20 
    For ArrayX = 1 To 20
      MapDaten(Arrayx, Arrayy) = 0
      
    Next 
  Next 
  
    For Arrayy = 1 To 20
    For ArrayX = 1 To 20
      wegdaten(Arrayx, Arrayy) = 1000
      
    Next 
  Next 
  
  
  
  
  
  
  
  CreateImage(0,20,20);begehbar
  CreateImage(1,20,20);Wand
  CreateImage(2,20,20);startpunkt
  CreateImage(3,20,20);ziel
  CreateImage(4,20,20);weg
  
  StartDrawing(ImageOutput(0))
  Box(0,0,20,20,RGB(0,255,0))
  StopDrawing()
  
  

  StartDrawing(ImageOutput(1))
    Box(0,0,20,20,RGB(0,0,0))
  StopDrawing()
  
  StartDrawing(ImageOutput(2))
    Box(0,0,20,20,RGB(0,0,255))
  StopDrawing()
  
    StartDrawing(ImageOutput(3))
    Box(0,0,20,20,RGB(255,0,0))
  StopDrawing()
  
    
    StartDrawing(ImageOutput(4))
    Box(0,0,20,20,RGB(255,255,0))
  StopDrawing()
  
  
MapDaten(5, 0) = 1

MapDaten(5, 1) = 1

MapDaten(5, 2) = 1

MapDaten(5, 3) = 1

MapDaten(5, 4) = 1

MapDaten(5, 5) = 1

MapDaten(5, 6) = 1

MapDaten(5, 7) = 1

MapDaten(5, 8) = 1

MapDaten(5, 9) = 1

MapDaten(5, 10) = 1

MapDaten(5, 11) = 1

MapDaten(5, 13) = 1

MapDaten(5, 14) = 1

MapDaten(5, 15) = 1

MapDaten(5, 16) = 1

MapDaten(5, 17) = 1

MapDaten(5, 18) = 1

MapDaten(5, 19) = 1


  For wer = 1 To 50
  
  MapDaten(Random(20,1), Random(20,1)) = 1
  
Next wer


wegdaten(xstart,ystart)=1


MapDaten(xstart, ystart) =2




MapDaten(xziel, yziel) = 3




OpenWindow(0,0,0,400,400,"",#PB_Window_ScreenCentered|#PB_Window_SystemMenu)

For x = 1 To 20
 For y= 1 To 20
   id+1
   ButtonImageGadget(id,x*20-20,y*20-20,20,20,ImageID(MapDaten(x, y)))
  ; ButtonGadget(id,x*20-20,y*20-20,20,20,"")
   id(x, y)=id

  Next y
  Next x
  
  ;-felder nummerieren
  
  
  
  
  
  
  


  
  xsrechnen=xstart-1
  ysrechnen=ystart-1
  
  weg =1
  For weg = 1 To 100
    For x=1 To 20
      For y=1 To 20
    xsrechnen=x
  ysrechnen=y
  
If vorhanden(xsrechnen,ysrechnen) = 1
 If wegdaten(xsrechnen,ysrechnen)=weg 
    ;oben
    xsrechnen=x
  ysrechnen=y-1
  
    If wegdaten(xsrechnen,ysrechnen)>(weg+1) And mapdaten(xsrechnen,ysrechnen)=0 And vorhanden(xsrechnen,ysrechnen) = 1
      wegdaten(xsrechnen,ysrechnen)=(weg+1)
     ; SetGadgetText(id(xsrechnen,ysrechnen),Str(weg+1))
  EndIf
  
  
  ;unten
    xsrechnen=x
  ysrechnen=y+1
  
    If wegdaten(xsrechnen,ysrechnen)>(weg+1) And mapdaten(xsrechnen,ysrechnen)=0 And vorhanden(xsrechnen,ysrechnen) = 1
      wegdaten(xsrechnen,ysrechnen)=(weg+1)
     ; SetGadgetText(id(xsrechnen,ysrechnen),Str(weg+1))
  EndIf
  
  
  ;rechts
    xsrechnen=x+1
  ysrechnen=y
  
    If wegdaten(xsrechnen,ysrechnen)>(weg+1) And mapdaten(xsrechnen,ysrechnen)=0 And vorhanden(xsrechnen,ysrechnen) = 1
     wegdaten(xsrechnen,ysrechnen)=(weg+1)
    ;   SetGadgetText(id(xsrechnen,ysrechnen),Str(weg+1))
  EndIf
  
  
  ;links
    xsrechnen=x-1
  ysrechnen=y
  
    If wegdaten(xsrechnen,ysrechnen)>(weg+1) And mapdaten(xsrechnen,ysrechnen)=0 And vorhanden(xsrechnen,ysrechnen) = 1
      wegdaten(xsrechnen,ysrechnen)=(weg+1)
   ;   SetGadgetText(id(xsrechnen,ysrechnen),Str(weg+1))
  EndIf
  
  

  EndIf
EndIf

    Next y
  Next x
  
  Next weg
  
  
  
  

  
  

  
  ;Weg suchen
  

    xsrechnen= xziel
  ysrechnen= yziel
  
  zaehler=1000
  
  
  Repeat
  
  For x =  xsrechnen-1 To xsrechnen+1
    For y = ysrechnen-1 To ysrechnen+1
  
    If wegdaten(x,y)<zaehler And wegdaten(x,y) <> 0
      zaehler= wegdaten(x,y)
      xneu=x
      yneu=y
      
      relativx=x-xsrechnen
      relativy=y-ysrechnen
      
      
  EndIf
  
    Next y
  Next x
  
  
  
  AddElement(mensch(1)\weg.w())

   ;1|2|3
   ;4|0|5
   ;6|7|8 
  
   If     relativx=-1 And relativy=-1 : mensch(1)\weg.w() = 1
   ElseIf relativx= 0 And relativy=-1 : mensch(1)\weg.w() = 2
   ElseIf relativx= 1 And relativy=-1 : mensch(1)\weg.w() = 3
   ElseIf relativx=-1 And relativy= 0 : mensch(1)\weg.w() = 4
   ElseIf relativx= 1 And relativy= 0 : mensch(1)\weg.w() = 5
   ElseIf relativx=-1 And relativy= 1 : mensch(1)\weg.w() = 6
   ElseIf relativx= 0 And relativy= 1 : mensch(1)\weg.w() = 7
   ElseIf relativx= 1 And relativy= 1 : mensch(1)\weg.w() = 8
   EndIf    
  
  xsrechnen=xneu
  ysrechnen=yneu
  
  SetGadgetAttribute(id(xsrechnen,ysrechnen),   #PB_Button_Image , ImageID(4))
  
  Until zaehler <=2
  
  
  
  
  Repeat
  event=WaitWindowEvent()
        
  
  
  If event = #PB_Event_Gadget
    
    For x = 1 To 20
      For y =1 To 20
        
        If EventGadget()=id(x,y)
          If startorstop=0
          
          
xstart= x
ystart= y
startorstop=1

Else

xziel= x
yziel= y
 
 startorstop=0
EndIf


 Goto neu

        EndIf
      Next y
    Next x
    
        
    
    
  EndIf
  

  
  Until event = #PB_Event_CloseWindow

Ich frage mich nun ob man sie nicht so optimieren kann, dass sie schneller funktioniert.
(mit einem 250*250 Feld dauert es ca. 5-10 s)
(wegfindung ist nach dem A* Algo. gemacht)

und warum sind alle wegfindungen auf diesem Forum so kompliziert, aber auch nach dem a*algo.?

http://forums.purebasic.com/german/view ... wegfindung

meine Informationen zum a*algo.:
http://de.wikipedia.org/wiki/A*

STARGÅTE · Beitrag von **STARGÅTE** » 04.05.2014 18:05

Purebasium hat geschrieben:und warum sind alle wegfindungen auf diesem Forum so kompliziert, aber auch nach dem a*algo.?

Weil sie dadurch vielleicht optimiert sind?

Purebasium hat geschrieben:mit einem 250*250 Feld dauert es ca. 5-10 s

Wie hast du das gemessen? Debugger An/aus? Wie viele Sackgasse, wie viele Blöcke?

Purebasium hat geschrieben:Ich frage mich nun ob man sie nicht so optimieren kann, dass sie schneller funktioniert.

Ich weiß jetzt nicht genau was du erwartest ...
Du bearbeitest ja gerade in jedem Suchdurchlauf immer alle Felder ab, obwohl du ja gerade am Anfang weiß, dass du nur in wenigen Felder suchen musst (um den Start).
Später weißt du dann, dass du auch wieder nur wenige Felder durchsuchen musst, da du das Ziel erreichst.
Wenn du natürlich immer alle 250*250 Felder mit jeder Iteration durchläufst, ist es klar das es langsam wird.

In dem geposteten Link wird doch genau erklärt, wie man es richtig macht (also die Verwaltung der Knoten).
Dein Code siehst zumindest nicht so aus, als ob er den Algorithmus nutzt, der auf deiner Wiki-Seite erklärt wird.

PureBoard

Wegfindung optimieren

Wegfindung optimieren

Re: Wegfindung optimieren