Binärer Baum

Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Neue Antwort erstellen

DAK

Betreff: Binärer Baum

 BeitragDo, Jan 10, 2013 10:52
Antworten mit Zitat
Benutzer-Profile anzeigen
Hier wurde letztens erwähnt, dass man da vielleicht was Schnelleres als eine Liste verwenden könnte, da ist mir aufgefallen, dass BMax als Datenstrukturen eigentlich nur eine doppeltverlinkte LinkedList und eine einzige Map unterstützt.
Beide davon eignen sich z.B. für Prioritätswarteschlangen wenig, also habe ich mal so als Übung einen Binären Baum mit Implementierung als Array geschrieben. Das Ganze schaut so aus:

BlitzMax: [AUSKLAPPEN] 
Type TBANode
	Field key:Int
	Field obj:Object
	
	Function Create:TBANode(obj:Object,key:Int)
		Local tmp:TBANode = New TBANode
		tmp.key = key
		tmp.obj = obj
		Return tmp
	End Function
End Type

Type TBinaryArrayTree
	Field array:TBANode[]
	Field fill:Int=0
	
	Function Create:TBinaryArrayTree(size:Int)
		Local bintree:TBinaryArrayTree = New TBinaryArrayTree
		bintree.array = New TBANode[size]
		Return bintree
	End Function
	
	Function CreateDefault:TBinaryArrayTree()
		Return Create(50)
	End Function
	
	Method insert(obj:Object, key:Int)
		If (fill=array.length-1) Then
			array=array[..array.length+50]
		EndIf
		array[fill] = TBANode.Create(obj,2147483647)
		fill:+1
		decreaseKey(fill-1,key)
	End Method
	
	Method remove:TBANode(i:Int)
		Local l:Int = getLastFill()
		Local tmp:TBANode = array[i]
		array[i] = array[l]
		array[l] = tmp
		array[l] = Null
		heapify(i)
		Return tmp
	End Method
	
	Method extractMin:TBANode()
		If (fill<=0) Then Return Null
		Return remove(0)
	End Method
	
	Method getMin:TBANode()
		Return array[0]
	End Method
	
	Method decreaseKey(location:Int, newkey:Int)
		If (array[location].key<newkey) Then
			Return
		EndIf
		array[location].key=newkey
		While (location>0 And array[location].key<array[parent(location)].key)
			Local tmp:TBANode = array[location]
			array[location] = array[parent(location)]
			array[parent(location)] = tmp
			location = parent(location)
		Wend
	End Method
	
	Method heapify(i:Int)
		If (array[i]=Null Or array[kleft(i)]=Null Or array[kright(i)]=Null) Then
			Return
		EndIf
		While(True)
			If Not(isHeap(kleft(i)) Or isHeap(kright(i))) Then Return
			Local x:Int=i
			If isHeap(kleft(i)) And (kleft(i) < array.length And array[kleft(i)].key < array[x].key) Then
				x = kleft(i)
			EndIf
			If isHeap(kright(i)) And (kright(i) < array.length And array[kright(i)].key < array[x].key) Then
				x = kright(i)
			EndIf
			If (x=i) Then
				Return
			EndIf
			Local tmp:TBANode = array[i]
			array[i] = array[x]
			array[x] = tmp
			i=x
		Wend
	End Method
	
	Method isHeap:Int(i:Int)
		If i>=array.length Then Return False
		If array[i]=Null Then Return False
		Return True
	End Method
	
	Method build()
		If (fill=0) Then
			Return
		EndIf
		Local i:Int
		For i = array.length/2-1 To 1 Step -1
			heapify(i)
		Next
	EndMethod
	
	Method parent:Int(i:Int)
		Return Int(Floor(Float(i-1)/2.0))
	End Method
	Method kleft:Int (i:Int)
		Return 2*i+1
	End Method
	Method kright:Int (i:Int)
		Return 2*i+2
	End Method
	Method getLastFill:Int()
		For Local i:Int=array.length-1 To 0 Step -1
			If array[i]<>Null Then Return i
		Next
	End Method
	
	Method printstruct()
		For Local i:Int=0 To array.length-1
			Local node:TBANode = array[i]
			If (node<>Null)  Then
				Print (String.fromInt(i)+":"+String(node.obj)+"/"+String.fromInt(node.key))
			Else
				'Print (String.fromInt(i)+":(null)")
			EndIf
		Next
	End Method
EndType



Will man das Testen habe ich hierzu diesen Code geschrieben:

BlitzMax: [AUSKLAPPEN] 
Local Tree:TBinaryArrayTree = TBinaryArrayTree.CreateDefault()
Tree.insert("TEST1",15)
Tree.insert("TEST2",1)
Tree.insert("TEST3",7)
Tree.insert("TEST4",4)
Tree.insert("TEST5",6)
Tree.insert("TEST6",20)
Tree.insert("TEST7",431)
Tree.insert("TEST8",112)
Tree.insert("TEST9",32)
Tree.insert("TEST10",65)
Tree.insert("TEST11",100)
Tree.insert("TEST12",99)
Tree.insert("TEST13",500)
Tree.insert("TEST14",64)
Tree.insert("TEST15",128)
Tree.build()
Tree.printstruct()

While (Tree.getMin()<>Null)
	Local node:TBANode = Tree.extractMin()
	Print ("Object with lowest key->"+String(node.obj)+"/"+String.fromInt(node.key))
	Print()
	Tree.printstruct()
Wend



Jetzt die große Frage: Wozu braucht man sowas? Die Antwort: Für den Anwender ist dieser Tree sowas Ähnliches wie eine automatisch und effizient selbst sortierende Liste.
Mittels Tree.insert(value,key) kann man neue Werte reinschreiben, die dann automatisch an der richtigen Stelle im Tree abgelegt werden.
Mit Tree.getMin() kriegt man den Value mit dem niedrigsten Key zurück.
Tree.extractMin() tut das Gleiche, nur nimmt es den niedrigsten Wert dann raus. Damit kann man den Tree von unten her abarbeiten.
Tree.remove(i) nimmt den i-ten Wert aus dem Tree heraus. Achtung: dieses i ist dabei nicht sortiert!
Tree.decreaseKey(i) setzt den Key des i-ten Werts herunter und sortiert den Tree neu. Dabei ist i auch nicht sortiert.

