Tipp 0319 Path-Finder
Autor/Einsender:
Datum:
  Alexander Csadek
17.03.2003
Entwicklungsumgebung:
DirectX-Version:
  VB 6
DirectX 7
Mit einem Path-Finder kann man einem Spiel ein bisschen etwas von einer künstlichen Intelligenz geben. Er hilft dabei, Spielfiguren einen Weg zu einem bestimmten Ziel zu finden, egal wie viele Hindernisse dazwischen liegen. So ist ein Path-Finder sehr hilfreich, um einem Feind die Möglichkeit zu geben, den Weg zum Spieler auf dem Spielfeld zu finden, oder damit die Spielfiguren den Weg zu einem Zielpunkt von alleine zu finden.
Als erstes sucht der Path-Finder die Position von Start und Ziel. Natürlich muss man dies nicht machen, wenn beide Positionen schon bekannt sind, dann braucht man diese beiden Punkte nur zu setzen. Als nächstes prüft der Path-Finder, ob überhaupt ein Ziel- und Startpunkt existiert. Wenn eines von den beiden fehlt, gibt es auch keinen Pfad zu finden.
Ein Pfad-Array wird ausgefüllt, der Startpunkt bekommt 0, alle Hindernisse einen sehr hohen Wert, z.B. 999. Alle anderen, inkl. dem Zielpunkt, werden auf -1 gesetzt. Jetzt hat man ein Array in dem alle nicht begehbaren Felder (Hindernisse) den Wert 999, und alle begehbaren, inkl. dem Zielpunkt, den Wert -1 haben, der Startpunkt hat 0.
Der Path-Finder durchsucht im nächsten Schritt das Pfad-Array nach begehbaren Feldern und deren Nachbarschaft. Ist es begehbar und noch nicht markiert worden, dann wird es jetzt markiert. Die Nachbarfelder bekommen einen höheren Wert als das Ausgangsfeld. So haben dann z.B. alle Felder rund um den Startpunkt mit dem Wert 0 einen Wert von 1. Dies geschieht solange bis keine Felder mehr frei sind, also den Wert -1 haben.
Der Path-Finder geht den Weg nun mehr oder weniger zurück und schaut, welches Feld in der Nachbarschaft einen kleineren Wert hat . Und zwar solange bis es das Ziel erreicht hat. Hat er das Ziel nicht erreicht, gibt es keinen Pfad.
 
Option Explicit

