SuperStrict

Graphics 1000, 1000

' Die Map erzeugen
Global map:Byte[,] = New Byte[100, 100]
For Local x:Int = 0 To 99
	For Local y:Int = 0 To 99
		If (Rand(0, 4) = 0) Then
			map[x, y] = True
		End If
	Next
Next

Global aStar:TAStar = TAStar.Create(map, 100, 100)

While Not KeyDown(KEY_ESCAPE)
	Cls
		Local s:Int = MilliSecs()
		DrawMap()
		SetColor(0, 255, 0)
		aStar.FindWay(0,0,MouseX() / 10, MouseY() / 10)
		'Print GCMemAlloced()
		SetColor(255, 255, 255)
		DrawText(MilliSecs() - s, 0, 0)
	Flip
Wend

' Zeichnet die Map
Function DrawMap()
	SetColor(255, 255, 255)
	For Local x:Int = 0 To 99
		For Local y:Int = 0 To 99
			If (map[x, y] <> 0) Then
				DrawRect(x * 10, y * 10, 10, 10)
			End If
		Next
	Next
End Function

' A* Klasse (nur für 2D Maps)
Type TAStar
	Field startX:Int' Hier beginnt die Suche
	Field startY:Int' Hier beginnt die Suche
	Field endX:Int' Hier endet die Suche
	Field endY:Int' Hier endet die Suche
	Field collisionMap:Byte[,]' Speichert die Kollisionsmatrix
	Field jointMap:TAStarJoint[,]' Speichert die Knotenpunkte
	Field mapSizeX:Int
	Field mapSizeY:Int
	Field openList:TList' Die offene Liste
	Field closedList:TList' Die geschlossene Liste
	Field currentJoint:TAStarJoint' Gibt immer den momentanen Knotenpunkt an
	
	' Erstellt eine neue A* Instanz
	Function Create:TAStar(collisionMap:Byte[,], mapSizeX:Int, mapSizeY:Int)
		Local aStar:TAStar = New TAStar
		aStar.collisionMap = collisionMap
		aStar.mapSizeX = mapSizeX
		aStar.mapSizeY = mapSizeY
		aStar.openList = CreateList()' Die offene Liste erstellen
		aStar.closedList = CreateList()' Die geschlossene Liste erstellen
		Return aStar
	End Function
	
	' Versucht den Weg vom Start zum Zielpunkt zu finden
	Method FindWay(startX:Int, startY:Int, endX:Int, endY:Int)
		' Initialisierungsphase
		Self.startX = endX
		Self.startY = endY
		Self.endX = startX
		Self.endY = startY
		Self.jointMap = New TAStarJoint[Self.mapSizeX, Self.mapSizeY]' Die Knotenmatrix erstellen
		If (Self.collisionMap[endX, endY] = True) Then
			Return
		End If
		Self.currentJoint = TAStarJoint.Create(Self, Null, Self.startX, Self.startY)' Der Starknoten hat keinen Vorgänger
		Self.openList.AddLast(Self.currentJoint)' Den Anfangspunkt ganz normal in die offene Liste eintragen
		' Beginn des A* Algorithmus
		Self.currentJoint.GetAdjacentJoints()' Anliegende Knoten untersuchen
		Self.currentJoint.Close()' Den momentanen Knotenpunkt in die geschlossene Liste verschieben
		' Jetzt als nächsten momentanen Punkt den mit den niedrigsten F - Kosten wählen
		While (True)
			If (Self.openList.IsEmpty() = True) Then
				Exit
			End If
			Self.currentJoint = TAStarJoint(Self.openList.First())
			Self.currentJoint.Close()' Den momentanen Knotenpunkt in die geschlossene Liste setzen
			Self.currentJoint.GetAdjacentJoints()' Anliegende Knotenpunkte suchen
			
			' Debug
			'Print currentJoint.x + "|" + currentJoint.y + " - " + currentJoint.fCosts + " - " + currentJoint.gCosts + " - " + currentJoint.hCosts
		
			If (Self.currentJoint.x = Self.endX And Self.currentJoint.y = Self.endY) Then
				Exit
			End If
		Wend
		' Jetzt den Pfad zurückberechnen
		Local searchJoint:TAStarJoint = currentJoint
		While (True)
			DrawRect(searchJoint.x * 10, searchJoint.y * 10, 10, 10)
			If (searchJoint.parentJoint = Null) Then
				Exit
			Else
				searchJoint = searchJoint.parentJoint
			End If
			'Print searchJoint.x + "|" + searchJoint.y
		Wend
		Self.jointMap = Null
		Self.openList.Clear()
		Self.closedList.Clear()
	End Method
	
	' Fügt den Knotenpunkt zur offenen Liste hinzu
	Method AddToOpenList(joint:TAStarJoint)
		Self.jointMap[joint.x, joint.y] = joint
		' Automatisch richtig einordnen, der Knotenpunkt mit den kleinsten F Wert ist immer der erste in der Liste
		For Local searchJoint:TAStarJoint = EachIn Self.openList
			If (joint.fCosts <= searchJoint.fCosts) Then
				Self.openList.InsertBeforeLink(joint, Self.openList.FindLink(searchJoint))
				Return
			End If
		Next
		Self.openList.AddLast(joint)
	End Method
