Wegfindung optimieren

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

 

Rocys

Betreff: Wegfindung optimieren

 BeitragDo, Mai 29, 2008 21:59
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo,
ich habe eine kleine Wegfindungsroutine geschrieben. Sie findet zwar nicht den perfekten Weg, aber das ist auch gar nicht notwendig, solange sie nur ueberhaupt einen findet. Allerdings ist sie verhaelltnismaessig langsam. Sie muss nicht Echtzeitfaehig sein, aber sie wird im Laufe des Spiels EXTREM oft ausgefuehrt, also ist jede Millisekunde wertvoll. Hat irgendjemand Ideen, wie man sie beschleunigen koennte?
Code: [AUSKLAPPEN]

;konstanten fuers PAthfinding
Const DIR_stay=0,DIR_right=1,DIR_rightdown=5,DIR_down=2,DIR_leftdown=6,DIR_left=3,DIR_leftup=7,DIR_up=4,DIR_rightup=8

Type PF_next
   Field x
   Field y
   Field cost
End Type

Function pathfinding(char,targetx,targety)
   ;PF
   ;diese Funktion berechnet einen Pfad von der Position des Chars nach (targetx,targety)
   race.race=Object.race(char_Race(char))
   ;wenn der Char eh nicht das Ziel erreichen kann, wird null zurueckgegeben
    If Not (race\where=0 And (map(targetx,targety)=MAP_cave Or map(targetx,targety)=MAP_water)) Or (race\where=1 And map(targetx,targety)=MAP_cave) Or (race\where=2 And map(targetx,targety)=MAP_water) Then Return 0
   ;das Feld mit erledigten Tiles wird geloescht
   Dim path_map(CW_mapsize,CW_mapsize)
   PF_next.PF_next=New PF_next
      PF_next\x=char_x(char)
      PF_next\y=char_y(char)
      
   path_map(char_x(char),char_y(char))=-1
   kosten=0
   Repeat
      gefunden=0
      kein_weg=1
      For PF_next.PF_next=Each PF_next
         If PF_next<>Null Then
            kein_weg=0
            If gefunden=1 Then Delete PF_next
            If gefunden<>1 Then
               For dir=1 To 9
                  Select dir
                     Case DIR_right
                        x1=PF_next\x+1
                        y1=PF_next\y
                     Case DIR_rightdown
                        x1=PF_next\x+1
                        y1=PF_next\y+1
                     Case DIR_down
                        x1=PF_next\x
                        y1=PF_next\y+1
                     Case DIR_leftdown
                        x1=PF_next\x-1
                        y1=PF_next\y+1
                     Case DIR_left
                        x1=PF_next\x-1
                        y1=PF_next\y
                     Case DIR_leftup
                        x1=PF_next\x-1
                        y1=PF_next\y-1
                     Case DIR_up
                        x1=PF_next\x
                        y1=PF_next\y-1
                     Case DIR_rightup
                        x1=PF_next\x+1
                        y1=PF_next\y-1
                  End Select
                  If path_map(x1,y1)=0 Then
                      If (race\where=0 And (map(x1,y1)=MAP_cave Or map(x1,y1)=MAP_water)) Or (race\where=1 And map(x1,y1)=MAP_cave) Or (race\where=2 And map(x1,y1)=MAP_water) Then
                        neu.PF_next=New PF_next
                           neu\x=x1
                           neu\y=y1
                           neu\cost=PF_next\cost+1
                           path_map(x1,y1)=dir
                        If x1=targetx And y1=targety Then
                           gefunden=1
                           kosten=neu\cost
                        End If
                        If KeyDown(1) Then End
                     End If
                  End If
               Next
               Delete PF_next
            End If
         End If
      Next
   Until gefunden=1 Or kein_weg=1
   If gefunden=1 Then
      FreeBank char_path(char)
      char_path(char)=CreateBank(kosten+1)
      x=targetx
      y=targety
      pos=kosten+1
      Repeat
         pos=pos-1
         PokeByte char_path(char),pos,path_map(x,y)
         
         Select path_map(x,y)
            Case DIR_right
               x=x-1
            Case DIR_rightdown
               x=x-1
               y=y-1
            Case DIR_down
               y=y-1
            Case DIR_leftdown
               x=x+1
               y=y-1
            Case DIR_left
               x=x+1
            Case DIR_leftup
               x=x+1
               y=y+1
            Case DIR_up
               y=y+1
            Case DIR_rightup
               x=x-1
               y=y+1
         End Select
      Until x=char_x(char) And y=char_y(char)
   End If
   Return gefunden
End Function