Sub Pathfinder()
  Dim X As Integer, Y As Integer
  Dim nX As Integer, nY As Integer
  Dim ptStart As strcPoint
  Dim ptZiel As strcPoint
  Dim ptPunkt As strcPoint
  Dim bolGefunden As Boolean
  Dim LowValue As Integer

  ptStart.X = -1
  ptZiel.X = -1

  For Y = 0 To MAPHEIGHT
    For X = 0 To MAPWIDTH
      If MAP(X, Y) = TileStart Then
        ptStart.X = X
        ptStart.Y = Y
      End If
      If MAP(X, Y) = TileZiel Then
        ptZiel.X = X
        ptZiel.Y = Y
      End If
      If MAP(X, Y) = TilePunkt Then MAP(X, Y) = TileLeer
    Next X
  Next Y

  If ptStart.X = -1 Then
    lbl_Pfad.Caption = "keinen Startpunkt gefunden !"
    Exit Sub
  End If

  If ptZiel.X = -1 Then
    lbl_Pfad.Caption = "keinen Zielpunkt gefunden !"
    Exit Sub
  End If

  For Y = 0 To MAPHEIGHT
    For X = 0 To MAPWIDTH
      Select Case MAP(X, Y)
        Case TileStart: Path(X, Y) = 0
        Case TileBlock: Path(X, Y) = 999
        Case TileLeer: Path(X, Y) = -1
        Case Else: Path(X, Y) = -1
      End Select
    Next X
  Next Y

  Do
    bolGefunden = False

    For Y = 0 To MAPHEIGHT
      For X = 0 To MAPWIDTH
        MARK(X, Y) = False
        If Path(X, Y) = -1 Then
          For nY = Y - 1 To Y + 1
            For nX = X - 1 To X + 1
              If (nX >= 0 And nY >= 0) And _
                    (nX <= MAPWIDTH And nY <= MAPHEIGHT) And _
                    Not (nX = X And nY = Y) Then
                If Path(nX, nY) >= 0 And Path(nX, nY) <> 999 Then
                  MARK(X, Y) = True
                  bolGefunden = True
                End If
              End If
            Next nX
          Next nY
        End If
      Next X
    Next Y

    For Y = 0 To MAPHEIGHT
      For X = 0 To MAPWIDTH
        If MARK(X, Y) Then
          LowValue = 999
          For nY = Y - 1 To Y + 1
            For nX = X - 1 To X + 1
              If (nX >= 0 And nY >= 0) And _
                    (nX <= MAPWIDTH And nY <= MAPHEIGHT) Then
                If Path(nX, nY) >= 0 Then
                  If Path(nX, nY) < LowValue Then _
                        LowValue = Path(nX, nY)
                End If
              End If
            Next nX
          Next nY
          Path(X, Y) = LowValue + 1
        End If
      Next X
    Next Y
  Loop While bolGefunden

  If Path(ptZiel.X, ptZiel.Y) <> -1 Then
    ptPunkt = ptZiel
    LowValue = Path(ptZiel.X, ptZiel.Y)
    Do While LowValue > 0
      bolGefunden = False
      Do
        Do
          nX = Rnd() * 2 - 1
          nY = Rnd() * 2 - 1
        Loop While ((nX = 0 And nY = 0) Or _
                    (ptPunkt.X + nX) < 0 Or _
                    (ptPunkt.X + nX) > MAPWIDTH Or _
                    (ptPunkt.Y + nY) < 0 Or _
                    (ptPunkt.Y + nY) > MAPHEIGHT)

        If Path(ptPunkt.X + nX, ptPunkt.Y + nY) < LowValue Then
          bolGefunden = True
          MAP(ptPunkt.X, ptPunkt.Y) = TilePunkt
          ptPunkt.X = ptPunkt.X + nX
          ptPunkt.Y = ptPunkt.Y + nY
          LowValue = Path(ptPunkt.X, ptPunkt.Y)
        End If
      Loop While Not bolGefunden
    Loop
    MAP(ptZiel.X, ptZiel.Y) = TileZiel
    lbl_Pfad.Caption = "Pfad gefunden !"
  Else
    lbl_Pfad.Caption = "Keinen Pfad gefunden !"
  End If
End Sub
 
Hinweis
Im Code-Ausschnitt ist nur die Path-Finder-Routine dargestellt, die auch ohne DirectX verwendet werden kann.
Um dieses Beispiel ausführen zu können, wird die DirectX 7 for Visual Basic Type Library benötigt (siehe dazu die Erläuterungen in der DirectX-Rubrik).

Windows-Version
95
98/SE
ME
NT
2000
XP
Vista
Win 7
VB-Version
VBA 5
VBA 6
VB 4/16
VB 4/32
VB 5
VB 6


Download  (7,3 kB) Downloads bisher: [ 1267 ]

Vorheriger Tipp Zum Seitenanfang Nächster Tipp

Startseite | Projekte | Tutorials | API-Referenz | VB-/VBA-Tipps | Komponenten | Bücherecke | VB/VBA-Forum | VB.Net-Forum | DirectX-Forum | Foren-Archiv | DirectX | VB.Net-Tipps | Chat | Spielplatz | Links | Suchen | Stichwortverzeichnis | Feedback | Impressum

Seite empfehlen Bug-Report
Letzte Aktualisierung: Sonntag, 18. September 2011