...

     For Local i:Int = 0 To 7
       Local x:Int = nod.x + dirx[i]
       Local y:Int = nod.y + diry[i]
      
       If x >= 0 And y >= 0 And x < mapwidth And y < mapheight
         If map[x,y] = 0 And nodemap[x,y] = 0
'           If dirz[i] = 1
             If map[x,nod.y] <> 1 And map[nod.x,y] <> 1                
                 tempnode:TNodes      = New TNodes
                 tempnode.parent      = nod
                 tempnode.cost         = nod.cost + 1
                 tempnode.x            = x
                 tempnode.y            = y
                
                 n_open:TOpen         = New TOpen
                 n_open.nod            = tempnode
                 nodemap[x,y]         = 1
                
                 If x = endx And y = endy Then ende = True; Exit
             EndIf
'           EndIf
         EndIf
       EndIf
     Next

...

Type TMap
   
   'Daten:
   Field Map:Int[1,1,1]    'die Karte: b*h*layer, wobei aus performancegründen l,h,w gespeichert wird, da
   Field width:Int         'dann die einzelnen Layerdaten hintereinander im Speicher stehen.
   Field height:Int
   Field layer:Int
   
   'Globale Daten:
   Global Lmap:TList = CreateList()
   
   'Funktionen:
   Function Create:Tmap(w:Int,h:Int,l:Int)
      'erstellt eine neue Karte in den angegebenen Dimensionen. Sie wird in Lmap gespeichert.
      Local instanz:tmap = New tmap
      instanz.map = New Int[l,h,w]
      instanz.width = w
      instanz.height = h
      instanz.Layer = l
      ListAddLast lmap,instanz
      Return instanz
   End Function
   
   'Methoden:
   Method resize(w:Int,h:Int,l:Int)
      'redimensioniert eine Karte. Der Inhalt wird soweit möglich erhalten.
      Local copyi:Int,copyj:Int,copyk:Int
      If w >= self.width Then
         copyi = self.width
         Else
         copyi = w
      EndIf
      If h >= self.height Then
         copyj = self.height
         Else
         copyj = h
      EndIf
      If l >= self.layer Then
         copyk = self.layer
         Else
         copyk = l
      EndIf            
      Local tempmap:Int[copyk,copyj,copyi]

      For Local i:Int = 0 To copyi -1
         For Local j:Int = 0 To copyj -1
            For Local k:Int = 0 To copyk-1
               tempmap[k,j,i]=self.map[k,j,i]
            Next
         Next
      Next
         
      self.map = New Int[l,h,w]
      self.width = w
      self.height = h
      self.Layer = l
      
      For i:Int = 0 To copyi -1
         For j:Int = 0 To copyj -1
            For k:Int = 0 To copyk-1
               self.map[k,j,i]=tempmap[k,j,i]
            Next
         Next
      Next
   
   End Method
   
   Method getvalue(w:Int,h:Int,l:Int)
      'liesst den Wert aus der angegebenen Zelle
      If (w >=0) And (w < self.width) And (h >=0) And (h <self.height) And (l >=0) And (l<self.layer) Then
         Return self.map(l,h,w)
      Else
         RuntimeError "Unable to perform 'Read' on 'Map':Index out of Bounds"
      EndIf
      
   End Method
   
   Method setvalue(w:Int,h:Int,l:Int,value:Int)
      'setzt den Wert in die angegebene Zelle
      If (w >=0) And (w < self.width) And (h >=0) And (h <self.height) And (l >=0) And (l<self.layer) Then
         self.map(l,h,w) = value
      Else
         RuntimeError "Unable to perform 'Write' on Map:Index out of Bounds"
      EndIf
   End Method
   
   Method fill(value:Int)
      'füllt die Map mit einem Wert
      For Local i:Int = 0 To self.width -1
         For Local j:Int = 0 To self.height -1
            For Local k:Int = 0 To self.layer -1
               self.map(k,j,i) = value
            Next
         Next
      Next   
   End Method

   Method filllayer(l:Int,value:Int)
      'füllt einen layer mit einem Wert
      If l < self.layer Then
         For Local i:Int = 0 To self.width -1
            For Local j:Int = 0 To self.height -1
               self.map(l,j,i) = value
            Next
         Next
      EndIf      
   End Method
   
   Method destroy:TMap()
      'zerstört die aktuelle Karteninstanz
      ListRemove lMap,Self
      Return Null
   End Method
   
   Method draw()
      'vorläufige Implementierung für Testzwecke Astar
      Local i:Int,j:Int,k:Int
      For i = 0 To self.width-1
         For j = 0 To self.height-1
            For k = 0 To self.layer-1
               If self.map(k,j,i) = 1 Then
                  SetColor 155+10*k,0,0
               Else
                  SetColor 100+10*k,100+10*k,100+10*k
               EndIf
               DrawRect i*30,j*30,25-(k*3),25-(k*3)
            Next
         Next
      Next   
   End Method
   