Vielleicht kann ja wer was damit machen.
Gewinner der 6. und der 68. BlitzCodeCompo
 

PhillipK

 BeitragDo, Jan 10, 2013 13:23
Antworten mit Zitat
Benutzer-Profile anzeigen
Edit: Habe einen fehler. Steht unten dran!

Schaut nett aus, aber ich mag das slizen des arrays nicht so.
Wäre es nicht sinnvoller exponentiell zu slicen?
BlitzMax: [AUSKLAPPEN] 
	Function CreateDefault:TBinaryArrayTree()
		Return Create(64) '<-- auf einen fixwert Binär: 0100 0000 setzen 
	End Function

	Method insert(obj:Object, key:Int)
		If (fill=array.length-1) Then
			array=array[..(array.length Shl 1)] '<--- Bit je um 1 nach links verschieben.
		EndIf
		array[fill] = TBANode.Create(obj,2147483647)
		fill:+1
		decreaseKey(fill-1,key)
	End Method


Macht in meinen augen mehr sinn:
Wer wirklich eine solche liste verwenden will, will leistung. Als beispiel: AStar wegfindung.
Regelmäßig nach 50 elementen slizen nervt da doch einfach nur Smile Denn: Allocaten des speichers kann hier ein flaschenhals sein.

Anyways, gute arbeit. Ich werds mir mal klauben wenn ich darf Razz

EDIT:

Ich habe grade aus jux nen astar damit geschrieben *grins*
Bzw ich habe den pseudo code dafür zusammengebastelt. Testen geht allerdings nicht, ich kriege einen fehler:
Code: [AUSKLAPPEN]
Unhandled Exception:Attempt to access field or method of Null object

in der Zeile:
BlitzMax: [AUSKLAPPEN] 
While (location>0 And array[location].key<array[parent(location)].key)

in der methode "decreaseKey".

Einfügen tue ich ein eigenes Objekt (TAStarNode) mit einem beliegen wert, den wegkosten entsprechend. Egal obs mit hohen oder niedriegen werten ist Very Happy

Das ganze mit einem if und einem assert zeigt:
BlitzMax: [AUSKLAPPEN] 
	Method decreaseKey(location:Int, newkey:Int)
		If (array[location].key<newkey) Then
			Return
		EndIf
		array[location].key = newkey
		
		If location <= 0 Then Return
		
		Assert array[location] <> Null, "Fehler: array[location] ist null."
		Assert array[parent(location)] <> Null, "Fehler: array[parent(location)] ist null."
		
		Print("Location: " + location)
		
		While (location>0 And array[location].key<array[parent(location)].key)
			Local tmp:TBANode = array[location]
			array[location] = array[parent(location)]
			array[parent(location)] = tmp
			location = parent(location)
		Wend
	End Method

Assert wird ausgelöst, weil array[parent(location)] = null ist. Der Location print findet NIEMALS statt, dh direkt beim (2ten?) durchlauf kommt der fehler.

Mein erstellen: (new TAStar.Create(....) -> Hier kommt es nicht zu einem fehler. Dist ist die manhatten dist zum ziel, g - Sprich mein Key - entspricht ebenfalls diesem wert.)
BlitzMax: [AUSKLAPPEN] 
		
		Self.search = New TBinaryArrayTree.Create(64)
		
		Local firstNode:TAStarNode = New TAStarNode.Create(start[0], start[1], 0, dist, Null)
		
		Self.search.insert(firstNode, firstNode.g)


Erst beim ersten durchlauf meines astar algos kommt es zu einem fehler:

BlitzMax: [AUSKLAPPEN] 
				'garnicht vorhanden?
				Else
					'ist nicht vorhanden.
					tmp = New TAStarNode.Create(x, y, node.wcosts + costs[i], Abs(ende[0] - x) + Abs(ende[1] - y) , node)
					
					search.insert(tmp, tmp.g)
					
					open[x, y] = tmp
					
					Continue
				EndIf


Dies ist der fall, wenn ein punkt weder in der offen-liste noch in der geschlossen-liste ist. Anzumerken sei auch, das ich direkt das erste eingefügte objekt wieder entferne.
Sprich: Astar wird erstellt: Ich erstelle den binary tree und füge den ersten wegpunkt ein.
Astar update entfernt nun den ersten (weil mit niedrigsten kosten) wegpunkt aus deinem tree und prüft die nachbarschaft. Ist ein punkt nicht vorhanden, wird er eingefügt und der fehler tritt auf.

Weiteres:
Ja ich schreibe viel *grins*
Aber ich hab spasseshalber mal die methode remove überarbeitet:
BlitzMax: [AUSKLAPPEN] 
	Method remove:TBANode(i:Int)
		Local l:Int = getLastFill()
		Local tmp:TBANode = array[i]
		array[i] = array[l]
		array[l] = tmp
		array[l] = Null
		heapify(i)
		fill:-1
		Return tmp
	End Method

hinzugekommen ist fill:-1.
Ob es richtig ist, kann ich nicht sagen. Ich fands nur seltsam, das beim einfügen fill:+1 gemacht wird, bei remove hingegen kein :-1.

Beim durchlaufen lassen sind eingie elemente in die liste gekommen. Ein erster fehler trat denn erst wieder bei meinem krams auf Smile

Mach was draus, vielleicht warst du nur müde? Very Happy
 

PhillipK

 BeitragDo, Jan 10, 2013 16:44
Antworten mit Zitat
Benutzer-Profile anzeigen
Entschuldigt, dieser doppelpost ist sogar absicht.

