Hilfe bei Pathfinding

Übersicht BlitzBasic Allgemein

Neue Antwort erstellen

Cykid

Betreff: Hilfe bei Pathfinding

BeitragMi, März 09, 2016 19:31
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo zusammen Smile
Ich brauch hilfe... ich verstehe das pathfinding nicht richtig und wenn ich denke ich habs, bekomme ich es einfach nicht korrekt mit Type Objekten umgesetzt.

Mein letzter versuch war es folgenden Code mit meinen zu verknüpfen:

(Pathfinding 0 )
https://www.blitzforum.de/foru...athfinding

Ich bekomme den aber einfach nicht so wie ich möchte implementiert.

Gibt es vlt. irgendwo ein gutes Tutorial welches ich einfach nicht gefunden habe?

Gibt es vlt. eine noch einfachere Methode?

Mein Ziel ist es das dass Objekt, nennen wir es Soldier, eine List hat, mit schritten die er abarbeiten muss.

Dahin komme ich leider nicht

Viele Grüße,
Maik

DAK

BeitragDo, März 10, 2016 17:27
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey!

Wenn du verstehen willst, wie der Algo funktioniert, schau dir mal die Wiki-Seite zum Dijkstra-Algo an. Der ist relativ simpel. Das GIF auf der Seite veranschaulicht die Funktionsweise sehr gut.

Die Listen werden durch einzelne Types implementiert, da jeder Type in Blitz automatisch eine Liste inkludiert hat.

Die Knoten im Dijkstra sind Pixel oder Tiles oder wasauchimmer du da in deinem Programm hast als Pfadfindungs-Knoten.

Wenn du den Dijkstra verstanden hast, kannst du mit dem A* weiter machen, der ist nicht viel komplexer und tendenziell schneller.
Gewinner der 6. und der 68. BlitzCodeCompo

Cykid

BeitragDo, März 10, 2016 20:28
Antworten mit Zitat
Benutzer-Profile anzeigen
Ach, das hatten wir irgendwann mal in der Uni Very Happy

Ich schau mal, ich denke ich sollte einfach nochmal bei 0 Anfangen.

Manchmal steuert man in eine Völlig falsche Richtung.

Ich arbeite nochmal Step bei Step nach diesem Video:
https://www.youtube.com/watch?v=4cIkP9Yw7hw

TimBo

BeitragFr, März 11, 2016 1:14
Antworten mit Zitat
Benutzer-Profile anzeigen
A* ist schon die bessere Option, falls du den Luxus hast, dass es sich bei deinen Abständen um euklidische Distanzen handelt.
mfg Tim Borowski // CPU: Ryzen 2700x GPU: Nvidia RTX 2070 OC (Gigabyte) Ram: 16GB DDR4 @ 3000MHz OS: Windows 10
Stolzer Gewinner des BCC 25 & BCC 31
hat einen ersten Preis in der 1. Runde beim BWInf 2010/2011 & 2011/12 mit BlitzBasic erreicht.

diceman

BeitragDo, Mai 12, 2016 18:13
Antworten mit Zitat
Benutzer-Profile anzeigen
Falls es hilft, hier ist meine Implementierung der A*-Wegfindungs-Routine: Smile
- Fertig kompilierbarer Code
- Optionen zur Darstellung des Pfades inklusive

Mit geringfügigem Aufwand kann man beim Suchen des Pfades noch eine Regel hinzufügen, daß keine "Ecken abgeschnitten" werden, also nur Diagonal gezogen wird, wenn man dabei keine Ecke eines Hindernis-Tiles tangiert.


Code: [AUSKLAPPEN]

Global FindPath
Const xMax = 49
Const yMax = 37
Global tileSize = 16

Global xOrigin,yOrigin ;Ursprungs-Koordinaten
Global xTarget,yTarget ;Zielkoordinaten
Dim map(xMax,yMax) ;1 = offenes Feld, 0 = Hindernis




;Richtungs-Modifikatoren einlesen ... 1-4 = "Himmelsrichtungen", 5-8 = Diagonalen
Dim dirModX(8), dirModY(8)

Restore dir_data
For a = 1 To 8
   Read dirModX(a)
   Read dirModY(a)
Next

.dir_data
Data 0,-1 ;Norden
Data -1,0 ;Westen
Data 1,0 ;Osten
Data 0,1 ;Süden

Data -1,-1 ;NW
Data 1,-1 ;NO
Data 1,1 ;SO
Data -1,1 ;SW





