Pathfinding
Übersicht
BlitzBasic Allgemein
|
ToeBBetreff: Pathfinding |
 Do, Jun 26, 2008 21:37Antworten mit Zitat 
|
|---|---|---|
|
Ich wollt für mein Aktuelles Project Smiley War einen Versich starten, eine KI zu bauen. Dafür brauche ich unter anderem Pathfindig. Ich wollte das so machen, das der Gegner (Array) eine Bestimmt Waypoint strecke hat (Type) die er ablaüft . Aber wie geht das ? Ich hab mal was von Weg-kosten gehört... Geht das auch ohne Waypoints ?
Hier die Map : Code: [AUSKLAPPEN] Graphics 800,600,16,2
SetBuffer BackBuffer() Const p_anz = 5 Dim x(p_anz),y(p_anz) Dim Map(49,49) For i = 2 To p_anz x(i) = 10 y(i) = 10 Next LoadMap("Monsterhölle.map") Repeat For xx = 0 To 49 For yy = 0 To 49 If Map(xx,yy) Then Color 255,255,255:Rect xx*10,yy*10,10,10 ;Color 0,0,0:Rect xx*10,yy*10,10,10,0 EndIf Next Next Color 0,255,0 For i = 2 To p_anz Oval x(i),y(i),10,10 Next Flip Cls Until KeyHit(1) End Function LoadMap(Name$) Dat = ReadFile(Name$) If dat <> 0 For yy = 0 To 49 For xx = 0 To 49 map(xx,yy) = ReadByte(dat) Next Next CloseFile dat EndIf End Function Wenn es geht könnt ihr mir bitte keinen fertigen code einreichen, die versteh ich sowie so nicht (wenn dann bitte mit ausfühlicher erkläreung) ... mfg ToeB |
||
|
CasiopayaBetreff: Re: Pathfinding |
Fr, Jun 27, 2008 0:46 Antworten mit Zitat
|
|---|---|---|
|
ToeB hat Folgendes geschrieben: eine KI zu bauen.
KI heist "Künstliche Intelligenz" 
ToeB hat Folgendes geschrieben: Ich wollte das so machen, das der Gegner (Array) eine Bestimmt Waypoint strecke hat (Type) die er ablaüft . Aber wie geht das ? Ich hab mal was von Weg-kosten gehört... Geht das auch ohne Waypoints ?
Hmm, ja also das hängt von deiner Architektur ab. Der Begriff "Waypoints" wird meist dann verwendet, wenn Computer-Gegner sich nicht völlig frei im möglichen Raum aller Positionen bewegen können, sondern nur entlang fester Wege zwischen bestimmten, festen Punkten. Der zu wählende Pfad ist dann der, der einen Bot in kürzester Zeit von seinem Start A zu seinem Ziel B bringt. (Kosten bedeutet meist Dauer und damit Wegstrecke.) WIE nun dieser Weg berechnet wird hat aber weniger damit zu tun, wie der Weg dargestellt wird. Beschreib mal so genau wie möglich, was deine "Wege" sind und was die "KI" so können soll. |
||
- Zuletzt bearbeitet von Casiopaya am Fr, Jun 27, 2008 8:47, insgesamt einmal bearbeitet
|
Noobody |
Fr, Jun 27, 2008 7:50 Antworten mit Zitat
|
|---|---|---|
|
Was du suchst, ist vermutlich A*.
Der Algorithmus ist nicht allzuschwer, gute Tutorials findest du überall im Internet, wie zum Beispiel dieses hier. Im Codearchiv gibt es auch jede Menge davon, aber am besten ist es doch, wenn man es selber schreibt. |
||
| 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 | ||
|
|
ToeB |
Fr, Jun 27, 2008 11:23 Antworten mit Zitat
|
|---|---|---|
|
@Noobody : Danke für das Tut !
Aber warum funzt das nicht bzw. was mache ich falsch ? Code: [AUSKLAPPEN] Function GetPath(sx,sy,zx,zy)
Local ak_x=1,ak_y=1 Local feld[8] Local Avail = 0 Local Weg[8] Local sch = 0 While Not Avail feld[1] = Map(ak_x-1,ak_y-1) > 0 feld[2] = Map(ak_x+1,ak_y+1) > 0 feld[3] = Map(ak_x+1,ak_y-1) > 0 feld[4] = Map(ak_x-1,ak_y+1) > 0 feld[5] = Map(ak_x,ak_y-1) > 0 feld[6] = Map(ak_x,ak_y+1) > 0 feld[7] = Map(ak_x-1,ak_y) > 0 feld[8] = Map(ak_x+1,ak_y) > 0 For i = 1 To 8 If feld[i] If i => 1 And i <= 4 Then WEG_ = 14 Else WEG_ = 10 WEG_X = Abs(ak_x-zx) WEG_Y = Abs(ak_y-zy) WEG_2 =(WEG_X+WEG_Y)*10 Weg[i] = WEG_ + WEG_2 EndIf Next For i = 1 To 8 For j = 1 To 8 If WEG[i] < WEG[j] Then Select i Case 1 ox = - 1 oy = - 1 Case 2 ox = + 1 oy = + 1 Case 3 ox = + 1 oy = - 1 Case 4 ox = - 1 oy = + 1 Case 5 ox = 0 oy = - 1 Case 6 ox = 0 oy = + 1 Case 7 ox = - 1 oy = 0 Case 8 ox = + 1 oy = 0 End Select EndIf Next Next ak_x = ak_x + ox ak_y = ak_y + oy wp.wp = New wp wp\x = ak_x*10 wp\y = ak_y*10 If ak_x = zx And ak_y = zy Avail = True sch = sch + 1 DebugLog "" DebugLog sch DebugLog ak_x DebugLog ak_y Wend End Function Iwie geht ak_x und ak_y die ganze zeit hoch... die schleife hört einfach nicht auf... mfg ToeB |
||
|
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt! |
||
|
|
Noobody |
Fr, Jun 27, 2008 17:33 Antworten mit Zitat
|
|---|---|---|
|
Auch wenn ich nicht ganz verstehe, was du mit dem Code erreichen willst, so sehe ich zumindest nirgends eine Einbindung von den Startkoordinaten....
Hier eine kleine Implementation mit Types (mithilfe der Kommentare solltest du es schon verstehen): Code: [AUSKLAPPEN] Graphics 800, 600, 0, 2
SetBuffer BackBuffer() Type Waynode Field X ; X - Position in Tilekoordinaten Field Y ; Y - Position in Tilekoordinaten Field GCost ; Die bisherigen Wegkosten, angegeben in Anzahl Tiles, die bis zu diesem Wegpunkt durchquert werden mussten Field HCost# ; Die geschätzten Wegkosten bis zum Ziel, angegeben in Tiles und ausgerechnet mit Pythagoras Field Parent.ClosedList ; Der vorherige Wegpunkt aus der Closedlist End Type Type ClosedList Field X ; X - Position in Tilekoordinaten Field Y ; Y - Position in Tilekoordinaten Field Parent.ClosedList ; Der vorherige Wegpunkt aus der Closedlist End Type Global MapsizeX = 100 ; Die Kartengrösse festlegen Global MapsizeY = 100 Global StartX = 10 ; Die Startkoordinaten festlegen Global StartY = 10 Dim MapData( MapsizeX - 1, MapsizeY - 1 ) ; Array Dimensionieren (stellt die Karte dar) For i = 0 To MapsizeX - 1 For t = 0 To MapsizeY - 1 MapData( i, t ) = ( Rand( 0, 2 ) = 2 ) ; Die Karte zufällig mit Werten befüllen (der Term in Klammern dient dazu, dass mehr Next ; freie Felder als blockierte Felder vorhanden sind) Next Timer = CreateTimer( 60 ) ; Die Framebegrenzung, damit wir hier nicht überflüssig Leistung verpulvern While Not KeyHit( 1 ) ; Hauptschleife Cls Color 255, 255, 255 For i = 0 To MapsizeX - 1 For t = 0 To MapsizeY - 1 Rect i*10, MapsizeY*10 - t*10, 10, 10, MapData( i, t ) ; Die Karte zeichnen Next Next EndX = MouseX()/10 EndY = MouseY()/10 If EndX >= 0 And EndX < MapsizeX Then If EndY >= 0 And EndY < MapsizeY Then ; Schauen, ob die Maus noch auf der Karte ist - was anderes hat der Algo nicht gerne. Counter = MilliSecs() Path$ = FindPath$( StartX, StartY, EndX, EndY ) ; Der eigentliche Algo Elapsed = MilliSecs() - Counter ; Die benötigte Berechnungszeit für den Pfad berechnen (ist nötig, da das Zeichnen der Karte ; viel mehr Leistung zieht als der Algo selbst) EndIf EndIf If MouseHit( 2 ) Then StartX = MouseX()/10 StartY = MouseY()/10 ; Bei Mausklick neue Startkoordinaten setzen EndIf Color 255, 0, 0 Rect StartX*10, StartY*10, 10, 10, 1 ; Das Startrechteck zeichnen CurrentX = StartX CurrentY = StartY For i = 1 To Len( Path$ ) Select Mid( Path$, i, 1 ) Case "1" CurrentX = CurrentX - 1 Case "2" CurrentY = CurrentY - 1 Case "3" CurrentX = CurrentX + 1 Case "4" CurrentY = CurrentY + 1 End Select Rect CurrentX*10, CurrentY*10, 10, 10 ; Den ganzen Pfad zeichnen - der Pfad liegt als String vor, '1' bedeutet links, '2' ; oben, '3' rechts und '4' unten. Next Text 0, 0, Elapsed + " : " + Len( Path$ ) ; Die Berechnungszeit zusammen mit der Pfadlänge anzeigen lassen Flip 0 WaitTimer Timer ; Buffer austauschen und dem System Erholungszeit gönnen Wend End Function FindPath$( X2, Y2, X1, Y1 ) Indexed = CreateBank( MapsizeX*MapsizeY ) ; Eine Bank erstellen, um bereits berechnete Felder einzutragen Start.Waynode = New Waynode ; Den ersten Wegpunkt erstellen, dies ist unser Startpunkt Start\X = X1 Start\Y = Y1 PokeByte Indexed, X1*MapsizeY + Y1, True ; In der Bank eintragen, dass der Startpunkt bereits betrachtet wurde Repeat Shortest.Waynode = First Waynode ; Den ersten Wegpunkt als kürzesten eintragen ; Nun gehen wir alle bereits betrachteten Wegpunkte durch. Sind die Kosten, um zu diesem Punkt zu gelangen ; plus die abgeschätzten Kosten bis zum Ziel kleiner als die des vermeintlich am nächsten zum Ziel ; liegenden Punktes, so wird der aktuelle Punkt in 'Shortest' eingetragen und der Vergleich geht mit dem ; nächsten Wegpunkt weiter. So erhalten wir am Ende den Punkt, der vermutlich am nächsten am Ziel liegt. For Node.Waynode = Each Waynode If ( Node\GCost + Node\HCost# ) < ( Shortest\GCost + Shortest\HCost# ) Then Shortest = Node Next Node.Waynode = Shortest ; Den am nächsten zum Ziel liegenden Punkt für die folgenden Berechnungen in 'Node' ablegen. If Node = Null Then Return "" ; Gibt es keinen Punkt mehr, der betrachtet werden könnte, gibt es keine Verbindung zum Ziel. Closed.ClosedList = New ClosedList Closed\X = Node\X Closed\Y = Node\Y Closed\Parent = Node\Parent ; Nun legen wir den Punkt in der Closedlist ab. Er ist fertig betrachtet. If Node\X - 1 >= 0 Then StateLeft = PeekByte( Indexed, ( Node\X - 1 )*MapsizeY + Node\Y ) Else StateLeft = 1 If Node\X + 1 < MapsizeX Then StateRight = PeekByte( Indexed, ( Node\X + 1 )*MapsizeY + Node\Y ) Else StateRight = 1 If Node\Y + 1 < MapsizeY Then StateBottom = PeekByte( Indexed, Node\X*MapsizeY + Node\Y + 1 ) Else StateBottom = 1 If Node\Y - 1 >= 0 Then StateTop = PeekByte( Indexed, Node\X*MapsizeY + Node\Y - 1 ) Else StateTop = 1 ; Wenn die benachbarten Punkte noch auf der Karte liegen und nicht bereits betrachtet wurden, so ist der entsprechende ; Wert auf 0, ansonsten auf 1. If Not StateLeft Then ; Wenn der Punkt gültig ist, wird er betrachtet If MapData( Node\X - 1, MapsizeY - Node\Y ) = 0 Then ; Ist sein Feld nicht blockiert, legen wir einen neuen Wegpunkt an. Newbie.Waynode = New Waynode Newbie\X = Node\X - 1 ; Seine Koordinaten sind benachbart zum vorherigen Feld Newbie\Y = Node\Y Newbie\GCost = Node\GCost + 1 ; Die Wegkosten bis zum Wegpunkt sind um eins höher als zum vorherigen ; Wegpunkt, da wir um ein Tile nach rechts/links/oben/unten mussten. Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) ; Die Wegkosten zum Ziel abschätzen (per Pythagoras) Newbie\Parent = Closed ; Den vorherigen Wegpunkt eintragen PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True ; In der Bank eintragen, dass der Punkt bereits ; betrachtet wurde. EndIf EndIf ; Die restlichen Betrachtungen sind analog zur ersten - nur für andere Felder (oben/unten/rechts) If Not StateRight Then If MapData( Node\X + 1, MapsizeY - Node\Y ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X + 1 Newbie\Y = Node\Y Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Not StateTop Then If MapData( Node\X, MapsizeY - Node\Y + 1 ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X Newbie\Y = Node\Y - 1 Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Not StateBottom Then If MapData( Node\X, MapsizeY - Node\Y - 1 ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X Newbie\Y = Node\Y + 1 Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Node\X = X2 And Node\Y = Y2 Then ; Sind wir am Ziel angelangt? Delete Each Waynode ; Alle Wegpunkte löschen - die brauchen wir jetzt nicht mehr. Path$ = "" Closed.ClosedList = Last ClosedList ; Den letzten betrachteten Punkt holen While Closed\Parent <> Null ; Bis wir am Startpunkt angelangt sind (der hat ja keinen vorherigen Wegpunkt). Der Startpunkt ; wird vor der Wegberechnung definiert (ein wenig hochscrollen) Select Closed\X - Closed\Parent\X ; Differenz der Koordinaten auf der X - Achse Case 1 Path$ = Path$ + "1" Case -1 Path$ = Path$ + "3" Case 0 Select Closed\Y - Closed\Parent\Y ; ...und der Y - Achse Case 1 Path$ = Path$ + "2" Case -1 Path$ = Path$ + "4" End Select End Select Closed = Closed\Parent ; Den vorherigen Wegpunkt betrachten Wend Delete Each ClosedList ; Die Closedlist brauchen wir auch nicht mehr FreeBank Indexed ; Genausowenig die Bank Return Path$ ; Nun den Pfad zurückgeben EndIf Delete Node ; Wenn wir nicht am Ziel sind, dann den Wegpunkt löschen. Er ist fertig betrachtet und in der Closedlist. Forever End Function |
||
| 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 | ||
|
|
ToeB |
Fr, Jun 27, 2008 19:06 Antworten mit Zitat
|
|---|---|---|
|
Hey cool danke ! Aber geht das auch so, das die Map richtigrum geprüft wird ? Die Steht immer auf dem Kopf...
mfg ToeB |
||
|
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt! |
||
|
|
Noobody |
Fr, Jun 27, 2008 23:27 Antworten mit Zitat
|
|---|---|---|
Upps, da hatte ich tatsächlich noch ein Überbleibsel aus älterer Zeit drin 
Korrigierter Code: [AUSKLAPPEN] Graphics 800, 600, 0, 2
SetBuffer BackBuffer() Type Waynode Field X ; X - Position in Tilekoordinaten Field Y ; Y - Position in Tilekoordinaten Field GCost ; Die bisherigen Wegkosten, angegeben in Anzahl Tiles, die bis zu diesem Wegpunkt durchquert werden mussten Field HCost# ; Die geschätzten Wegkosten bis zum Ziel, angegeben in Tiles und ausgerechnet mit Pythagoras Field Parent.ClosedList ; Der vorherige Wegpunkt aus der Closedlist End Type Type ClosedList Field X ; X - Position in Tilekoordinaten Field Y ; Y - Position in Tilekoordinaten Field Parent.ClosedList ; Der vorherige Wegpunkt aus der Closedlist End Type Global MapsizeX = 20 ; Die Kartengrösse festlegen Global MapsizeY = 20 Global StartX = 10 ; Die Startkoordinaten festlegen Global StartY = 10 Dim MapData( MapsizeX - 1, MapsizeY - 1 ) ; Array Dimensionieren (stellt die Karte dar) For i = 0 To MapsizeX - 1 For t = 0 To MapsizeY - 1 MapData( i, t ) = ( Rand( 0, 2 ) = 2 ) ; Die Karte zufällig mit Werten befüllen (der Term in Klammern dient dazu, dass mehr Next ; freie Felder als blockierte Felder vorhanden sind) Next Timer = CreateTimer( 60 ) ; Die Framebegrenzung, damit wir hier nicht überflüssig Leistung verpulvern While Not KeyHit( 1 ) ; Hauptschleife Cls Color 255, 255, 255 For i = 0 To MapsizeX - 1 For t = 0 To MapsizeY - 1 Rect i*10, t*10, 10, 10, MapData( i, t ) ; Die Karte zeichnen Next Next EndX = MouseX()/10 EndY = MouseY()/10 If EndX >= 0 And EndX < MapsizeX Then If EndY >= 0 And EndY < MapsizeY Then ; Schauen, ob die Maus noch auf der Karte ist - was anderes hat der Algo nicht gerne. Counter = MilliSecs() Path$ = FindPath$( StartX, StartY, EndX, EndY ) ; Der eigentliche Algo Elapsed = MilliSecs() - Counter ; Die benötigte Berechnungszeit für den Pfad berechnen (ist nötig, da das Zeichnen der Karte ; viel mehr Leistung zieht als der Algo selbst) EndIf EndIf If MouseHit( 2 ) Then StartX = MouseX()/10 StartY = MouseY()/10 ; Bei Mausklick neue Startkoordinaten setzen EndIf Color 255, 0, 0 Rect StartX*10, StartY*10, 10, 10, 1 ; Das Startrechteck zeichnen CurrentX = StartX CurrentY = StartY For i = 1 To Len( Path$ ) Select Mid( Path$, i, 1 ) Case "1" CurrentX = CurrentX - 1 Case "2" CurrentY = CurrentY - 1 Case "3" CurrentX = CurrentX + 1 Case "4" CurrentY = CurrentY + 1 End Select Rect CurrentX*10, CurrentY*10, 10, 10 ; Den ganzen Pfad zeichnen - der Pfad liegt als String vor, '1' bedeutet links, '2' ; oben, '3' rechts und '4' unten. Next Text 0, 0, Elapsed + " : " + Len( Path$ ) ; Die Berechnungszeit zusammen mit der Pfadlänge anzeigen lassen Flip 0 WaitTimer Timer ; Buffer austauschen und dem System Erholungszeit gönnen Wend End Function FindPath$( X2, Y2, X1, Y1 ) Indexed = CreateBank( MapsizeX*MapsizeY ) ; Eine Bank erstellen, um bereits berechnete Felder einzutragen Start.Waynode = New Waynode ; Den ersten Wegpunkt erstellen, dies ist unser Startpunkt Start\X = X1 Start\Y = Y1 PokeByte Indexed, X1*MapsizeY + Y1, True ; In der Bank eintragen, dass der Startpunkt bereits betrachtet wurde Repeat Shortest.Waynode = First Waynode ; Den ersten Wegpunkt als kürzesten eintragen ; Nun gehen wir alle bereits betrachteten Wegpunkte durch. Sind die Kosten, um zu diesem Punkt zu gelangen ; plus die abgeschätzten Kosten bis zum Ziel kleiner als die des vermeintlich am nächsten zum Ziel ; liegenden Punktes, so wird der aktuelle Punkt in 'Shortest' eingetragen und der Vergleich geht mit dem ; nächsten Wegpunkt weiter. So erhalten wir am Ende den Punkt, der vermutlich am nächsten am Ziel liegt. For Node.Waynode = Each Waynode If ( Node\GCost + Node\HCost# ) < ( Shortest\GCost + Shortest\HCost# ) Then Shortest = Node Next Node.Waynode = Shortest ; Den am nächsten zum Ziel liegenden Punkt für die folgenden Berechnungen in 'Node' ablegen. If Node = Null Then Return "" ; Gibt es keinen Punkt mehr, der betrachtet werden könnte, gibt es keine Verbindung zum Ziel. Closed.ClosedList = New ClosedList Closed\X = Node\X Closed\Y = Node\Y Closed\Parent = Node\Parent ; Nun legen wir den Punkt in der Closedlist ab. Er ist fertig betrachtet. If Node\X - 1 >= 0 Then StateLeft = PeekByte( Indexed, ( Node\X - 1 )*MapsizeY + Node\Y ) Else StateLeft = 1 If Node\X + 1 < MapsizeX Then StateRight = PeekByte( Indexed, ( Node\X + 1 )*MapsizeY + Node\Y ) Else StateRight = 1 If Node\Y + 1 < MapsizeY Then StateBottom = PeekByte( Indexed, Node\X*MapsizeY + Node\Y + 1 ) Else StateBottom = 1 If Node\Y - 1 >= 0 Then StateTop = PeekByte( Indexed, Node\X*MapsizeY + Node\Y - 1 ) Else StateTop = 1 ; Wenn die benachbarten Punkte noch auf der Karte liegen und nicht bereits betrachtet wurden, so ist der entsprechende ; Wert auf 0, ansonsten auf 1. If Not StateLeft Then ; Wenn der Punkt gültig ist, wird er betrachtet If MapData( Node\X - 1, Node\Y ) = 0 Then ; Ist sein Feld nicht blockiert, legen wir einen neuen Wegpunkt an. Newbie.Waynode = New Waynode Newbie\X = Node\X - 1 ; Seine Koordinaten sind benachbart zum vorherigen Feld Newbie\Y = Node\Y Newbie\GCost = Node\GCost + 1 ; Die Wegkosten bis zum Wegpunkt sind um eins höher als zum vorherigen ; Wegpunkt, da wir um ein Tile nach rechts/links/oben/unten mussten. Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) ; Die Wegkosten zum Ziel abschätzen (per Pythagoras) Newbie\Parent = Closed ; Den vorherigen Wegpunkt eintragen PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True ; In der Bank eintragen, dass der Punkt bereits ; betrachtet wurde. EndIf EndIf ; Die restlichen Betrachtungen sind analog zur ersten - nur für andere Felder (oben/unten/rechts) If Not StateRight Then If MapData( Node\X + 1, Node\Y ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X + 1 Newbie\Y = Node\Y Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Not StateTop Then If MapData( Node\X, Node\Y - 1 ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X Newbie\Y = Node\Y - 1 Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Not StateBottom Then If MapData( Node\X, Node\Y + 1 ) = 0 Then Newbie.Waynode = New Waynode Newbie\X = Node\X Newbie\Y = Node\Y + 1 Newbie\GCost = Node\GCost + 1 Newbie\HCost# = Sqr( ( X2 - Newbie\X )*( X2 - Newbie\X ) + ( Y2 - Newbie\Y )*( Y2 - Newbie\Y ) ) Newbie\Parent = Closed PokeByte Indexed, Newbie\X*MapsizeY + Newbie\Y, True EndIf EndIf If Node\X = X2 And Node\Y = Y2 Then ; Sind wir am Ziel angelangt? Delete Each Waynode ; Alle Wegpunkte löschen - die brauchen wir jetzt nicht mehr. Path$ = "" Closed.ClosedList = Last ClosedList ; Den letzten betrachteten Punkt holen While Closed\Parent <> Null ; Bis wir am Startpunkt angelangt sind (der hat ja keinen vorherigen Wegpunkt). Der Startpunkt ; wird vor der Wegberechnung definiert (ein wenig hochscrollen) Select Closed\X - Closed\Parent\X ; Differenz der Koordinaten auf der X - Achse Case 1 Path$ = Path$ + "1" Case -1 Path$ = Path$ + "3" Case 0 Select Closed\Y - Closed\Parent\Y ; ...und der Y - Achse Case 1 Path$ = Path$ + "2" Case -1 Path$ = Path$ + "4" End Select End Select Closed = Closed\Parent ; Den vorherigen Wegpunkt betrachten Wend Delete Each ClosedList ; Die Closedlist brauchen wir auch nicht mehr FreeBank Indexed ; Genausowenig die Bank Return Path$ ; Nun den Pfad zurückgeben EndIf Delete Node ; Wenn wir nicht am Ziel sind, dann den Wegpunkt löschen. Er ist fertig betrachtet und in der Closedlist. Forever End Function |
||
| 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 | ||
|
ozzi789 |
So, Jun 29, 2008 19:12 Antworten mit Zitat
|
|---|---|---|
|
Noobody hat Folgendes geschrieben: Was du suchst, ist vermutlich A*.
Der Algorithmus ist nicht allzuschwer, gute Tutorials findest du überall im Internet, wie zum Beispiel dieses hier. Im Codearchiv gibt es auch jede Menge davon, aber am besten ist es doch, wenn man es selber schreibt. thx der Link ist echt gut 
|
||
|
0x2B || ! 0x2B
C# | C++13 | Java 7 | PHP 5 |
||
Dreamora |
So, Jun 29, 2008 20:58 Antworten mit Zitat
|
|
|---|---|---|
|
Wenn du mit Wegpunktnetzen arbeitest, befrag google vor allem auch nach Dijkstra.
A* wird normalerweise bei vollständigen Grids genutzt, nicht bei sehr "leeren" gittern wo man nur einzelne graphen drin hat wie bei einem Wegpunktnetz. |
||
| Ihr findet die aktuellen Projekte unter Gayasoft und könnt mich unter @gayasoft auf Twitter erreichen. | ||
|
|
ToeB |
Di, Jul 15, 2008 15:23 Antworten mit Zitat
|
|---|---|---|
|
sry ich war 2 wochen weg und konnte deswegen nicht gleich antworten... Also bitte nicht gleich schließen...
Ich hab mal ne fRage... Wie kann ich eine person anhand dieses Strrings die Strecke abfahren lassen ?? mfg ToeB |
||
|
Religiöse Kriege sind Streitigkeiten erwachsener Männer darum, wer den besten imaginären Freund hat.
Race-Project - Das Rennspiel der etwas anderen Art SimpleUDP3.0 - Neuste Version der Netzwerk-Bibliothek Vielen Dank an dieser Stelle nochmal an Pummelie, welcher mir einen Teil seines VServers für das Betreiben meines Masterservers zur verfügung stellt! |
||
|
|
Noobody |
Di, Jul 15, 2008 17:09 Antworten mit Zitat
|
|---|---|---|
|
Naja, im String stehen ja Zahlen von 1 - 4, die die Richtung angeben, wobei 1 für links steht, 2 für oben, 3 für rechts und 4 für unten (steht in der Hauptschleife sogar in einem Kommentar).
Wenn du nun eine Figur eine Strecke abfahren lassen willst, dann kannst du mithilfe des Strings herausfinden, in welche Richtung sie als nächstes gehen muss. Dann bewegst du die Figur in jedem Frame in diese Richtung, bis sie das Tile, auf das sie gehen muss, erreicht hat. Dann geht der Spuk wieder von vorne los, d.h. die nächste Richtung auslesen und Figur bewegen. Das geht dann solange, bis du das Ende des Strings erreicht hast - das heisst, du hast die Zielposition erreicht. |
||
| 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 | ||
Übersicht
BlitzBasic Allgemein
Powered by phpBB © 2001 - 2006, phpBB Group