Ich bitte die Mod's, meine beiden beiträge nicht zu mergen. Vielmehr den oberen zu löschen, wenn DAK ihn gelesen und den Fehler (wenns denn einer war) überarbeitet hat. Dies hier soll nur die pure geilheit seines codes beweisen Very Happy Deshalb sollte er in meinen augen gesondert stehen.

scheinbar habe ich das Astar nun doch irgendwie hingekriegt, lag wirklich nur an dem fehler.
Um zu beweisen, wie schnell DAK's tree funktioniert, habe ich hier mal den astar, basierend auf eben jenem tree für euch.
Ob der Algo nun 100% korrekt umgesetzt ist, weiß ich nicht. Grundlegend sollte aber der AStar gedanke umgesetzt sein.

als key nehme ich immer wie potentziellen wegkosten, arbeiten tue ich immer mit extractmin() um die geschwindigkeit zu erhalten.
BlitzMax: [AUSKLAPPEN] 
SuperStrict

Local waycosts:Int[,] = New Int[Floor(1024 / 10), Floor(768 / 10)]
Local dims:Int[] = waycosts.dimensions()
Local map:Int[,] = New Int[dims[0], dims[1]]

For Local x:Int = 0 Until dims[0]
	For Local y:Int = 0 Until dims[1]
		waycosts[x, y] = 0'Rand(0, 10)
		If Rand(0, 1000) < 100 Then
			map[x, y] = 1
		ElseIf x = 0 Or y = 0 Or x = dims[0] - 1 Or y = dims[1] - 1 Then
			map[x, y] = 1
		EndIf
	Next
Next

Graphics(1024, 768)

Local entity:TEntity = New TEntity.Create(1024 / 20, 768 / 20)

Local astar:TAstar

Local mapSchwellwert:Int = 100
Local oldMapSchwellwert:Int = 100

Local useWaycosts:Int = 0

Local lastTimeTaken:Int = 0

Local pencilSize:Int = 1

While Not KeyHit(KEY_ESCAPE) And Not AppTerminate()

	mapSchwellwert:+KeyDown(KEY_UP) - KeyDown(KEY_DOWN)
	mapSchwellwert = Min(Max(mapSchwellwert, 1), 9999)

	If oldMapSchwellwert <> mapSchwellwert Then
		CreateWalls(map, mapSchwellwert)
		oldMapSchwellwert = mapSchwellwert
	End If
	
	
	If KeyHit(KEY_ENTER)
		useWaycosts = 1 - useWaycosts
		SetWaycosts(waycosts, useWaycosts)
	End If
	
	If KeyHit(KEY_BACKSPACE) ClearWalls(map)
	
	
	pencilSize:+MouseZSpeed()
	
	pencilSize = Min(Max(pencilSize, 1), 100)
	
	
	If MouseHit(1) Then 'wegfindung starten.
		'ex,ey = endpunkt. Mauskoords
		Local ex:Int = MouseX() / 10
		Local ey:Int = MouseY() / 10
		
		Local sx:Int = entity.x
		Local sy:Int = entity.y
		
		
		'astar objekt erschaffen
		astar = New TAstar.Create(map, waycosts, [sx, sy], [ex, ey], False)
		
		'zeitmessung und laufen lassen
		Local ms:Int = MilliSecs()
		astar.Update()
		lastTimeTaken = (MilliSecs() - ms)
		
	ElseIf MouseHit(2) Then
		'ex,ey = endpunkt. Mauskoords
		Local ex:Int = MouseX() / 10
		Local ey:Int = MouseY() / 10
		
		Local sx:Int = entity.x
		Local sy:Int = entity.y
		
		
		'astar objekt erschaffen
		astar = New TAstar.Create(map, waycosts, [sx, sy], [ex, ey])
		
		'zeitmessung und laufen lassen
		Local ms:Int = MilliSecs()
		astar.Update()
		lastTimeTaken = (MilliSecs() - ms)
		
	ElseIf MouseDown(3) Or KeyDown(KEY_SPACE) Then
		Local _x:Int = MouseX() / 10
		Local _y:Int = MouseY() / 10
		
		Local dims:Int[] = map.dimensions()
		
		For Local i:Int = _x - pencilSize To _x + pencilSize
			For Local j:Int = _y - pencilSize To _y + pencilSize
			
				If Pythagoras(_x, _y, i, j) <= pencilSize * 0.5 Then
					If i >= 0 And j >= 0 And i < dims[0] And j < dims[0] Then
						map[i, j] = 1
					End If
				End If
			
			Next
		Next
	EndIf
	
	'Faulheit: wenn astar fertig, dh endwaypoint <> null, und wegpunkte nochnicht überarbeitet...
	If astar And astar.endWaypoint And astar.endWaypoint.prev And astar.endWaypoint.prev._Next = Null Then

		Local n:TAStarNode = astar.endWaypoint
		Local s:TAStarNode = Null
		Local last:TAStarNode = n
		While n
			
			If last <> n Then
				n._Next = last 'dann wegpunkte umgekehrt verlinken. 
			End If
			
			last = n
			
			n = n.prev
			s = last
		Wend
	
		'Entity kriegt den zuletzt bekannten wegpunkt als "start" eingetragen.
		entity._nextWaypoint = s
	End If
	
	entity.update()
	
	Cls
	
	
	'Map zeichnung. 
	'wegkosten
	Local dims:Int[] = waycosts.dimensions()

	For Local x:Int = 0 Until dims[0]
		For Local y:Int = 0 Until dims[1]
			Local col:Int = ((waycosts[x, y] / 20.0) + 0.5) * 255
			SetColor(0, col, 0)
			DrawRect(x * 10, y * 10, 10, 10)
			
			If map[x, y] > 0 Then
				SetColor(50, 50, 50)
				DrawRect(x * 10, y * 10, 10, 10)
			End If
		Next
	Next
		
	entity.draw()
	
	SetColor(255, 255, 255)
	
	If astar And astar.endWaypoint Then

		Local n:TAStarNode = astar.endWaypoint
		
		Local last:TAStarNode = n
		While n
			
			DrawLine(n.x * 10 + 5, n.y * 10 + 5, last.x * 10 + 5, last.y * 10 + 5)
			
			last = n
			n = n.prev
			
		Wend
	
	End If
	
	
	DrawText("wand-schwellwert: " + mapSchwellwert+" - PfeilHoch / PfeilRunter um den Schwellwert zu ändern und die Wände neu zu generieren.", 5, 5)
	
	If useWaycosts Then
		DrawText("Waycost mode ist aktiv. Enter um zu togglen.", 5, 20)
	Else
		DrawText("Waycost mode ist inaktiv. Enter um zu togglen.", 5, 20)
	End If
	
	DrawText("Clearwalls mit Backspace", 5, 35)
	
	DrawText("Drücke die Linke Maustaste auf ein Feld, um die 4-Wege suche zu nutzen.", 5, 70)
	DrawText("Drücke die Rechte Maustaste auf ein Feld, um die 8-Wege suche zu nutzen.", 5, 90)
	
	DrawText("Dauer letzte suche: " + lastTimeTaken + "ms.", 5, 110)
	
	DrawText("MapDraw mit Mittlere Maustaste oder Space.", 6, 140)
	DrawText("Pencilsize aendern mit Mausrad. Current: " + pencilSize, 6, 155)
	
	Flip 1