Ich hoffe sie ist einigermassen verstaendlich. Wenn nicht, beantworte ich natuerlich gerne Fragen. Falls wider Erwarten jemandem diese Funktion gefaellt, darf er sie natuerlich verwenden.
Danke schon mal im Vorraus!
 

Matthias

 BeitragSo, Jun 01, 2008 16:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Hay.

Ein Pfadfinding so zwichendurch zu machen ist kein Problem.
Ein Extrem schnelles dagegen sehr.

Also. Mach ersteinmal ein Vernünftiges Beispiel.

Das mann sofort ausführen kann. Und wo auch die Zeit gemessen wird, die das Pfadfinding braucht.

Wenn du ein schnelles Pfadfinding willst dann lass die Types. Und benuze Dims.

Wenn du ein noch schnellesres Pfadfinding willst benutze nur eindimensionale Dim Felder.

Und wenn dies auch noch zu langsam ist dann verteile die Suche über mehrere Frams.

Und wenn du dann noch Bock hast, es noch schneller zu machen,
verringere die Dim Zugriffe. Durch ein Bittmap. Wobei ein Bitt für schon besucht bzw Hinderniss steht.


Natürlich brauchst du noch eine Vorauswahl. Alle zusammenhängenden Flächen ermitteln (Füllalgo) und nur wenn Start und Ende auf ein und der selben Fläche liegen, ist das Suchen sinvoll.

Das suchen ist aber nur dann sinvoll, wenn ein direkter Weg verspert ist.

Einen schnellen Pfadfinding zu entwickeln ist keine Sache von 2Tage es dauert mit unter Wochen.

Mfg Matthias.

Das ist zB mein Pfafinding. Es durchsucht ein 512x512 Map großes Map
in ca 8(+-3) ms bei 1,8 GHz

Bei meinen jetzigen 2x3 GHz dauert 10mal suchen 6ms.
Code: [AUSKLAPPEN]