;Mit ganzen Zahlen arbeiten! Floats verlangsamen den Prozess!
Const costStraight = 10, costDiagonal = 14 ;Pfadkosten initialisieren (14 => angenäherte Wurzel aus 2)

Dim checkList(xMax, yMax)
Dim parentX(xMax,yMax), parentY(xMax,yMax)
Dim pathCost(3,xMax,yMax) ;1 = G-Kosten, 2 = H-Kosten, 3 = F-Kosten

Type NODE
   Field X
   Field Y
End Type



;Optional für Darstellung des Pfades:
Const maxPath = 200 ;Anzahl der Nodes, die gespeichert werden für die Darstellung
Dim drawPath_X(maxPath), drawPath_Y(maxPath)













SeedRnd MilliSecs()
Graphics 800,600,16,2
SetBuffer BackBuffer()

;zufällige Map erstellen und zeichnen
For y = 1 To yMax
   For x = 1 To xMax
      map(x,y) = limit(Rand(0,2),0,1) ;2/3-Verhältnis freie Felder zu Hindernissen
      If map(x,y) = 1 Then Rect(x-1)*tileSize,(y-1)*tileSize,tileSize,tileSize,1
   Next
Next

;zufällige Koordiaten wählen
Repeat
   xOrigin = Rand(1,xMax)
   yOrigin = Rand(1,yMax)
   xTarget = Rand(1,xMax)
   yTarget = Rand(1,yMax)
Until map(xOrigin,yOrigin) = 1 And map(xTarget,yTarget) = 1 And (Not (xOrigin = xTarget And yOrigin = yTarget))





FindPath = updatePath(xOrigin,yOrigin,xTarget,yTarget)

Color 255,0,0
If FindPath = True
   recordPath()
   drawPath()
Else
   Text 5,5,"Keinen Pfad gefunden!"
EndIf
Flip
WaitKey()
End









Function updatePath(xO,yO,xT,yT)
   Local PathExist

   ;Parameter jedesmal neu initialisieren, damit die Funktion ggf. wiederholt aufgerufen werden kann.
   Dim checkList(xMax,yMax)
   Dim parentX(xMax,yMax), parentY(xMax,yMax)
   Dim pathCost(3,xMax,yMax)
   Delete Each NODE


   
   xOrigin = xO
   yOrigin = yO
   xTarget = xT
   yTarget = yT
   ;es wird der Weg vom Ziel zum Start gesucht, da der Pfad hinterher rückwärts aufgezeichnet wird!
   ;so hat man dann automatisch die erste PathNode für die Darstellung an erster Stelle stehen!
   addOpenList(xTarget,yTarget,0,0) ;Weg wird rückwärts gesucht!!!
   PathExist = calculatePath()
   
   Return PathExist
End Function






Function calculatePath()
   Local x,y
   Local lowF
   Local lowF_X, lowF_Y
   Local tempG, tempH,tempF
   Local PathFound = False
   Local dir
   Local checkNode
   
      
   ;optionale G-Penalities für bestimmte Felder festlegen
   ;Beispiel: pathCost(1,lavaX,lavaY) = 1000
   Repeat
      ;find Low F
      node.NODE = First NODE
      If node <> Null
         lowF = pathCost(3,node\X,node\Y)
         lowF_X = node\X
         lowF_Y = node\Y   

         For node.NODE = Each NODE
            If pathCost(3,node\X,node\Y) < lowF            
               lowF = pathCost(3,node\X,node\Y)
               lowF_X = node\X
               lowF_Y = node\Y
            EndIf
         Next
      Else
         Return False
         ;optionale Konsequenz aufrufen, wenn kein Pfad gefunden wurde
      EndIf
      
      If checkList(lowF_X,lowF_Y) = 1
   
         addClosedList(lowF_X,lowF_Y)

         For dir = 1 To 8
            x = limit(lowF_X+dirModX(dir),1,xMax)
            y = limit(lowF_Y+dirModY(dir),1,yMax)
            
            If map(x,y) = 1
               ;optionale Bedingungen einfügen, ob das zu untersuchende, angrenzende Feld überhaupt legitim ist
               ;Mauern, Wasser, keine Ecken "abschneiden", etc.):
               checkNode = True
            
               If checkNode = True
                  PathFound = checkAdjacent(x,y,lowF_X,lowF_Y)
                  If PathFound = True Then Return True
               EndIf
            EndIf
         Next
      
      EndIf

   Forever
End Function