End Type
'____________________________________________________________________________________________________

'____________________________________________________________________________________________________
Type TNode
   
   'Daten:
   Field lastnode:TNode
   Field x:Int,y:Int
   Field cost:Float, aprox:Float
   
   'Globale Daten:
   Global LOpen:TList = CreateList()
   Global LClose:TList = CreateList()
   
   'Funktionen:
   Function Create:TNode()
      'erstellt einen neuen Knoten.
      Local instanz:TNode = New TNode
      Return instanz
   End Function
   
   Function clear()
      'löscht die Offene und die geschlossene Liste
      ClearList LOpen
      ClearList LClose
   End Function
   
   Function draw(ldraw:TList)
      'zeichnet den Weg der gefunden wurde ein. Testimplementierung.
      SetColor 0,0,200
      If ldraw = Null Then Return
      For Local drawnode:tnode = EachIn Ldraw
         DrawRect drawnode.x*30+10,drawnode.y*30+10,10,10
      Next
   End Function
   
   Function AStar8:TList(startX:Int,startY:Int,targetX:Int,targetY:Int,map:TMap,layer:Int = 0,block:Int = 1,Returnnearest:Int = False)
      'Der AStar-Algo für 8 Richtungen. Block gibt an welcher Karteneintrag für blockerte Wege
      'gilt, Map ist die Karte die für die Wegfindung benutzt wird.
      
      TNode.clear()   'die Listen werden gesäubert
      Local Start:Tnode= TNode.create()   'Der Startpunkt wird erschaffen
      start.setcoords(startx,starty)      'Die Startkoorinaten werden eingetragen
      start.addopen()                  'und der Startpunkt wird auf die offene Liste gesetzt.
      start.cost = 0

      Target:Tnode = TNode.create()      'das Ziel wird erschaffen
      Target.setcoords(targetX,targety)   'und mit Koordinaten versehen
      start.aprox = Sqr((target.x-start.x)^2+(target.y-start.y)^2)   'Kostenschätzung Startfeld
      
      Local search:Tnode = start   'nun beginnt der Reigen: Start ist der erste untersuchte Knoten
      Local done:Int = False      'Noch kein Ziel gefunden
      Local donenode:tnode      'Nodeinstanz für das Zielfeld
      While (Not done) And (Not ListIsEmpty(LOpen)) 'solange es noch offene Knoten zum untersuchen gibt
         search.close()   'die aktuelle Node wird bearbeitet und ist daher geschlossen
         For Local x = -1 To 1   'untersuche die umliegenden Felder
            For Local y = -1 To 1
               Local tempx:Int = search.x+x
               Local tempy:Int = search.y+y
               If tempx = target.x And tempy = target.y Then   'Ziel gefunden ?
                  done = True 'Ziel gefunden !
                  donenode = tnode.create()   'nun wird donenode erschaffen
                  donenode.lastnode=search   'und der letzte schritt dort hin gespeichert
                  donenode.setcoords(tempx,tempy)
               EndIf
               If (tempx >=0) And (tempx < map.width) And (tempy>=0) And (tempy<map.height) Then   'gültige Kartenposition?
                  If (x + 2*y) Then 'falls nicht der Mittelpunkt (ist nur 0 wenn beide Komponenten es sind)
                     Local tempfound:Int = False   'das untersuchte Feld ist noch nicht in der Liste der offenen Felder ?
                     For Local secsearch:Tnode = EachIn LOpen
                        If (secsearch.x = tempx) And (Secsearch.y=tempy) Then
                           tempfound = True 'doch, ist es
                        EndIf
                     Next
                     For secsearch:Tnode = EachIn LClose   'und bei den geschlossenen vielleicht ?
                        If (secsearch.x = tempx) And (Secsearch.y=tempy) Then   
                           tempfound = True   'doch, ist es
                        EndIf
                     Next
                     If (tempfound = False) And (map.getvalue(tempx,tempy,layer) <> block) Then   'wenn der Knoten noch nicht bekannt war
                        Local node:Tnode = TNode.create()   'dann ist er es jetzt
                        Node.setcoords(tempx,tempy)   'wo ist er
                        node.lastnode = search   'von wo wurde er erreicht ?
                        node.addopen()   'ab auf die Liste der zu bearbeitenden Knoten
                        node.cost = search.cost +Sqr(Abs(x)+Abs(y))   'wie teuer war es her zu kommen (es werden für Diagonalen mehr berechnet.) ?
                        node.aprox = Sqr((target.x-node.x)^2+(target.y-node.y)^2)   'wie lautet die Schätzung für den Rest der Strecke ?
                     EndIf
                  EndIf
               EndIf
               
            Next
         Next
         Local mincost:Float =$7fffffff   'setze die Kosten auf ein maximum   
         For secsearch:Tnode = EachIn LOpen'nun suche in der Offenen Liste nach dem Knoten mit den geringsten zu erwartenden Gesamtkosten
            If secsearch.cost + secsearch.aprox < mincost Then
               search = secsearch   'dieser ist dann der nächste Suchknoten für Astar und wird beim nächsten durchlauf auf die geschlossene gesetzt.
               mincost = secsearch.cost+secsearch.aprox
            End If
         Next   
      Wend
      'dieser Teil wird abgearbeitet wenn: a) der Zielknoten erreicht wurde oder
                                 'b) kein offener Knoten mehr existiert, d.h. das Ziel nicht
                                 'erreicht werden kann.
      If (Returnnearest = True) And (done = False)  Then   'soll der nächstmöglichste Punkt zurückgegeben werden ?
         mincost= $7fffffff
         For secsearch:Tnode = EachIn LClose   'dann suche in der geschlossenen Liste den Punkt mit den niedrigsten geschätzten Restkosten
            If secsearch.aprox < mincost Then
               donenode = secsearch
               mincost = secsearch.aprox
            End If
         Next
      EndIf   
      
      If donenode <> Null Then   'wenn es ein Ziel gibt, erstelle die Liste mit den Wegpunkten
         Local Lreturn:TList = CreateList()
         Local loop:TNode = Donenode
         Repeat
            ListAddFirst Lreturn,loop
            loop = loop.lastnode
         Until loop = start
         ListAddFirst Lreturn,loop   'optional, so wird der Sartpunkt auch als wegpunkt übergeben.
         Return LReturn
      Else                  'wenn es kein Ziel gibt, gebe eine undefinierte Liste zurück
         Return Null
      EndIf
      
   End Function
   
   'Methoden:
   Method Addopen()
      'fügt die Instanz der Suchliste hinzu.
      ListAddLast LOpen, Self
   End Method
   
   Method Close()
      'entfernt die Instanz von der Offenen Liste und setzt sie auf die geschlossene Liste
      If ListContains (LOpen,Self) Then
         ListRemove LOpen,Self
         ListAddLast LClose,Self
      EndIf      
   End Method
   
   Method setcoords(x:Int,y:Int)
      'Koordinaten einer Node festlegen
      self.x = x
      self.y = y
   End Method
   
End Type

'___________________________________________________________________________________________________

'Rem TESTCODE
   test:tmap = tmap.create(15,15,1)
   AppTitle="A* Demo V1.0 ~t~~BladeRunner~~"
   Graphics 640,480
   
   Repeat
      Local mx:Int = MouseX()
      Local my:Int = MouseY()
      mbl:Int = MouseHit(1)
      mbr:Int = MouseHit(2)
      If mbl Then
         test.setvalue(mx/30,my/30,0,1)
      EndIf
      If mbr Then
         test.setvalue(mx/30,my/30,0,0)
      EndIf
      
      ldraw:TList=Tnode.astar8(0,0,3,14,test,,,True)
      test.draw()
      TNode.draw(ldraw)
      DrawText GCMemAlloced(),500,460
      Flip
      Cls
   Until KeyHit(KEY_ESCAPE) Or AppTerminate()   
'EndRem