Pfadfinde Algorithmus

    • VB.NET

    Es gibt 12 Antworten in diesem Thema. Der letzte Beitrag () ist von Firestorm.

      Pfadfinde Algorithmus

      Der TE des Thema [VB 2010] Problem bei der umsetzung eines Games wollte ein TowerDefense mit dynamischen Routen der Monster programmieren - sie sollen also von alleine um die Türme herum laufen können, noch dazu auf dem kürzesten weg. Ich habe nun einen Weg-Finde-Algorithmus ähnlich der A*-Methode in VB.NET Realisiert.
      Viel zu sagen gibt es denke ich nicht, selbst wer den Algorithmus nicht versteht oder verstehen will sieht sofort, wo er den code für sich anpassen kann. Der Pfad kann in der Auflistung "Wegpunkte" nachvollzogen werden. Ebenfalls werden die Wegpunkte in das intern verwendete "MapFormat" eingetragen.


      Als input wird eine scharz/weiß-bitmap verlangt (schwarz = hinderniss, weiß = begehbar). Einfacher ist es - sofern man bereits eine eigene datenstruktur aufgebaut hat - direkt auf das intern genutzte "MapFormat" zurückzugreifen und eigene Karten etc in dieses umzuwandeln.

      Um etwas zur Performance zu sagen: Der Code ist mit Sicherheit an der ein oder anderen Stelle ausbesserbar, eine 100x100 pixel große bitmap berechnet es allerdings in "nullkommanix" - und 100x100 Tiles sind schon einiges finde ich - vor allem für ein TowerDefense^^

      Hier mal ein Video, dass die Funktion grafisch darstellt:




      Hier der Source:
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Public Class PathFinder
      3. Public Sub New(ByVal _MapPath As String, ByVal _start As Point, ByVal _ziel As Point)
      5. Dim tmp As New Bitmap(_MapPath)
      6. Start = _start
      7. Ziel = _ziel
      9. MapSize = tmp.Size
      10. Map = New Feld(MapSize.Width - 1, MapSize.Height - 1) {}
      12. For x = 0 To MapSize.Width - 1
      13. For y = 0 To MapSize.Height - 1
      15. Dim tmpFeld As New Feld
      17. If tmp.GetPixel(x, y).R > 50 Then
      18. tmpFeld.Hindernis = False
      19. Else
      20. tmpFeld.Hindernis = True
      21. End If
      23. Map(x, y) = tmpFeld
      25. Next
      26. Next
      28. 'startet die wegsuche
      29. Berechne()
      30. End Sub
      32. Public Start As New Point(10, 90)
      33. Public Ziel As New Point(90, 10)
      35. Public MapSize As New Size
      36. Public Map(,) As Feld
      38. Public Wegpunkte As New List(Of Point)
      40. Public Event NoWay()
      42. Public Sub Berechne()
      44. Dim lastLocs As New Queue(Of Point)
      45. Dim tmpGüte As Integer = 0
      46. Dim Nachbarn As New List(Of Point)
      47. Nachbarn.Add(Start)
      49. Dim Treffer As Boolean = False
      50. Dim KeinWeg As Boolean = False
      52. Do 'Until Treffer = True
      54. KeinWeg = True
      55. For Each n As Point In Nachbarn
      56. lastLocs.Enqueue(n)
      57. If Map(n.X, n.Y).Güte = -1 Then KeinWeg = False
      58. Next
      60. If KeinWeg = True Then RaiseEvent NoWay()
      62. Do
      63. Dim loc As Point = lastLocs.Dequeue
      64. Dim F As Feld = Map(loc.X, loc.Y)
      66. If F.Güte = -1 Then
      67. Map(loc.X, loc.Y).Güte = tmpGüte
      69. If loc = Ziel Then Treffer = True
      71. 'nachbarpunkte der newlastlocsliste hinzufügen
      72. Dim x As Integer = loc.X
      73. Dim y As Integer = loc.Y
      75. Dim Ld As Point = New Point(x - 1, y - 1)
      77. Dim points() As Point = New Point() {New Point(x + 1, y), New Point(x - 1, y), New Point(x, y - 1), New Point(x, y + 1)}
      79. For Each p As Point In points
      80. If p.X >= 0 AndAlso p.X < MapSize.Width AndAlso p.Y >= 0 AndAlso p.Y < MapSize.Height Then
      81. Dim cn As Feld = Map(p.X, p.Y)
      82. If cn.Hindernis = False AndAlso cn.Güte = -1 Then
      83. Nachbarn.Add(p)
      84. End If
      85. End If
      86. Next
      87. End If
      91. Loop While (Treffer = False) AndAlso (lastLocs.Count <> 0) AndAlso (KeinWeg = False)
      93. tmpGüte += 1
      95. Loop While (Treffer = False) AndAlso (KeinWeg = False)
      97. 'rückverfolgung des weges
      98. If Treffer = True Then
      99. Wegpunkte.Add(Ziel)
      100. Do While tmpGüte > 0
      101. Map(Wegpunkte.Last.X, Wegpunkte.Last.Y).Wegpunkt = True
      102. Wegpunkte.Add(GetBefore(Wegpunkte.Last))
      103. tmpGüte -= 1
      104. Loop
      105. End If
      107. End Sub
      108. Function GetBefore(ByVal loc As Point) As Point
      109. Dim x As Integer = loc.X
      110. Dim y As Integer = loc.Y
      111. Dim currentGüte As Integer = Map(x, y).Güte
      112. Dim points() As Point = New Point() {New Point(x + 1, y), New Point(x - 1, y), New Point(x, y - 1), New Point(x, y + 1)}
      114. For Each p As Point In points
      115. If p.X >= 0 AndAlso p.X < MapSize.Width AndAlso p.Y >= 0 AndAlso p.Y < MapSize.Height Then
      116. If Map(p.X, p.Y).Güte < currentGüte AndAlso Map(p.X, p.Y).Güte >= 0 Then
      117. Return p
      118. End If
      119. End If
      120. Next
      122. End Function
      124. Class Feld
      125. Public Hindernis As Boolean = False
      126. Public Wegpunkt As Boolean = False
      127. Public Güte As Integer = -1
      128. End Class
      129. Sub ErrorMsgBox() Handles Me.NoWay
      130. MsgBox("Es existiert kein möglicher weg!")
      131. End Sub
      133. Public Function ToBitmap() As Bitmap
      134. Dim tmp As New Bitmap(MapSize.Width, MapSize.Height)
      135. Dim c As Color = Color.Black
      136. For x = 0 To MapSize.Width - 1
      137. For y = 0 To MapSize.Height - 1
      138. c = Color.Black
      139. If Map(x, y).Hindernis = True Then c = Color.Gray
      140. If Map(x, y).Wegpunkt = True Then c = Color.Red
      141. tmp.SetPixel(x, y, c)
      142. Next
      143. Next
      144. Return tmp
      145. End Function
      146. End Class


      und ein Anwendungsbeispiel..
      Spoiler anzeigen

      VB.NET-Quellcode

      1. Dim tmp As New PathFinder("M:\a.bmp", New Point(10, 90), New Point(90, 10))
      2. tmp.ToBitmap.Save("M:\result.bmp")




      EDIT: Im Showroom gibt es ab jezt eine Verbesserte/Erweiterte Version als OpenSource Lib: [Release] PathFinderLib 1.0

      Dieser Beitrag wurde bereits 2 mal editiert, zuletzt von „FreakJNS“ ()

      Brauchte zwar eine Weile

      Kommt jetzt zwar drauf an wie lange es dauert, aber eigt. ist es egal, wenn der Weg nicht direkt da ist, denn schließlich handelt es sich um eine Bewegung, es muss nur mindestens so schnell rechnen, wie sich das Objekt bewegen soll...
      Ich wollte auch mal ne total überflüssige Signatur:
      ---Leer---

      Es braucht so um die 5-10 Sekunden zum Berechnen ... habe das Ganze jetzt mal mit LockBits realisiert, einen großen Performance-Unterschied konnte ich aber leider nicht feststellen.

      Hallo,

      hab sowas auch mal umgesetzt.
      Nur mit deutlich weniger Wegpunkten.

      War aber auch zu langsam.

      Ich denke, du solltest immer nur einige wenige neue Schritte berechnen lassen.
      Willst du den Weg auf einmal haben kommst du mit der Zeit nicht klar.

      Gruss

      mikeb69

      Hi, schon mal danke für die lobenden beiträge!^^

      Ich will nur nochmal sagen, dass JEDER Pixel einzeln geprüft wird. Bei einem Rasterbasierendem RPG steht ein Pixel also für ein Tile - bei dem Gameboyspiel Pokemon ist ein Tile 16x16 Pixel groß, der maximale Bildschirminhalt ist also deutlich kleiner als 100x100 "Kollisions-Pixel".
      Ich habe hier die Kollisionsmap von Pokemon: Die Reine Rechenroutine (also das einlesen der Bitmap nicht mitgerechnet, frisst ca. 200ms) braucht nur 135ms um einen Pfad über die gesamte Map zu finden! Jeder der Pokemon gespielt hat weiß, dass er für diesen Weg viele Stunden spielzeit opfern muss^^ Kurze strecken (von einem dorf ins andere) lassen sich in 10-20ms finden.



      Sehr Interessant ist es auch, wenn man die Güte-Werte grafisch darstellt:



      Spoiler anzeigen

      Der Code gehört in den Berechne-Sub. => nach den loops und vor der "rückverfolgung des weges"

      VB.NET-Quellcode

      1. ''(...)
      2. ''Loop While (Treffer = False) AndAlso (KeinWeg = False)
      5. 'Dim tmp As New Bitmap(MapSize.Width, MapSize.Height)
      6. 'Dim c As Color = Color.Red
      7. 'For x = 0 To MapSize.Width - 1
      8. ' For y = 0 To MapSize.Height - 1
      9. ' c = Color.Red
      10. ' Dim v As Integer = CInt((Map(x, y).Güte / tmpGüte) * 255)
      11. ' c = Color.FromArgb(255, v, v, v)
      12. ' If Map(x, y).Güte = -1 Then c = Color.Red
      13. ' If Map(x, y).Hindernis = True Then c = Color.Blue
      14. ' If Map(x, y).Wegpunkt = True Then c = Color.Red
      15. ' tmp.SetPixel(x, y, c)
      16. ' Next
      17. 'Next
      18. 'tmp.Save("m:\lol.bmp")
      21. ''rückverfolgung des weges
      22. ''If Treffer = True Then

      einen großen Performance-Unterschied konnte ich aber leider nicht feststellen.

      Dann musst du es irgendwie falsch angewendet haben...

      Hinzu kommt natürlich noch, dass man das nachher eher mit einem eigenen MapSystem macht, welches dann mit Arrays arbeiten dürfte, wobei man da dann keine Pixel mehr auflesen muss und die Performance wiederum steigt...

      Aber wie gesagt, die Berechnung muss nict schneller sein, als sich das jeweilige Objekt, dass den Pfad entlang geht nachher braucht...
      Ich wollte auch mal ne total überflüssige Signatur:
      ---Leer---

      einen großen Performance-Unterschied konnte ich aber leider nicht feststellen.

      richtig weil: Die Map wird aus der bitmap ausgelesen - nur einmal - und in ein internes format gespeichert. Also nochmal: das laden der bitmap ist ein einmaliger vorgang, noch dazu eher künstlicher natur da ein spiel bereits über ein eigenes map-system verfügen sollte welches zig mal performanter ist als das laden aus einer bitmap. eben genau wie jvbsl schon sagte

      Dann musst du es irgendwie falsch angewendet haben...

      nicht unbedingt - sooo langsam sind die bitmapfunktionen auch nciht - zumindest bei großen bitmaps steigt der rechenaufwand zur wegfindung so starkt, dass das laden in den hintergrund rückt. lockbits ist aber allemale schöner! ich verweise auf das pokemonbeispiel von mir: laden der bitmap = 200ms, berechnen des pfades = 135ms

      Aber wie gesagt, die Berechnung muss nict schneller sein, als sich das jeweilige Objekt, dass den Pfad entlang geht nachher braucht...

      das ist falsch^^ sieh dir mal das youtube-video das ich in den ersten post gesetzt habe an, dann kannst du sogar sehen warum: im endeffekt gibt es zwei zustände: der pfad (oder auch nur der kleineste teil von ihm) ist bekannt oder eben nicht. Aussagen über den Pfad können erst getroffen werden wenn alle pixel bis zum ziel durchgerechnet wurden - der weg wird nämlich vom ziel aus zurückrekonstruiert!

      Optimierungsmöglichkeiten gibt es aber trotzdem: Mal angenommen man hat ein RPG mit vielen dörfern. Man möchte nun von dorf #5 zu dorf #32 reisen. baut man nun eine struktur auf die die dörfer unterinander verknüpft kann man sagen "der schnellste weg ist wenn man von dorf #5, nach #14,#33 und anschließend zu #32 geht". Dafür ist A* gedacht. Erst dann setzt man meinen Pfadfinder ein, und zwar nur um einen einzelnen weg von jetztposition zu dorf #XX zu suchen.

      das ist falsch^^

      Gut, da kommt es jetzt auf den verwendeten Algorithmus an :P

      Ich spreche jetzt auf Algorithmen an, die nicht unbedingt den schnellsten finden, aber trotzdem einen Weg finden ;)
      Natürlich ist dabei aber eine gewisse Vorrausberechnung nötig...
      Ich wollte auch mal ne total überflüssige Signatur:
      ---Leer---

      So, eine kleine Erweiterung:



      Bisher wurden nur die sogenannten Von-Neumann-Nachbarn als Nachbarpixel gewertet. Das hat zur Folge, dass kein Diagonaler Pfad möglich ist - alles sieht sehr eckig aus.

      Nun tausche man einfach die alte Liste der Nachbarpunkte..

      VB.NET-Quellcode

      1. Dim points() As Point = New Point() {New Point(x + 1, y), New Point(x - 1, y), New Point(x, y - 1), New Point(x, y + 1)}

      ..gegen die neue Moore-Nachbar-Liste aus (zu finden in: Sub Berechnen und Function GetBefore)

      VB.NET-Quellcode

      1. Dim points() As Point = New Point() {New Point(x + 1, y), New Point(x - 1, y), New Point(x, y - 1), New Point(x, y + 1), New Point(x + 1, y + 1), New Point(x - 1, y + 1), New Point(x + 1, y - 1), New Point(x - 1, y - 1)}


      Das Ergebnis (Moore-Liste im Rechten Bild) zeigt geschwungenere, abgerundetere Pfadstrecken. Großer Nachteil: Theoretisch ist das ganze Falsch: wenn ein pixel eine kantenlänge von 1 hat ist die diagonale 1.4 einheiten lang, nicht 1. Daran stört sich mein Algo allerdings nicht... diagonal und seitlich zählt als eine Einheit. Ist im endeffekt - mir zumindest - egal. Ich sehe nur, dass der Weg schöner aussieht

      Was ich mich momentan noch frage ist wie eine sackgasse erkannt wird.

      VB.NET-Quellcode

      1. Map(loc.X, loc.Y).Güte = tmpGüte


      Mit der Zeile werden ja, sollte ich das ganze richtig verstanden haben, allen Nachbarn des aktuellen punkt's die aktuelle Güte zugewiesen. Dann müsste es doch auf dem Rückweg, wenn du den Pfad tatsächlich ermitteltst ein Problem geben weil alle Punkte eine Güte über -1 haben, oder?

      Funktioniert aber einwandfrei.

      Mfg
      Firestorm

      eine güte von -1 bedeutet, dass der Knoten noch keiner güte-bestimmung unterzogen wurde.
      mit der von dir zitierten zeile wird nur dem aktuellem Punkt die güte zugewiesen! die nachbarn werden erst später ausfindig gemacht (for-schleife ab zeile 79).
      Ich gebe zu, dass der algorithmus sehr sehr verschachtelt ist und schwer nachzuvollziehen ist..

      Ganz grob gesagt: der startpunkt wird expandiert, d.h. seine betretbaren (kein hinderniss, güte = -1) nachbarn werden gefunden. diese nachbarn kommen in eine liste. Alle knoten auf dieser liste haben die selbe güte, da sie alle gleichweit weg vom startpunkt sind. die güte wird um 1 erhöht.
      der nächste schritt ist, dass die knoten auf eben dieser liste expandiert werden und die "neuen" nachbarn auf dieser liste landen - mit erhöhter güte.

      dies wiederholt sich solange bis ein knoten mit den koordinaten des zielpunktes übereinstimmt. dann beginnt die rückverfolgung:

      zielpunkt hat beispielsweise die güte 10. Der nächst nähere punkt zum startpunkt muss also die güte 9 haben. dieser wird gefunden (sollte es mehrere geben nimmt man einfach den ersten den man findet, sind ja alle gleichweit weg^^). Nun sucht man von diesem punkt ausgehen den nächst näheren punkt - gütewert = 8 usw...

      so rekonstruiert man den weg von ziel zu start. fertig^^



      Das Problem mit der Sackgasse erübrigt sich recht schnell, da knoten die in einer sackgasse liegen (also hindernisse als nachbarn haben und knoten mit güte <> -1) können nciht expandiert werden. das heißt, dass ihre nachbarpunkte nie auf die entsprechende liste gesetzt werden können und die zukünftige überprüfung sich auf die übrigen gültigen nachbarpunkte anderer knoten ausweitet.

      Dieser Beitrag wurde bereits 1 mal editiert, zuletzt von „FreakJNS“ ()

    Facebook
    Telefonspende