Wend

Function ClearWalls:Int(map:Int[,])
	Local dims:Int[] = map.dimensions()
	
	For Local x:Int = 0 Until dims[0]
		For Local y:Int = 0 Until dims[1]
			If x = 0 Or y = 0 Or x = dims[0] - 1 Or y = dims[1] - 1 Then
				map[x, y] = 1
			Else
				map[x, y] = 0
			EndIf
		Next
	Next
End Function

Function CreateWalls:Int(map:Int[,], schwellwert:Int)
	
	Local dims:Int[] = map.dimensions()
	
	For Local x:Int = 0 Until dims[0]
		For Local y:Int = 0 Until dims[1]
			If Rand(0, 1000) < schwellwert Then
				map[x, y] = 1
			ElseIf x = 0 Or y = 0 Or x = dims[0] - 1 Or y = dims[1] - 1 Then
				map[x, y] = 1
			Else
				map[x, y] = 0
			End If
		Next
	Next
End Function
Function SetWaycosts:Int(waycost:Int[,], active:Int)
	Local dims:Int[] = waycost.dimensions()
	
	For Local x:Int = 0 Until dims[0]
		For Local y:Int = 0 Until dims[1]
			
			
			waycost[x, y] = Rand(0, 10) * active
			
		Next
	Next
End Function

Type TEntity
	Field x:Float
	Field y:Float
	
	Field _nextWaypoint:TAstarNode
	
	Method Create:TEntity(x:Float, y:Float)
		Self.x = x
		Self.y = y
		
		Return Self
	End Method
	Method draw()
		
		SetColor(255, 0, 0)
		DrawRect(Self.x * 10, Self.y * 10, 10, 10)
		
	End Method
	
	Method update()
		If _nextWaypoint Then
			Local ent:TVec2 = Vec2(Self.x, Self.y)
			Local aim:TVec2 = Vec2(_nextwaypoint.x, _nextwaypoint.y)
			
			Local diff:TVec2 = aim.subtract(ent)
			
			If diff.getAbsolut() <.1 Then
				_nextWaypoint = _nextWaypoint._next
				Return
			End If
			
			diff.Normalize()
			
			Self.x:+diff.getX() * 0.2
			Self.y:+diff.getY() * 0.2
			
		End If
	End Method
End Type

Function Pythagoras:Float(x1:Float, y1:Float, x2:Float, y2:Float)
	Return Sqr((x2 - x1) * (x2 - x1) + (y2 - y1) * (y2 - y1))
End Function

Type TAstar

	Field map:Int[,]
	Field waycosts:Int[,]
	
	Field start:Int[]
	Field ende:Int[]

	Field search:TBinaryArrayTree
	Field closed:TAStarNode[,]
	Field open:TAStarNode[,]
	
	Field searchDiagonal:Int = True
	
	Field dirX:Int[] = [- 1, 0, 1, 0, -1, -1, 1, 1]
	Field dirY:Int[] = [0, -1, 0, 1, -1, 1, 1, -1]
	Field costs:Int[] = [10, 10, 10, 10, 14, 14, 14, 14]
	
	Field endWaypoint:TAStarNode = Null
	
	Method Create:TAstar(map:Int[,], waycosts:Int[,], start:Int[], ende:Int[], searchDiagonal:Int = True)
		
		Self.map = map
		Self.waycosts = waycosts
		Self.start = start
		Self.ende = ende
		
		Self.searchDiagonal = searchDiagonal
		
		
		Self.search = New TBinaryArrayTree.Create(64)
		
		Local dist:Float = Abs(ende[0] - start[0]) + Abs(ende[1] - start[1]) 'manhatten distanz
		
		
		Self.search = New TBinaryArrayTree.Create(64)
		
		Local firstNode:TAStarNode = New TAStarNode.Create(start[0], start[1], 0, dist, Null)
		
		Self.search.insert(firstNode, firstNode.g)
		
		Local dims:Int[] = map.Dimensions()
		
		closed = New TAStarNode[dims[0], dims[1]]
		open = New TAStarNode[dims[0], dims[1]]
		open[start[0], start[1]] = firstNode
		
		Return Self
	End Method
	
	Method Update:TList(cnt:Int = 1000)
		
		Local node:TAStarNode
		
		Local x:Int, y:Int
		
		Local dims:Int[] = Self.map.dimensions()
		
		Local tmp:TAstarNode
		
		Local mapCost:Int = 0
		
		While Self.search.fill > 0
			node = TAStarNode(Self.search.extractMin().obj)
			
			open[node.x, node.y] = Null
			closed[node.x, node.y] = node
			
			For Local i:Int = 0 To 3 + (4 * Self.searchDiagonal)
				
				x = node.x + dirX[i]
				y = node.y + dirY[i]
				
				If ende[0] = x And ende[1] = y Then
					'endpunkt.
					endWaypoint = New TAStarNode.Create(x, y, node.wcosts + costs[i], Abs(ende[0] - x) + Abs(ende[1] - y) , node)
					Return Null
				End If
				
				'check: out of bounds?
				If x < 0 Or y < 0 Or x >= dims[0] Or y >= dims[1] Then Continue
				
				'check: wand im weg?
				If map[x, y] > 0 Then Continue
				
				'mapkosten einpflegen.
				mapCost = waycosts[x, y] * 100
				
				'ist es in der geschlossen liste?
				If closed[x, y] Then
					If node.wcosts + costs[i] + mapCost < closed[x, y].wcosts Then
						closed[x, y].prev = node
						closed[x, y].UpdateWCost(node.wcosts + costs[i] + mapCost)
					End If
		'			Print("ist geschlossen.")
					Continue
				'ist es in der offen liste?
				ElseIf open[x, y] Then
					If node.wcosts + costs[i] + mapCost < open[x, y].wcosts Then
						open[x, y].prev = node
						open[x, y].UpdateWCost(node.wcosts + costs[i] + mapCost)
					End If
		'			Print("ist offen.")
					
					Continue
				'garnicht vorhanden?
				Else
					'ist nicht vorhanden.
					tmp = New TAStarNode.Create(x, y, node.wcosts + costs[i] + mapCost, Abs(ende[0] - x) + Abs(ende[1] - y) , node)
					
					search.insert(tmp, tmp.g)
					
					open[x, y] = tmp
					
					Continue
				EndIf
			Next
			
		Wend
	End Method
		

