Pathfinding

Übersicht BlitzBasic Beginners-Corner

Neue Antwort erstellen

 

Phlox

Betreff: Pathfinding

 BeitragSo, Aug 31, 2008 15:25
Antworten mit Zitat
Benutzer-Profile anzeigen
Hi,

also ich versuche mich gerade an Pathfinding im 2D Bereich...
Ich greife nicht auf irgendeinen Algo zurück sondern versuche es auf meine eigene Art.
Zur Funktionsweise:
Es wird in allen Richtungen in allen Richtungen gesucht. Wenn ein Weg passt, wird er einem Typefeld
hinzugefügt. Der kürzeste Weg wird ausgesucht. Dies wird über einen (ich denke ziemlich langen) String an
die Funktion selbst zurückgegeben. Sie addiert einen zur länge hinzu und gibt es wieder zurück.
Dieser String enthält als Trennzeichen "|". Dies wird durch Chr(13) und Chr(10) ersetzt und in eine Datei geschrieben.
(damit man es einfacher auslesen kann...)
Hinterher sollen(ist noch nicht eingebaut) diese wie gesagt in ein Type aufgenommen werden.
Meine Frage:
Wieso beendet sich das Programm?
Es erscheint keine Datei!

Ich habe den Code aufgeteilt in Haupt- und Includefile:

include_path.bb Code: [AUSKLAPPEN]
Type pFeld
   Field x,y,state
End Type

Type ways
   Field length
   Field positions$[10000]
End Type

Global path_width,path_height
Const path_block=1,path_nothing=0,path_start=2,path_end=3



Function InitPathFinding(map_w,map_h)
   Local X,Y
   If map_w*map_h=0 Then Return 0
   path_width=map_w
   path_height=map_h
   
   For X=1 To map_w
      For Y=1 To map_h
         f.pFeld=New pFeld
         f\x=X
         f\y=Y
         f\state=0
      Next
   Next
   
   If state=0 Then Return 4 Else Return state
End Function



Function SetFieldState(x,y,state)
   state=Int(state)
   If state<0 Or state>3 Then Return 0
   For f.pFeld=Each pFeld
      If x=f\x And y=f\y Then f\state=state
   Next
   Return 1
End Function

Function FindPath()
   Local s_x,s_y,f_x,f_y
   For f.pFeld=Each pFeld
      If f\state=2 Then
         s_x=f\x
         s_y=f\y
      EndIf
      If f\state=3 Then
         f_x=f\x
         f_y=f\y
      EndIf
   Next
   ;RuntimeError f_x+""+f_y+""+s_x+""+s_y
   CheckAndGo(s_x,s_y,f_x,f_y)
End Function