Function ME_FindPfad(ME_BA,ME_SX,ME_SY,ME_EX,ME_EY,ME_G#)
   
   ME\PP[0]=(ME_SX Shl 9)+ME_SY:ME_E=ME_EX Shl 9+ME_EY
   If ME_G=>0 And ME_G<1 Then
 
      Repeat
         If BankSize(ME\FLBank[ME_GG])<300000 Then
            ME_H1=PeekByte(ME\FLBank[ME_GG],ME\PP[0])
            ME_H2=PeekByte(ME\FLBank[ME_GG],ME_E)
         Else
            ME_H1=PeekShort(ME\FLBank[ME_GG],ME\PP[0]*2)
            ME_H2=PeekShort(ME\FLBank[ME_GG],ME_E*2)
         End If:ME_GG=ME_GG+1
         If (ME_H1>0 And ME_H2>0) And ME_H1=ME_H2 Exit 
      Until ME_GG>10:ME_GG=ME_GG-1
      If ME_GG>Int(ME_G*10) Return:Else ME_G=ME_GG*.1
   End If

 
   ME_O=8500*Int(Abs(ME_G)*10):If ME_O>85000 ME_O=85000
   ME_1=ME\PP[0] Shr 5:ME_A=1 Shl (ME\PP[0]-(ME_1 Shl 5))
   If (ME\PMap[ME_O+ME_1] And ME_A)>0 Then Return
   ME_1=ME_E Shr 5:ME_A=1 Shl (ME_E-(ME_1 Shl 5))
   If (ME\PMap[ME_O+ME_1] And ME_A)>0 Then Return
   Local ME_M[8500],ME_PX[9000],ME_PY[9000],ME_I=1,ME_Z=0
   For ME_N=0 To 8499:ME_M[ME_N]=ME\PMap[ME_O+ME_N]:Next
   
   While ME_Z<ME_I:ME_Q=ME\PP[ME_Z]:ME_1=ME_Q Shr 5
      ME_A=1Shl (ME_Q-(ME_1 Shl 5)):If ME_Q=ME_E ME_OK=1Exit
      ME_2=(ME_Q-1) Shr 5:ME_B=1 Shl ((ME_Q-1)-(ME_2 Shl 5))
      ME_3=(ME_Q+1) Shr 5:ME_C=1 Shl ((ME_Q+1)-(ME_3 Shl 5))
      Select (ME_M[ME_2]And ME_B)Case 0ME_M[ME_2]=ME_M[ME_2]Or ME_B
      ME\PA[ME_I]=ME_Z:ME\PP[ME_I]=ME_Q-1:ME_I=ME_I+1:End Select
      Select (ME_M[ME_3]And ME_C)Case 0ME_M[ME_3]=ME_M[ME_3]Or ME_B
      ME\PA[ME_I]=ME_Z:ME\PP[ME_I]=ME_Q+1:ME_I=ME_I+1:End Select
      Select (ME_M[ME_1-16] And ME_A):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q-512ME_M[ME_1-16]=ME_M[ME_1-16]Or ME_A:End Select
      Select (ME_M[ME_1+16] And ME_A):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q+512ME_M[ME_1+16]=ME_M[ME_1+16]Or ME_A:End Select
      Select (ME_M[ME_3-16] And ME_C):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q-511ME_M[ME_3-16]=ME_M[ME_3-16]Or ME_C:End Select
      Select (ME_M[ME_2+16] And ME_B):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q+511ME_M[ME_2+16]=ME_M[ME_2+16]Or ME_B:End Select
      Select (ME_M[ME_3+16] And ME_C):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q+513ME_M[ME_3+16]=ME_M[ME_3+16]Or ME_C:End Select
      Select (ME_M[ME_2-16] And ME_B) Case 0:ME\PA[ME_I]=ME_Z ME_I=ME_I+1
      ME\PP[ME_I-1]=ME_Q-513ME_M[ME_2-16]=ME_M[ME_2-16]Or ME_B:End Select
      ME_Z=ME_Z+1
   Wend
     

   ME_N=ME_Z:If ME_OK=0 Then Return:Else ResizeBank(ME_BA,4)
  Repeat:ME_D=ME\PA[ME_Z]:ME_Z=ME_D:ME_PSt=ME_PSt+1:Until ME_Z=0
   ME_Z=ME_N:ME_SS=ME_PSt-1:Repeat:ME_D=ME\PA[ME_Z]:ME_P=ME\PP[ME_D]
   ME_X=ME_P Shr 9:ME_PX[ME_SS]=ME_X:ME_PY[ME_SS]=ME_P-ME_X Shl 9
   ME_SS=ME_SS-1:ME_Z=ME_D:Until ME_Z=0:ME_I=0:ME_J=0

   While ME_J<ME_PSt:ME_X1=ME_PX[ME_J]:ME_Y1=ME_PY[ME_J]:ME_J=ME_J+1
      ME_DX=ME_X2-ME_X1:ME_X2=ME_PX[ME_I]:ME_Y2=ME_PY[ME_I]:ME_S=1
      ME_IX=(ME_DX>0)-(ME_DX<0):ME_DX=Abs(ME_DX):ME_DY=ME_Y2-ME_Y1
      ME_IY=(ME_DY>0)-(ME_DY<0):ME_DY=Abs(ME_DY)

      Select ME_DY>ME_DX
      Case 0:ME_ER=-ME_DX:ME_DE=ME_DY Shl 1:ME_SC=ME_ER Shl 1
         While ME_X1<>ME_X2:ME_Q=(ME_X1 Shl 9)+ME_Y1:ME_X1=ME_X1+ME_IX
            ME_1=ME_Q Shr 5ME_ER=ME_ER+ME_DE:ME_QA=1Shl(ME_Q-ME_1 Shl 5)
            Select (ME\PMap[ME_O+ME_1] And ME_QA)>0 Case 1 ME_S=0 Exit
            End Select:If ME_ER>0 ME_Y1=ME_Y1+ME_IY:ME_ER=ME_ER+ME_SC
         Wend
   
      Case 1:ME_ER=-ME_DY:ME_DE=ME_DX Shl 1:ME_SC=ME_ER Shl 1
         While ME_Y1<>ME_Y2:ME_Q=(ME_X1 Shl 9)+ME_Y1:ME_Y1=ME_Y1+ME_IY
            ME_1=ME_Q Shr 5ME_ER=ME_ER+ME_DE:ME_QA=1Shl(ME_Q-ME_1 Shl 5)
            Select (ME\PMap[ME_O+ME_1] And ME_QA)>0:Case 1:ME_S=0:Exit
            End Select:If ME_ER>0 ME_X1=ME_X1+ME_IX:ME_ER=ME_ER+ME_SC
         Wend
      End Select
      If ME_S=0 Or ME_J=ME_PSt Then
         ME_BS=BankSize(ME_BA):ResizeBank(ME_BA,ME_BS+4)
         PokeShort(ME_BA,ME_BS+2,ME_PY[ME_J])
         PokeShort(ME_BA,ME_BS,ME_PX[ME_J]):ME_I=ME_J
      End If
   Wend:PokeShort(ME_BA,ME_BS,ME_EX):PokeShort(ME_BA,ME_BS+2,ME_EY)   
   PokeShort(ME_BA,0,ME_SX):PokeShort(ME_BA,2,ME_SY):Return 1
End Function

Noobody

 BeitragSo, Jun 01, 2008 17:27
Antworten mit Zitat
Benutzer-Profile anzeigen
Eigentlich sollte die Suchgeschwindigkeit eines A* - Algos nicht von der Grösse der Map abhängen.
Meiner bringt 0 Ms bei einer Map von 2048x2048 zustande - aber nur, wenn Start- und Endpunkt nahe beieinander liegen.

Meiner Ansicht nach ist es meist viel lohnender, den Gebrauch der Wegfindung zu senken, als unbedingt noch die letzte halbe Millisekunde im Code zu optimieren.
Wenn es beispielsweise darum geht, ein sich bewegendes Objekt zu verfolgen, ist es klüger, das Pathfinding einmal durchzuführen und von da an die Bewegungen des zu verfolgenden Objekts zum aktuellen Pfad hinzuzufügen.
Ich möchte dir darum empfehlen, jeden Gebrauch des Pathfinding nochmals gut zu überdenken - es ist einfach ein rechenintensiver Algorithmus, und meist lässt es sich auch anders lösen.

@Matthias: Eine Bank ist niemals so schnell wie ein Array.
Deine Methode senkt zwar den Speicherverbrauch um ein vielfaches, jedoch sind Bankzugriffe in der Regel 1.3 mal langsamer als ein Zugriff auf ein Array - zumal du auch die Bytes in einzelne Bits umwandeln musst (was durch Bitweise Operanden wie Shr hier nicht gross ins Gewicht fällt).
Auch verstehe ich nicht, was dir solche Select - Case Anweisungen bringen, wenn dich doch sowieso nur ein Fall interessiert?
Code: [AUSKLAPPEN]
 Select (ME_M[ME_1+16] And ME_A):Case 0:ME\PA[ME_I]=ME_Z:ME_I=ME_I+1 ME\PP[ME_I-1]=ME_Q+512ME_M[ME_1+16]=ME_M[ME_1+16]Or ME_A:End Select


Auch entgegen deiner wahrscheinlichen Meinung wird ein Code nicht schneller, wenn er unübersichtlicher wird Wink
Verzichte doch auf ':', da sie die Leserlichkeit des Codes unglaublich erschweren, und gib deinen Namen aussagekräftige Namen.
Man is the best computer we can put aboard a spacecraft ... and the only one that can be mass produced with unskilled labor. -- Wernher von Braun
 

Rocys

 BeitragSo, Jun 01, 2008 18:53
Antworten mit Zitat
Benutzer-Profile anzeigen
okay, erstmal vielen Dank.
Die Idee mit den bewegenden Objekten ist offentsichtlich, aber trotzdem bin ich nicht draufgekommen. naja.
Hab mal nen kleinen Speedtest geschrieben, und Arrays sind ja wirklich schneller als Banks, wer haette das gedacht?
Jetzt muss ich mal raetseln, wie ich die Types durch Arrays oder Banks (da haette ich ne Idee, bei Arrays noch nicht) ersetzen kann.
Die Idee mit dem Fuellalgo werde ich wohl auch noch versuchen umzusetzen. Koennte nochmal einiges an Zeit sparen genauso wie die Suche nach dem direkten Weg.(Das meintest du wohl im Sinne von
Code: [AUSKLAPPEN]

if char_x(char)=targetx or char_y(char)=targety then ueberpruefe_direkten_Weg
, oder?)
Aber programmiertechnische Fettnaepfchen ala bildinschleifeladen habt ihr keine entdeckt?

@Matthias
Vielen Dank fuer den Code, aber bevor ich mich da durch gekaempft habe, kann ich glaube ich meine Routine eher selbst optimieren. Trotzdem Danke schoen.

p.s.
so langsam ist meine Routine wohl gar nicht. Fuer strecken von ca 50 Tiles (also der gefundene Weg, nicht Luftlinie) braucht sie ca. 10-15 ms bei 1ghz.
 

Matthias

 BeitragSo, Jun 01, 2008 18:57
Antworten mit Zitat
Benutzer-Profile anzeigen
@Noobody.

Du hast sogar Recht. Banken sind zwar schneller als Types aber langsamer als Dims.

Anfangs wird nur geprüft ob der Start und das Ziel auf ein und der selben Fläche liegen. Und diese daten sind in einer Bank gespeichert.
Also 2Zugriffe. Das ist keine Problem.

Ich habe Banken genommen da Banken sparsammer sind.

Den es gibt nicht nur ein Map sondernt 10Maps. Gestaffelt nach Terrainhöhenunterschied.

Wäre es im Dim Feld wären es 10MB. Allerdings so sinds nur 3MB

Das Tatsächliche Pfadfinding liest die daten aus dem ME_M Arrea das Anfangs ersteinmal übertragen werden muß.

Später wird dann noch der Pfad geglättet. Nur das Ergebniss wird letzendlich in die PfadBank( ME_BA) die am Anfang an die Function übergeben wurde übertragen.

Da Banken für Unit Typen Ideal sind.

Das mit Select Case ist ganz einfach. Die Zeile wäre mir einfach zu lang mit IF

Und es ist natürlich selbstverständlich, das um so näher das Ziel vom Start entfernt ist, der Algo natürlich schneller ist. Ich habe jetzt mal den Extremfall beschrieben. Start 50,50 Ende 480,480

Bei mir braucht der A*Algo (50,50)-(480,480) 1,8 GHz 4800ms.

Der Algo ist nicht dafür gedacht Objeckte zu verfolgen sondernt die Einheiten in die nähe zu bringen.

Bei Verfolgung soltet mann das Ziel mit LinePick Picken und nur dann wenn es sichtbar ist, den Zielpunkt aktualiesieren. Natürlich wäre es Selbstmord andauernt zu Picken. Es reicht wenn es alle 2000ms geschied.

Und auch nicht alle Objekte bzw Ziele nur das was am nästen drann ist.

Edit:
Laughing Es solte nur ein Beispiel sein wie soetwas aussehen könnte.
Das hier ist die 6te Version aus meinen Pfadfinding Ordner. Von 72.

user posted image[/code]

Code: [AUSKLAPPEN]

Graphics 800,600,32,2
Global MapImage=LoadImage("Map.png")
Global StartX=50,StartY=50
Global EndeX=400,EndeY=400
Global PfadSt
Dim XS(100000),YS(100000),WW(1000000)
Dim Map(520,520),PfadX(10000),PfadY(10000)
Dim CMap(520,520)
LoadMap()

SetBuffer BackBuffer()
Ak=1
Repeat:


DrawBlock MapImage,0,0
Color 255,255,255:Oval StartX-5,StartY-5,10,10
Color 255,255,0:Oval EndeX-5,EndeY-5,10,10
If MouseDown(1)=1 Then StartX=MouseX():StartY=MouseY():AK=1
If MouseDown(2)=1 Then EndeX=MouseX():EndeY=MouseY():AK=1
 
If Ak=1 Then
Zeit=MilliSecs()
;For I=0 To 19
FINDEWEG()
;Next


Zeit=MilliSecs()-Zeit
End If
LockBuffer
For I=0 To PfadSt-1
WritePixelFast(PfadX(I)*2,PfadY(I)*2,$FFFF00)

Next
UnlockBuffer
Text 10,10,Zeit

Flip
Until KeyDown(1)=1
End





Function FINDEWEG()
For ZX=0 To 255:For ZY=0 To 255
CMap(ZX,ZY)=Map(ZX,ZY)
Next:Next


MapG=250
XS(0)=StartX/2:YS(0)=StartY/2
EnX=EndeX/2:EnY=EndeY/2:I=1

For Z=0 To I-1
X1=XS(Z):Y1=YS(Z):If X1=EnX And Y1=EnY Then OK=1:Exit


X=X1-1:Y=Y1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1+1:Y=Y1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1:Y=Y1-1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1:Y=Y1+1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
 
X=X1-1:Y=Y1-1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1-1:Y=Y1+1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1+1:Y=Y1-1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1
X=X1+1:Y=Y1+1 If CMap(X,Y)=0 WW(I)=Z:XS(I)=X:YS(I)=Y:CMap(X,Y)=2:I=I+1

Next

Select OK:Case 1
PfadSt=0

Repeat:D=WW(Z)

PfadX(PfadSt)=XS(D):PfadY(PfadSt)=YS(D):PfadSt=PfadSt+1


Z=D:Until Z=0
End Select
Select OK:Case 1:AppTitle "ZielGefunden":Default:AppTitle "nichtGefunden":End Select



End Function








Function LoadMap()

Buff=ImageBuffer(MapImage)
LockBuffer Buff:WS=ReadPixelFast(0,0,Buff)

For ZX=0 To 255:For ZY=0 To 255
If ReadPixelFast(ZX*2,ZY*2,Buff)<>WS Then Map(ZX,ZY)=1
If ZX<2 Or ZY<2 Or ZX>253 Or ZY>253 Then Map(ZX,ZY)=1
Next:Next
UnlockBuffer Buff
End Function

Er ist natürlich lange nicht so schnell, aber schon recht gut.

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group