End Type
Type TAStarNode
	
	Field x:Int
	Field y:Int
	
	Field wcosts:Int
	Field dist:Int
	Field g:Int
	
	Field prev:TAStarNode
	Field _Next:TAStarNode 'beachte: Hat keinerlei verwendungszweck für AStar. Ist nur ein kleiner faulheitsboni:
	'ist man durch mit der wegsuche, kann man anhand von "prev" die nodes andersrum verketten, um so seinem zu bewegenden objekt eine astarNode zu geben, damit er sich bewegt :)
	Method Create:TAStarNode(x:Int, y:Int, waycost:Int, distanz:Int, prev:TAStarNode)
		Self.x = x
		Self.y = y
		
		Self.wcosts = waycost
		Self.dist = distanz
		
		Self.g = waycost + distanz
		
		Self.prev = prev
		
		Return Self
	End Method
	
	Method UpdateWCost(n:Int)
		Self.wcosts = n
		Self.g = n + Self.dist
	End Method
End Type

Type TBANode
	Field key:Int
	Field obj:Object
	
	Function Create:TBANode(obj:Object,key:Int)
		Local tmp:TBANode = New TBANode
		tmp.key = key
		tmp.obj = obj
		Return tmp
	End Function
End Type

Type TBinaryArrayTree
	Field array:TBANode[]
	Field fill:Int=0
	
	Function Create:TBinaryArrayTree(size:Int)
		Local bintree:TBinaryArrayTree = New TBinaryArrayTree
		bintree.array = New TBANode[size]
		Return bintree
	End Function
	
	Function CreateDefault:TBinaryArrayTree()
		Return Create(64)
	End Function
	
	Method insert(obj:Object, key:Int)
		If (fill=array.length-1) Then
			array = array[..array.length Shl 1]
		EndIf
		array[fill] = TBANode.Create(obj,2147483647)
		fill:+1
		decreaseKey(fill-1,key)
	End Method
	
	Method remove:TBANode(i:Int)
		Local l:Int = getLastFill()
		Local tmp:TBANode = array[i]
		array[i] = array[l]
		array[l] = tmp
		array[l] = Null
		heapify(i)
		fill:-1
		Return tmp
	End Method
	
	Method extractMin:TBANode()
		If (fill<=0) Then Return Null
		Return remove(0)
	End Method
	
	Method getMin:TBANode()
		Return array[0]
	End Method
	
	Method decreaseKey(location:Int, newkey:Int)
		If (array[location].key<newkey) Then
			Return
		EndIf
		array[location].key = newkey
		
		If location <= 0 Then Return
		
		Assert array[location] <> Null, "Fehler: array[location] ist null."
		Assert array[parent(location)] <> Null, "Fehler: array[parent(location)] ist null."
		
		'Print("Location: " + location)
		
		While (location>0 And array[location].key<array[parent(location)].key)
			Local tmp:TBANode = array[location]
			array[location] = array[parent(location)]
			array[parent(location)] = tmp
			location = parent(location)
		Wend
	End Method
	
	Method heapify(i:Int)
		If (array[i]=Null Or array[kleft(i)]=Null Or array[kright(i)]=Null) Then
			Return
		EndIf
		While(True)
			If Not(isHeap(kleft(i)) Or isHeap(kright(i))) Then Return
			Local x:Int=i
			If isHeap(kleft(i)) And (kleft(i) < array.length And array[kleft(i)].key < array[x].key) Then
				x = kleft(i)
			EndIf
			If isHeap(kright(i)) And (kright(i) < array.length And array[kright(i)].key < array[x].key) Then
				x = kright(i)
			EndIf
			If (x=i) Then
				Return
			EndIf
			Local tmp:TBANode = array[i]
			array[i] = array[x]
			array[x] = tmp
			i=x
		Wend
	End Method
	
	Method isHeap:Int(i:Int)
		If i>=array.length Then Return False
		If array[i]=Null Then Return False
		Return True
	End Method
	
	Method build()
		If (fill=0) Then
			Return
		EndIf
		Local i:Int
		For i = array.length/2-1 To 1 Step -1
			heapify(i)
		Next
	EndMethod
	
	Method parent:Int(i:Int)
		Return Int(Floor(Float(i-1)/2.0))
	End Method
	Method kleft:Int (i:Int)
		Return 2*i+1
	End Method
	Method kright:Int (i:Int)
		Return 2*i+2
	End Method
	Method getLastFill:Int()
		For Local i:Int=array.length-1 To 0 Step -1
			If array[i]<>Null Then Return i
		Next
	End Method
	
	Method printstruct()
		For Local i:Int=0 To array.length-1
			Local node:TBANode = array[i]
			If (node<>Null)  Then
				Print (String.fromInt(i)+":"+String(node.obj)+"/"+String.fromInt(node.key))
			Else
				'Print (String.fromInt(i)+":(null)")
			EndIf
		Next
	End Method