Function CheckAndGo(sx,sy,fx,fy)
   Local check2$,file
   If sx=fx And sy=fy Then Return 1
   
   If sx>1 Then
      check2$=Check(sx-1,sy,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sy>1 Then
      check2$=Check(sx,sy-1,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sx<path_width
      check2$=Check(sx+1,sy,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sy<path_height
      check2$=Check(sx,sy+1,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   
   Return 0
End Function

Function Check$(x,y,fx,fy,he=0)
   Local check2$
   If x=fx And y=fy Then Return 1
   If sx>1 Then
      check2$=Check$(x-1,y,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If sy>1 Then
      check2$=Check$(x,y-1,fx,fy,he+1)
      If check2$<>"" Then
         Return (he+1)+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If sx<path_width
      check2$=Check$(x+1,y,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If sy<path_height
      check2$=Check$(x,y+1,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   Return ""
End Function


Und die Testdatei Code: [AUSKLAPPEN]
Graphics 800,600,32,2
AppTitle "2D Pathfinding"
SetBuffer BackBuffer()
Include "include_path.bb"


Const mw=10,mh=10
Local state,X,Y

InitPathFinding(mw,mh)

Restore mdata
For X=1 To mw
   For Y=1 To mh
      Read state
      SetFieldState(X,Y,state)
   Next
Next

.mdata
Data 1,1,1,1,1,1,1,1,1,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,0,2,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,0,0,0,0,0,0,3,0,1
Data 1,0,0,0,0,0,0,0,0,1
Data 1,1,1,1,1,1,1,1,1,1


t=CreateTimer(20)
FindPath()
While Not KeyDown(1)
   WaitTimer(t)
   
   ;DrawPath()
   
   Flip
   Cls
   
Wend
End


ich habe das so gelöst, damit ich es immer wieder benutzen kann.

Tia, MfG

SpionAtom

 BeitragSo, Aug 31, 2008 15:57
Antworten mit Zitat
Benutzer-Profile anzeigen
FindPath() Arrow CheckAndGo(s_x,s_y,f_x,f_y) Arrow check2$=Check(sx-1,sy,fx,fy) Arrow check2$=Check$(x-1,y,fx,fy,he+1)

Check ruft sich selber auf, ohne abzubrechen Arrow Overflow Idea
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
 

Phlox

 BeitragSo, Aug 31, 2008 16:03
Antworten mit Zitat
Benutzer-Profile anzeigen
Aber wenn ich diese Zeile einfüge, wird die Datei leer.


Code: [AUSKLAPPEN]
   If he>100 Then Return

SpionAtom

 BeitragSo, Aug 31, 2008 16:07
Antworten mit Zitat
Benutzer-Profile anzeigen
Also die einzige Abfrage, die ich vor dem Check-Aufruf sehe, ist:
Code: [AUSKLAPPEN]
If sx>1 Then

und sx wird nie verändert.
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080
 

Phlox

 BeitragSo, Aug 31, 2008 16:15
Antworten mit Zitat
Benutzer-Profile anzeigen
sx ist die Position des Startpunktes (X-Achse). Die soll auch nicht verändert werden.
Mir fällt gerade auf:
Stimmt. sx ist lokal....

und jetzt hängt es sich auf. Toll.

Include Datei
Code: [AUSKLAPPEN]
Type pFeld
   Field x,y,state
End Type

Type ways
   Field length
   Field positions$[10000]
End Type

Global path_width,path_height
Const path_block=1,path_nothing=0,path_start=2,path_end=3



Function InitPathFinding(map_w,map_h)
   Local X,Y
   If map_w*map_h=0 Then Return 0
   path_width=map_w
   path_height=map_h
   
   For X=1 To map_w
      For Y=1 To map_h
         f.pFeld=New pFeld
         f\x=X
         f\y=Y
         f\state=0
      Next
   Next
   
   If state=0 Then Return 4 Else Return state
End Function



Function SetFieldState(x,y,state)
   state=Int(state)
   If state<0 Or state>3 Then Return 0
   For f.pFeld=Each pFeld
      If x=f\x And y=f\y Then f\state=state
   Next
   Return 1
End Function

Function FindPath()
   Local s_x,s_y,f_x,f_y
   For f.pFeld=Each pFeld
      If f\state=2 Then
         s_x=f\x
         s_y=f\y
      EndIf
      If f\state=3 Then
         f_x=f\x
         f_y=f\y
      EndIf
   Next
   ;RuntimeError f_x+""+f_y+""+s_x+""+s_y
   CheckAndGo(s_x,s_y,f_x,f_y)
End Function

Function CheckAndGo(sx,sy,fx,fy)
   Local check2$,file
   If sx=fx And sy=fy Then Return 1
   
   If sx>1 Then
      check2$=Check(sx-1,sy,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sy>1 Then
      check2$=Check(sx,sy-1,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sx<path_width
      check2$=Check(sx+1,sy,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   If sy<path_height
      check2$=Check(sx,sy+1,fx,fy)
      file=WriteFile("temp.tmp")
      If file=0 Then Return 0
      WriteLine file,Replace(check2$,"|",Chr(13)+Chr(10))
      CloseFile file
      file=0
   EndIf
   
   
   Return 0
End Function

Function Check$(x,y,fx,fy,he=0)
   If he>800 Then Return
   Local check2$
   If x=fx And y=fy Then Return 1
   If x>1 Then
      check2$=Check$(x-1,y,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If y>1 Then
      check2$=Check$(x,y-1,fx,fy,he+1)
      If check2$<>"" Then
         Return (he+1)+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If x<path_width
      check2$=Check$(x+1,y,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   
   If y<path_height
      check2$=Check$(x,y+1,fx,fy,he+1)
      If check2$<>"" Then
         Return he+1+"|"+check2$+"|"+x+"|"+y
      EndIf
   EndIf
   Return ""
End Function

SpionAtom

 BeitragSo, Aug 31, 2008 19:01
Antworten mit Zitat
Benutzer-Profile anzeigen
Also wenn du folgendes in deine Checkmethode schreibst, merkt man, dass er da immer noch festhakt:
Code: [AUSKLAPPEN]
Function Check$(x,y,fx,fy,he=0)
   DebugLog "check " + x + "," + y + "," + fx + "," + fy + "," + he   
   Oval x * 5, y * 5, 5, 5


D.h. einer deiner Bedingungen, dass Check sich selber aufruft ist immer erfüllt. Wenn ich mir das inhaltlich anschauen würde, würde ich wohl irgendwann den Fehler finden, aber du sollst ja auch was zu tun haben Wink


Edit:
check2 ist von anfang an = "". Und wird nur was anderes, wenn es vorher schon was anderes ist.
Code: [AUSKLAPPEN]
If check2$<>"" Then

Diese Bedingung wird nie erfüllt.
os: Windows 10 Home cpu: Intel Core i7 6700K 4.00Ghz gpu: NVIDIA GeForce GTX 1080

Neue Antwort erstellen


Übersicht BlitzBasic Beginners-Corner

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group