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


Function FindPath$( X2, Y2, X1, Y1 )
  Local MapSizeX = MapWidth
   Local MApSizeY = MapHeight

   Indexed = CreateBank( MapsizeX*MapsizeY )   ; Eine Bank erstellen, um bereits berechnete Felder einzutragen
   
   begin.Waynode = New Waynode      ; Den ersten Wegpunkt erstellen, dies ist unser Startpunkt
      begin\X = X1
      begin\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 map( 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 map( 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 map( 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 map( 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