EndType

Type TVec2
	Field data:Float[]
	
	Method New()
		data = New Float[2]
	End Method
	
	Method Create:TVec2(x:Float, y:Float)
		Self.data = [x, y]
		Return Self
	End Method
	Method set:TVec2(x:Float, y:Float)
		Self.data = [x, y]
		Return Self
	End Method
	Method setX:TVec2(x:Float)
		Self.data[0] = x
		Return Self
	End Method
	Method setY:TVec2(y:Float)
		Self.data[1] = y
		Return Self
	End Method
	Method getX:Float()
		Return Self.data[0]
	End Method
	Method getY:Float()
		Return Self.data[1]
	End Method
	Method get:Float[] ()
		Return Self.data[..2] 'slizen, um eine kopie zu machen. dirty, aber funktioniert ohne viel code :>
	End Method
	Method add:TVec2(toAdd:Tvec2)
		Self.data[0]:+toAdd.data[0]
		Self.data[1]:+toAdd.data[1]
		Return Self
	End Method
	Method subtract:TVec2(toSub:TVec2)
		Self.data[0]:-toSub.data[0]
		Self.data[1]:-toSub.data[1]
		Return Self
	End Method
	Method scale:TVec2(s:Float)
		Self.data[0]:*s
		Self.data[1]:*s
		Return Self
	End Method
	Method divide:TVec2(s:Float)
		If s <> 0
			Self.data[0]:/s
			Self.data[1]:/s
		EndIf
		Return Self
	End Method
	Method getAbsolut:Float()
		Return Sqr((data[0] * data[0]) + (data[1] * data[1]))
	End Method
	Method normalize:TVec2()
		Return Self.divide(Self.getAbsolut())
	End Method
	Method DotProduct:Float(toVec:Tvec2)
		Return Self.data[0] * toVec.data[0] + Self.data[1] * toVec.data[1]
	End Method
	Method getAngle:Float(toVec:TVec2)
		Return ACos(Self.DotProduct(toVec) / (Self.getAbsolut() * toVec.getAbsolut()))
	End Method
	Method getNormal:TVec2(dir:Int = 0)
		If dir Then
			Return Vec2(Self.data[1], -Self.data[0]).divide(Self.getAbsolut())
		Else
			Return Vec2(-Self.data[1], Self.data[1]).divide(Self.getAbsolut())
		End If
	End Method
	
	Method rotate:TVec2(angle:Float)
		'aktuelle drehung und länge holen:
		Local a:Float = ATan2(Self.data[1], Self.data[0])
		Local l:Float = Self.getAbsolut()
		
		'aus rotation + angle und l neue position berechnen:		
		Local v:TVec2 = vec2(Cos(a + angle) * l, Sin(a + angle) * l)
		Return v
	End Method
	Method rotateArround:TVec2(origin:TVec2, angle:Float)
		Self.subtract(origin)
		Self.rotate(angle)
		Return Self.add(origin)
	End Method
	
	Method getCopy:TVec2()
		Return Vec2(Self.data[0], Self.data[1])
	End Method
End Type


Function Vec2:TVec2(x:Float, y:Float)
	Return New TVec2.set(x, y)
End Function


Das ergebniss lässt sich sehen: Im Debug teilweise max. 100ms suchzeit. Nodebug war 3-4 ms das höchste was ich hatte!
Saubere arbeit, DAK *verneig*, ich bin froh, das du dir die mühe gemacht hast *daumen hoch*

DAK

 BeitragFr, Jan 11, 2013 16:14
Antworten mit Zitat
Benutzer-Profile anzeigen
Hey, cool, ich hätt eigentlich echt nicht erwartet, dass sich jemand für meinen Code interessieren wird, geschweige denn etwas daraus machen würde! Danke für das Lob^^
Der A* ist aber auch sehr schön gemacht. Ich habs echt versucht, aber länger als 10ms im Nodebug is es nicht geworden.

Zum Slicen: Ist natürlich schöner so, wie du's gelöst hast, hast du recht. Die Quelle von der ich mir die Struktur des BinaryArrayTrees geholt hab (Wiki-Pseudocode Wink ), die hätte sogar bei jedem einzelnen Mal, wo etwas dazugekommen oder weggenommen worden wäre, gesliced.

Du hast auch recht mit dem Remove, da hab ich das Fill-:1 auch glatt vergessen. Danke!

Ich frage mich, ob es sinnvoll wäre, beim Remove auch "herunterzuslicen", wenn das Array zu wenig gefüllt ist. Bin mir nicht sicher, ob das dann aber wieder zu viel Zeit braucht. Ich mein, selbst die JavaVM gibt RAM, den sie mal hat, nicht mehr her.

Den DecreaseKey-Bug werde ich mir anschauen, wenn ich etwas mehr Zeit habe (oder hast du den schon gelöst, bei deinem A*-Programm?). Dann werde ich deine Änderungen auch in den ersten Post einfügen, wenn das ok ist für dich.


Falls Interesse besteht, könnte ich auch noch ein paar andere schön schnelle Datenstrukturen zusammenschreiben.
Gewinner der 6. und der 68. BlitzCodeCompo
 