End Type

' Ein vom A* verwendeter Knotenpunkt
Type TAStarJoint
	Field aStar:TAStar
	Field parentJoint:TAStarJoint' Die
	Field x:Int
	Field y:Int
	Field fCosts:Int' Die F - Kosten
	Field gCosts:Int' Die G - Kosten
	Field hCosts:Int' Die K - Kosten
	Field inOpenList:Byte = False' Gibt an ob sich der Punkt in der offenen Liste befindet
	Field inClosedList:Byte = False' Gibt an ob sich der Punkt in der geschlossenen Liste befindet
	
	' Erstellt einen neuen Knotenpunkt
	Function Create:TAStarJoint(aStar:TAStar, parentJoint:TAStarJoint, x:Int, y:Int)
		Local joint:TAStarJoint = New TAStarJoint
		joint.aStar = aStar
		joint.parentJoint = parentJoint
		joint.x = x
		joint.y = y
		Return joint
	End Function
	
	' Sucht anliegene Knotenpunkte
	Method GetAdjacentJoints()
		Self.GetJoint(Self.x - 1, Self.y)
		Self.GetJoint(Self.x + 1, Self.y)
		Self.GetJoint(Self.x, Self.y - 1)
		Self.GetJoint(Self.x, Self.y + 1)
	End Method
	
	' Versucht den Punkt an dieser Stelle in die offene Liste aufzunehmen
	Method GetJoint(x:Int, y:Int)
		' Prüfen ob der Punkt überhaupt in der Map liegt
		If (x >= 0 And x < Self.aStar.mapSizeX And y >= 0 And y < Self.aStar.mapSizeY) Then
			' Der Punkt befindet sich in der Map, doch ist er auch begehbar?
			If (Self.aStar.collisionMap[x, y] = False) Then
				' Der Punkt ist begehbar, doch er darf nicht bereits in der offenen oder geschlossenen Liste sein
				If (Self.aStar.jointMap[x, y] = Null) Then
					Self.inOpenList = True
					' Jetzt eine Knotenpunkt Instanz dieses Punktes erstellen
					Local joint:TAStarJoint = TAStarJoint.Create(Self.aStar, Self, x, y)
					joint.CalculateCosts()
					Self.aStar.AddtoOpenList(joint)' Den Knotenpunkt in die offene Liste eintragen
				Else If (Self.aStar.jointMap[x, y].inOpenList = True) Then
					'DebugSTop
				End If
			End If
		End If
	End Method
	
	' Berechnet die Kostendaten dieses Punktes
	Method CalculateCosts()
		Self.gCosts = Self.parentJoint.gCosts + 10
		Self.hCosts = (Abs(Self.x - Self.aStar.endX) + Abs(Self.y - Self.aStar.endY)) * 10
		Self.fCosts = Self.gCosts + Self.hCosts
	End Method
	
	' Verschiebt den Punkt in die geschlossene Liste
	Method Close()
		Self.inOpenList = False
		Self.inClosedList = True
		Self.aStar.openList.Remove(Self)
		Self.aStar.closedList.AddLast(Self)
	End Method
End Type