Function addOpenList(xx,yy,pX,pY)
   checkList(xx,yy) = 1
   node.NODE = New NODE
   node\X = xx
   node\Y = yy
   parentX(xx,yy) = pX
   parentY(xx,yy) = pY
End Function






Function addClosedList(xx,yy)
   checkList(xx,yy) = -1
   For node.NODE = Each NODE
      If node\X = xx And node\Y = yy
         Delete node
         Return
      EndIf
   Next
End Function






Function checkAdjacent(xx,yy,pX,pY)
   Local nodeCost = costStraight
   If xx <> pX And yy <> pY Then nodeCost = costDiagonal

   If checkList(xx,yy) = 1
      ;checken, ob der Weg zum bereits bekannten Feld über den neuen Pfad kürzer ist.
      checkNewPath(xx,yy,pX,pY)
   EndIf
   If checkList(xx,yy) = 0
      addOpenList(xx,yy,pX,pY)   
      pathCost(1,xx,yy) = pathCost(1,xx,yy) + pathCost(1,pX,pY) + nodeCost
      pathCost(2,xx,yy) = (Abs(xx-xOrigin) + Abs(yy-yOrigin)) * costStraight      ;Ausreichend für eine Approximation.
                                                               ;Genauer wäre eine Distanz-Berechnung mit dem Satz des Pythagoras,
                                                               ;der führt aber zu Fließkommazahlen, die man tunlichst vermeiden sollte!
      pathCost(3,xx,yy) = pathCost(1,xx,yy) + pathCost(2,xx,yy)
   EndIf
   
   If xx = xOrigin And yy = yOrigin Then Return True ;Weg wird rückwärts gesucht (Origin = Enemy)
   
   Return False
End Function






Function checkNewPath(xx,yy,pX,pY)
   Local nodeCost = costStraight
   If xx <> pX And yy <> pY Then nodeCost = costDiagonal

   ;checken, ob der Weg zum bereits bekannten Feld über den neuen Pfad kürzer ist.
   ;Wenn ja, dann Parent-Koordinaten des bekannten Feldes "umleiten".
   
   If (pathCost(1,pX,pY) + nodeCost) < pathCost(1,xx,yy)
      pathCost(1,xx,yy) = pathCost(1,pX,pY) + nodeCost
      pathCost(3,xx,yy) = pathCost(1,xx,yy) + pathCost(2,xx,yy)
      parentX(xx,yy) = pX
      parentY(xx,yy) = pY   
   EndIf
End Function





Function limit(var,min,max)
   If var > max Then Return max
   If var < min Then Return min
   
   Return var
End Function











;Optionale Funktionen für Darstellung des Pfades

Function recordPath()
   Local var
   Local pX_last, pY_last

        ;Variablen für Darstellung jedesmal neu initialisieren (falls Funktion mehrfach aufgerufen wird)
   For var = 1 To maxPath
      drawPath_X(var) = 0
      drawPath_Y(var) = 0
   Next

   drawPath_X(1) = xOrigin
   drawPath_Y(1) = yOrigin
   pX_last = xOrigin
   pY_last = yOrigin
   For var = 2 To maxPath
      drawPath_X(var) = parentX(pX_last,pY_last)
      drawPath_Y(var) = parentY(pX_last,pY_last)
      pX_last = drawPath_X(var)
      pY_last = drawPath_Y(var)
      
      If pX_last = 0 Then Exit
   Next
End Function





Function drawPath()
   Local lastX, lastY
   Local nextNode
   
   nextNode = 2
   lastX = xOrigin
   lastY = yOrigin
   
   Oval (xTarget-1)*tileSize,(yTarget-1)*tileSize,tileSize,tileSize,0
   Oval (xOrigin-1)*tileSize,(yOrigin-1)*tileSize,tileSize,tileSize,0
   
   Repeat
      Line ((lastX-1) * tileSize) + (tileSize/2),((lastY-1) * tileSize) + (tileSize/2),((drawPath_X(nextNode)-1) * tileSize) + (tileSize/2), ((drawPath_Y(nextNode)-1) * tileSize) + (tileSize/2)
      lastX = drawPath_X(nextNode)
      lastY = drawPath_Y(nextNode)
      nextNode = nextNode +1
   Until nextNode = maxPath Or drawPath_X(nextNode) = 0
End Function
Now these points of data make a beautiful line,
And we're out of Beta, we're releasing on time.

Neue Antwort erstellen


Übersicht BlitzBasic Allgemein

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group