PhillipK

 BeitragFr, Jan 11, 2013 18:14
Antworten mit Zitat
Benutzer-Profile anzeigen
Hallo DAK!
Du, ich habe leider soviel ahnung von solchen trees wie .. naja einfach garkeine. Im groben weiß ich, was stattfindet.
Im AStar ding hab ich einfach mal nach gutdünken das -1 eingefügt. Mehr nicht.
Dh einzige änderungen bei mir: Defaultgröße ist 64, das slicen findet per shl 1 statt. Beim remove wird fill wieder runtergezählt.
Habe versucht, das ganze zu verstehen, aber hab bisher lediglich rausgefunden, das fill die anzahl der objekte angibt, von daher schien es mir logisch, das runtergezählt werden müsste.
Das ist dein baby, das musst du fixen Very Happy
Einen bug in DecreaseKey konnte ich nicht finden - was meinst du damit?

Ich würde mich über weitere Listen freuen. Je mehr unterschiedliche umsetzungen ich testen kann, desto besser. Aber leider habe ich nie eine gute liste schreiben können, bin dafür wohl zu doof *grins*
Mein jetziges problem ist zb, das ich einen haufen linien gegeneinander vergleichen muss - per line intersect. Eine liste, welche nach koordinaten sortiert ist und trotzdem dynamischer wie ein array, wäre zb praktisch Razz So könnte ich meinen schattenwurf schön in echtzeit schreiben *grins*


Ps: Die schnelligkeit des AStar kommt och nur wegen deinem BinaryTree, sei dir dessen bewusst Wink Der wirkliche speedkiller beim AStar ist die liste, aus welcher man den potentiell "günstigsten" knoten zum ziel rausholt und weiterprüft. DH wenn man erst eine ganze liste abklappern muss, dauerts eben, weil gut 400 elemente drin sein können, die pro durchlauf einmal durchlaufen werden. Fand ichn prima test für deine liste Razz

DAK

 BeitragSa, Jan 12, 2013 0:42
Antworten mit Zitat
Benutzer-Profile anzeigen
PhillipK hat Folgendes geschrieben:

EDIT:

Ich habe grade aus jux nen astar damit geschrieben *grins*
Bzw ich habe den pseudo code dafür zusammengebastelt. Testen geht allerdings nicht, ich kriege einen fehler:
Code: [AUSKLAPPEN]
Unhandled Exception:Attempt to access field or method of Null object

in der Zeile:
BlitzMax: [AUSKLAPPEN] 
While (location>0 And array[location].key<array[parent(location)].key)

in der methode "decreaseKey".

Einfügen tue ich ein eigenes Objekt (TAStarNode) mit einem beliegen wert, den wegkosten entsprechend. Egal obs mit hohen oder niedriegen werten ist Very Happy

Das ganze mit einem if und einem assert zeigt:
BlitzMax: [AUSKLAPPEN] 
	Method decreaseKey(location:Int, newkey:Int)
		If (array[location].key<newkey) Then
			Return
		EndIf
		array[location].key = newkey
		
		If location <= 0 Then Return
		
		Assert array[location] <> Null, "Fehler: array[location] ist null."
		Assert array[parent(location)] <> Null, "Fehler: array[parent(location)] ist null."
		
		Print("Location: " + location)
		
		While (location>0 And array[location].key<array[parent(location)].key)
			Local tmp:TBANode = array[location]
			array[location] = array[parent(location)]
			array[parent(location)] = tmp
			location = parent(location)
		Wend
	End Method

Assert wird ausgelöst, weil array[parent(location)] = null ist. Der Location print findet NIEMALS statt, dh direkt beim (2ten?) durchlauf kommt der fehler.

Mein erstellen: (new TAStar.Create(....) -> Hier kommt es nicht zu einem fehler. Dist ist die manhatten dist zum ziel, g - Sprich mein Key - entspricht ebenfalls diesem wert.)
BlitzMax: [AUSKLAPPEN] 
		
		Self.search = New TBinaryArrayTree.Create(64)
		
		Local firstNode:TAStarNode = New TAStarNode.Create(start[0], start[1], 0, dist, Null)
		
		Self.search.insert(firstNode, firstNode.g)


Erst beim ersten durchlauf meines astar algos kommt es zu einem fehler:

BlitzMax: [AUSKLAPPEN] 
				'garnicht vorhanden?
				Else
					'ist nicht vorhanden.
					tmp = New TAStarNode.Create(x, y, node.wcosts + costs[i], Abs(ende[0] - x) + Abs(ende[1] - y) , node)
					
					search.insert(tmp, tmp.g)
					
					open[x, y] = tmp
					
					Continue
				EndIf


Dies ist der fall, wenn ein punkt weder in der offen-liste noch in der geschlossen-liste ist. Anzumerken sei auch, das ich direkt das erste eingefügte objekt wieder entferne.
Sprich: Astar wird erstellt: Ich erstelle den binary tree und füge den ersten wegpunkt ein.
Astar update entfernt nun den ersten (weil mit niedrigsten kosten) wegpunkt aus deinem tree und prüft die nachbarschaft. Ist ein punkt nicht vorhanden, wird er eingefügt und der fehler tritt auf.



Das ist, worauf ich mich beziehe. Ich muss zugeben, ich bin mir nicht sicher, was sich da genau als Fehler tut. Kannst du mir vielleicht einen Code geben, der den Fehler reproduziert, damit ich ihn mir im Debug anschauen kann? Das wär echt nett.

Zu deinem anderen Linienproblem: 2D oder 3D?
Gewinner der 6. und der 68. BlitzCodeCompo
 

PhillipK

 BeitragSa, Jan 12, 2013 8:35
Antworten mit Zitat
Benutzer-Profile anzeigen
hier, auf die schnelle gebastelt. Scheint wirklich am "fill:-1" gelegen zu haben Smile
BlitzMax: [AUSKLAPPEN] 
SuperStrict

Const TO_INSERT:Int = 100

'Ich tue einfach mal so, als wäre das ein AStar *grins* Prinzipiell gehe ich so vor, wie es mein AStar getan hat:

Local binTree:TBinaryArrayTree = TBinaryArrayTree.Create(64)
Local startPunkt:String = "BinStartpunkt"

'anfangs kam genau 1 punkt rein. Faken wir das mal :)
binTree.insert(startPunkt, Rnd(40, 100))


'nun eine schleife, die solange arbeitet, bis binTree "leer" ist.
Local _cnt:Int = 0


Local _content:String
While binTree.fill > 0
	'while of death - check: Extra nicht in While <condition>.
	If _cnt > TO_INSERT Then Exit
	_cnt:+1
	
	_content = String(binTree.extractMin().obj)
	
	'...
	'blabla, Astar abfrage, unnötig für den code
	'...
	
	binTree.insert("BinPoint" + Rand(10, 100), Rnd(10, 100))
	

Wend



Type TBANode
	Field key:Int
	Field obj:Object
	
	Function Create:TBANode(obj:Object,key:Int)
		Local tmp:TBANode = New TBANode
		tmp.key = key
		tmp.obj = obj
		Return tmp
	End Function
End Type

Type TBinaryArrayTree
	Field array:TBANode[]
	Field fill:Int=0
	
	Function Create:TBinaryArrayTree(size:Int)
		Local bintree:TBinaryArrayTree = New TBinaryArrayTree
		bintree.array = New TBANode[size]
		Return bintree
	End Function
	
	Function CreateDefault:TBinaryArrayTree()
		Return Create(50)
	End Function
	
	Method insert(obj:Object, key:Int)
		If (fill=array.length-1) Then
			array=array[..array.length+50]
		EndIf
		array[fill] = TBANode.Create(obj,2147483647)
		fill:+1
		decreaseKey(fill-1,key)
	End Method
	
	Method remove:TBANode(i:Int)
		Local l:Int = getLastFill()
		Local tmp:TBANode = array[i]
		array[i] = array[l]
		array[l] = tmp
		array[l] = Null
		heapify(i)
		Return tmp
	End Method
	
	Method extractMin:TBANode()
		If (fill<=0) Then Return Null
		Return remove(0)
	End Method
	
	Method getMin:TBANode()
		Return array[0]
	End Method
	
	Method decreaseKey(location:Int, newkey:Int)
		If (array[location].key<newkey) Then
			Return
		EndIf
		array[location].key=newkey
		While (location>0 And array[location].key<array[parent(location)].key)
			Local tmp:TBANode = array[location]
			array[location] = array[parent(location)]
			array[parent(location)] = tmp
			location = parent(location)
		Wend
	End Method
	
	Method heapify(i:Int)
		If (array[i]=Null Or array[kleft(i)]=Null Or array[kright(i)]=Null) Then
			Return
		EndIf
		While(True)
			If Not(isHeap(kleft(i)) Or isHeap(kright(i))) Then Return
			Local x:Int=i
			If isHeap(kleft(i)) And (kleft(i) < array.length And array[kleft(i)].key < array[x].key) Then
				x = kleft(i)
			EndIf
			If isHeap(kright(i)) And (kright(i) < array.length And array[kright(i)].key < array[x].key) Then
				x = kright(i)
			EndIf
			If (x=i) Then
				Return
			EndIf
			Local tmp:TBANode = array[i]
			array[i] = array[x]
			array[x] = tmp
			i=x
		Wend
	End Method
	
	Method isHeap:Int(i:Int)
		If i>=array.length Then Return False
		If array[i]=Null Then Return False
		Return True
	End Method
	
	Method build()
		If (fill=0) Then
			Return
		EndIf
		Local i:Int
		For i = array.length/2-1 To 1 Step -1
			heapify(i)
		Next
	EndMethod
	
	Method parent:Int(i:Int)
		Return Int(Floor(Float(i-1)/2.0))
	End Method
	Method kleft:Int (i:Int)
		Return 2*i+1
	End Method
	Method kright:Int (i:Int)
		Return 2*i+2
	End Method
	Method getLastFill:Int()
		For Local i:Int=array.length-1 To 0 Step -1
			If array[i]<>Null Then Return i
		Next
	End Method
	
	Method printstruct()
		For Local i:Int=0 To array.length-1
			Local node:TBANode = array[i]
			If (node<>Null)  Then
				Print (String.fromInt(i)+":"+String(node.obj)+"/"+String.fromInt(node.key))
			Else
				'Print (String.fromInt(i)+":(null)")
			EndIf
		Next
	End Method
EndType


Dreckig, hässlich, tut seinen job. Oder eben nicht:
Ich bin vorgegangen wie in der AStar sache. Ein punkt rein, dann solange noch was drin ist, immer einen rausholen und was machen.
Hier tue ich allerdings nichts weiter wie:
Punkt rausholen, punkt reinstecken (mit einer kleinen _cnt variable um eine while of death zu vermeiden!)

Der fehler tritt wieder auf Smile

Ändert man die remove methode von dir wie folgt:
BlitzMax: [AUSKLAPPEN] 
	Method remove:TBANode(i:Int)
		Local l:Int = getLastFill()
		Local tmp:TBANode = array[i]
		array[i] = array[l]
		array[l] = tmp
		array[l] = Null
		fill:-1
		heapify(i)
		Return tmp
	End Method

Funktioniert es. Bitte überprüfe das ganze nocheinmal bitte Smile
(ps: grade bei der removemethode.. array[i] =array[l] - array L neu belegen - array L = null. Hm, verquer gedacht? Razz )

Das ich gefragt habe, worauf du dich beziehst, war dumm - hätte mir klar sein sollen hihi. War wohl "leicht" übermüdet gestern ^^

(liniensache:
Wird zwar eine pseudo3d umgebung, aber die koordinaten in 2d reichen *grins*)

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Codearchiv & Module

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group