A* algorythmus - Speed vs Speicher - wie vorgehen? :)

Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Neue Antwort erstellen

 

PhillipK

Betreff: A* algorythmus - Speed vs Speicher - wie vorgehen? :)

 BeitragFr, Okt 07, 2011 12:46
Antworten mit Zitat
Benutzer-Profile anzeigen
Nachtrag:
Ich liste hier mal meine Fragen auf, da die im Text untergegangen sind glaube ich *g* (und noch ein wenig erweitert!)

(1) Wäre jemand so freundlich mein TAStern2d - objekt durchzuschauen?
Ich weiß nicht recht, ob ich das speichern der Offenen und geschlossenen einträge so lassen kann. Wenn 20 Wegfindungen vorhanden sind, und immer nur die erste bearbeitet wird, könnte es sau lange dauern.
Alle gleichzeitig abzuarbeiten würde aber den RAM sprengen. Ich bin mir ein wenig unsicher ^^

(2) Läuft die Wegfindung bei euch flüssig, wenn ihr beide Quellcodes in ein Programm werft und per Linksklick die Unit rumschickt?

(3) Ist der Algorythmus richtig umgesetzt? Ist das wirklich A* ?Smile Funktionieren tut er super (siehe Screenshot)

(4) Gibt es eine bessere Methode, die "Offenen" einträge zu speichern, als in einer TList? Geschwindigkeit und Ramverbrauch sind seeeehr wichtig für mein vorhaben!

(5) Sind die abfragen soweit richtig sortiert, oder wäre es Chronologisch sinnvoller, die abbruchsbedingungen im AStern - Knotencheck (prüfung, ob ein Knoten bereits irgendwo bearbeitet wurde!) anders zu sortieren? Wieder: Performance ist sehr wichtig!

(6) Kann ich eventuell etwas Ressourcenarmeres nutzen, um die TKnoten zu sortieren? Vielleicht sogar einzelwerte? Ich sehe ein TKnoten leider als beste methode momentan, aber die zwingt mich zur TList (und die ist beim Iterieren ja nicht grade die schnellste :<) Vielleicht doch lieber eine Art array mit festgelegter Größe?

Hoffentlich gibts antworten *g*

-------------------

Heyho!
Ich habe mich die letzten 2 Tage mit einem A* algorythmus beschäftigt, der als erste grundlage für eine wegfindung in meinem Projekt dienlich sein soll.
Der Algorythmus an sich hat super funktioniert, war allerdings recht schlampig durchgearbeitet, da ich zuerst keinen wirklichen anhaltspunkt hatte, wie ich die informationen genau brauche.

Nun schreibe ich das ganze grade in ein Type um, worin jede instanz dieses Objektes eine eigene Wegfindung durchführt und sich in einer Globalen liste registriert, um dort über eine Updatemethode auf mehrere Frames verteilt ihre berechnungen durchführt.

A* sieht (laut tutorial^^) ja so aus:

2 Listen - Offen und geschlossen
Jeder eintrag ist ein "Knoten", welcher 3 werte hält: Schrittkosten, Geschätze entfernung zum Ziel, Wegkosten gesamt.

In meinem Tutorial waren die werte mit f g und h bezeichnet.

F = Kosten gesamt
H = heuristic? Entfernung zum Ziel (geschätzt!)
G = Schrittkosten (10 für Vertikal/Horizontal, 14 für diagonalen schritt)

Der Tutorial ersteller hatte diese Knoten in einer "Liste" sortiert. Ich nahm also zuerst an, er meinte eine Linked List.
Allerdings meinte er auch, das er die "Offen" (dh noch zu prüfende, angrenzende wegpunkte) nach ihren F kosten sortiert. Das klang wiederrum nach einem Array.

Meine erste version sah nun auch so aus, das ich einen Array immer um 1 Element erweitert hatte, später wollte ich dann auf eine "Finde freien Platz"-methode umsteigen und zb einen TKnoten[] mit Länge 100 halten, sollte dieser nun mehr einträge benötigen, um weitere 100 erweitern.
Das lief aber ganz und garnicht und ich bin Frustriert auf TList umgestiegen.

Danach lief der Algo auch super - ein paar kleinere abfragen musste ich zwar noch fixen, aber ansonsten liefs.

Nachdem es liefs, stieß ich allerdings auf mehrere Probleme:

1) Wegfindung die Komplex war, produzierte aufgrund einer Rekursiven Funktion ab und zu einen Absturz
2) Der Speicherbedarf war enorm - bei Komplexen Findungen hatte ich gute 50mb Speicher belegt (konnte aber aufgrund der Rekursion sein, ich weiß ehrlich gesagt nicht, wann der GCC so ausgeführt wird^^)
3) Es war absolut nichts zu rütteln, komplexe wegfindungen haben 2-3 Sekunden gebraucht.

--------------------------

Schritt 2: umschreiben in einen Type

Gut, aufgrund der Rekursion wollte ich stattdessen Iterativ (nennt sich das so?^^) das ganze abarbeiten. Dazu noch einen Wert, wieviele Knoten pro durchlauf getestet werden sollte.
Dh nicht so wichtige wegfindungen liefen mit 30knoten pro Frame, wichtigere konnten dann mal 200 machen.
Es ist ja nur menschlich, wenn jemand mal grade überlegt, wo er langlaufen muss Wink

Als "Offen" halte ich nun eine TList und als "Geschlossen" einen Simplen Byte[,], welcher die Mappositionen wiederspiegelt und TRUE/FALSE werte enthält. False = Punkt ist nicht als Geschlossen makiert, true = Er ist als geschlossen makiert.
(anmerkung: Die Geschlossenen Punkte enthalten bereits den Absolut besten weg zu diesem Punkt - die Offenen müssen noch überprüft werden)

Ich werde noch grade ein wenig an dem Type feilen müssen, der läuft grade nicht richtig. Wenn ers dann tut, werde ich mal meinen Code hier rein stellen und auf rückmeldung hoffen Smile

Ist das der richtige ansatz - eine Instanz erstellen und in einzelschritten abarbeiten -> Fördert FPS. Dazu die Linked List aufgrund ihrer Dynamic. Für die geschlossene liste brauche ich keine Pointer halten, da diese irgendwo in den Verlinkungen der Knoten noch existiert - nur die "offenen" sind relevant.

Gibt es eventuell eine methode, mit der ich einen TKnoten[] nach einem TKnoten.field sortieren kann? Um genauer zu sein, nach .f ? =) Dafür auchnoch einen Algorythmus bauen wäre mir zu schwer.

Sollte ich vielleicht - aufgrund der geschwindigkeit - keine TKnoten-instanzen verwenden, sondern die werte anders sortieren? Wenn ja, wie? Smile

Ps: Ich brauch hoffentlich nicht lange, um meinen Type umzuschreiben - die Test Szene ist zwar hoffnungslos schlecht gecoded, aber es reicht evtl, das ihr mich mit Kritik am Type AStern2d in der luft zerreißen könnt und mir dann doch ein bissl helfen könnt *g*

Edit:

So, diverse kleinere Fehler behoben. Die Type version wählt zwar noch nicht den besten weg, aber es ist ziemlich schnell.
Speicherverbrauch habe ich noch nicht überprüft - hoffentlich nicht zu viel Smile

Meine Testversion beinhaltet folgendes:

Einstellbares raster (über CONST rSizeX und rSizeY vor programmstart!), eine TUnit einheit, die per Mausklick platziert werden kann und über einenen weiteren Mausklick (links!) mit dem Type-system rumgeschickt wird.
Mittlere Maustaste-klick nimmt die alte methode (Rekursiv! Aufpassen, kann leicht die maximale Rekursions-tiefe eures Prozessors erreichen ->Programmabsturz).
Per Rechtsklick lassen sich wände in die Map eintragen - diese werden bei der Wegfindung natürlich nicht genutzt. Die Unit sucht automatisch einen neuen weg, falls ihr nächster Knotenpunkt mittlerweile eine wand ist.
Das ganze ist nicht wirklich sauber, aber es ist ja auch nur ein erster Test - und die Wegfindung steht mir im vordergrund!
Sollte kein weg gefunden werden, bricht der Algorythmus ab und löscht sich selbst.

Hier mal ein Screenshot:
user posted image
Der kleine rote punkt ist meine "TUnit" Smile Die blauen linienen werden entlang der Wegpunkte gezeichnet. Sie zeigen also den gefundenen weg.
Dieser dauerte 1-2sekunden und ist ziemlich komplex. Eine Diagonale bewegung an der wand lang wird nicht akzeptiert (ganz gut an den harten kanten sichtbar!)


Und hier mein Testcode.

Hauptprogramm:
BlitzMax: [AUSKLAPPEN] 
SuperStrict

Rem
	bbdoc: Das ist mein erster ansatz, einen A* algo zu schreiben. Das ganze diehnt gleichermaßen als testfläche und wird deshalb grafisch vorher aufgemotzt :)
end rem

SeedRnd(MilliSecs())

Const ResX:Int = 1280, ResY:Int = 1024
Const rSizeX:Int = 75, rSizeY:Int = 75
Const tileSize:Int = Int((resy - 200) / rSizeY)

Graphics ResX, ResY

Local fps:Int = 0
Local oldFPS:Int = 0
Local fpsTimer:Int = MilliSecs()
Global timer:TTimer = CreateTimer(120)

Local clickState:Int = 0 'wenn 1, dann ist das nächste ein zielpunkt.

Global curr:TList = CreateList()
Global closed:TList = CreateList()
Global off:TList = CreateList()

Global selectedID:Int = 0

Global lastSlotX:Int = -1
Global lastSlotY:Int = -1

Global cnt:Int = 0

Global map:Short[,] = New Short[rSizeX + 2, rSizeY + 2]'MakeMaze(rSizeX + 2, rSizeY + 2, 1, 1)

For Local x:Int = 0 Until rSizeX + 2
	map[x, 0] = 500
	map[x, rSizeY + 1] = 500
Next

For Local y:Int = 0 Until rSizeY + 2
	map[0, y] = 500
	map[rSizeX + 1, y] = 500
Next

'For Local x:Int = 0 Until rSizeX + 2
'	For Local y:Int = 0 Until rSizeY + 2
'		map[x, y] = 500 * map[x, y]
'	Next
'Next

SetOrigin(tileSize + 50, tileSize + 50)


Local clickTimer:Int = MilliSecs()

While Not KeyHit(KEY_ESCAPE)
	Cls
	
	Local mPosX:Int = MouseX()
	Local mPosY:Int = MouseY()

	
	'Slot X/Y bestimmen.
	Local x:Int = (mPosX - 50 - tileSize) / tileSize
	Local y:Int = (mPosY - 50 - tileSize) / tileSize
	
	If KeyHit(KEY_1) Then selectedID = 1
	If KeyHit(KEY_2) Then selectedID = 2
	If KeyHit(KEY_3) Then selectedID = 3
	If KeyHit(KEY_4) Then selectedID = 4
	If KeyHit(KEY_5) Then selectedID = 5
	If KeyHit(KEY_6) Then selectedID = 6
	If KeyHit(KEY_7) Then selectedID = 7
	If KeyHit(KEY_8) Then selectedID = 8
	If KeyHit(KEY_9) Then selectedID = 9
	If KeyHit(KEY_0) Then selectedID = 0 'void

	'Wenn maus gedrückt wurde...
	If MouseHit(1) And clickTimer < MilliSecs()
		clickTimer = MilliSecs() + 100 'kleiner workarround, da meine maus manchmal doppelklicks produziert :<
		
		'...und der slot innerhalb der Map-range liegt..
		If x >= 0 And x < rSizeX + 2 And y >= 0 And y < rSizeY + 2 Then
			If clickState = 0 Then
				Local unit:TUnit = TUnit.Create(x, y) 'unit erstellen
				clickState = 1
			Else
				If map[x, y] = Null Then
					Local unit:TUnit = TUnit(TUnit.list.Last())
					TAStern2D.Create(map, unit.slotX, unit.slotY, x, y)
					'unit.zielList = AStern(unit.slotX, unit.slotY, x, y) 'einen zufälligen wegpunkt bestimmen.
					'clickState = 0
				End If
			EndIf
		End If
	ElseIf MouseDown(2) And clickTimer < MilliSecs()
	'	clickTimer = MilliSecs() + 100
		If x >= 0 And x < rSizeX + 2 And y >= 0 And y < rSizeY + 2 Then
			If KeyDown(KEY_LCONTROL) Then
				map[x, y] = 0
			ElseIf KeyDown(KEY_LSHIFT) Then
				'steigungen bestimmen
				Local _sX:Float = x - lastSlotX
				Local _sY:Float = y - lastSlotY
				Local dist:Float = Sqr((_sx * _sx) + (_sy * _sy))
				
				If _sX > _sY Then
					_sY:/_sX
				Else
					_sX:/_sY
				End If
				
				Local _x2:Int = lastSlotX, _y2:Int = lastSlotY
				
				While 1
					If _x2 >= 0 And _y2 >= 0 And _x2 < rSizeX + 2 And _y2 < rSizeY + 2 Then
						map[_x2, _y2] = selectedID
						If selectedID = 0 Then map[_x2, _y2] = 500
						
						_x2:+_sX
						_y2:+_sY
						
						If _x2 > x Or _y2 > y Then Exit
					Else
						Exit
					EndIf
				Wend
			Else
				map[x, y] = selectedID
				If selectedID = 0 Then map[x, y] = 500
			EndIf
		End If
	ElseIf clickState = 1 And MouseHit(3) Then
		Local unit:TUnit = TUnit(TUnit.list.Last())
			unit.slotX:+(unit.posx / tileSize)
			unit.slotY:+(unit.posy / tileSize)
			unit.posx = 0
			unit.posy = 0
			unit.zielList = AStern(unit.slotX, unit.slotY, x, y)

	End If

	
	lastSlotX = x
	lastSlotY = y
	
	Local aS:TAStern2D = TAStern2d(TAStern2D.list.First())
	If aS Then
		Local vecList:TVec2[] = aS.Update(100)
		If vecList Then
			Local unit:TUnit = TUnit(TUnit.list.Last())
			'TAStern2D.Create(map, unit.slotX, unit.slotY, x, y)
			If unit.ziellist Then
				unit.tmplist = vecList
			Else
				unit.zielList = vecList
			EndIf
			TAStern2D.list.RemoveFirst()
		End If
	EndIf
	'Grafische ausgabe: 
	SetLineWidth(1)
	DrawRaster() 'raster zeichnen.
	DrawBorders() '"aussenwände" zeichnen.
	
	SetLineWidth(3)
	For Local unit:TUnit = EachIn TUnit.list
		unit.Move() 'unit bewegen
		unit.Draw() 'unit zeichnen
	Next
	
	'Debug Texte!
	SetColor(255, 255, 255)
	DrawText("FPS: " + oldFPS, -50, -50)
	DrawText("MausX: " + MouseX() + " MausY: " + MouseY(), -50, -35)
	DrawText("SlotX: " + x + " SlotY: " + y, -50, -20)
	
	DrawText("Ausgewählte ID: " + selectedID, ResX - 400, -15)
	DrawRect(ResX - 400, 10, 295, 295)
	
	SetColor(selectedID * 23, selectedID * 14, 0)
	If selectedID = 0 Then SetColor(128, 128, 128)
	DrawRect(ResX - 390, 20, 275, 275)
	
	SetColor(255, 255, 255)
	Flip 0
	
	'FPS Timer hochzählen.
	fps:+1
	If fpsTimer < MilliSecs()
		oldFPS = fps
		fps = 0
		fpsTimer = MilliSecs() + 1000
	End If
	
	WaitTimer(timer) 'Cpu-verbrauch senken.
Wend

Rem
	bbdoc: AStern ist der Wegfinde algo den ich nun schreiben möchte. Sie sollte nahezu perfekt funktionieren, um kleinere distanzen zu überbrücken. Ab einem gewissen abstand sollte allerdings etwas anderes her!
end rem
Function AStern:TVec2[] (sX:Int, sY:Int, eX:Int, eY:Int)
	StopTimer(timer)
	timer = CreateTimer(40)
	'sX / sY = startpunkt, eX / eY = endpunkt.
	Print "AStern soll den weg weisen! Startpunkt X/Y: " + sx + "/" + sy + " --- Endpunkt: " + ex + "/" + ey
	'Local offen:TKnoten[] '= New TKnoten[100]
	'Local geschlossen:TKnoten[] '= New TKnoten[100]
	Local offen:TList = CreateList()
	Local geschlossen:TList = CreateList()
	
	'Zeiger-map!
	Local inOffen:Tknoten[,] = New Tknoten[rSizeX + 2, rSizeY + 2]
	Local inGeschlossen:Tknoten[,] = New TKnoten[rSizeX + 2, rSizeY + 2]
	'anmerkung:
	'Die "Zeigermaps" sollen einen Speedboosts auf kosten von Ram produzieren.
	'Sinn dieser maps ist, das sie die Map wiederspiegeln und für jeden Slot zwei Integer halten.
	'Ist inOffen auf platz X,Y etwas anderes als 0 eingetragen, so stehen diese werte für "offen[z-1]" bzw "geschlossen[z-1]"
	'---> Ich spare mir das suchen der teile in den offen/geschlossen arrays -> speedboost!
	
	off.Clear()
	closed.Clear()
	curr.Clear()
	
	
	'init - startpunkt als knoten in die offene liste einfügen, danach die rekursive funktion _AStern_Knotencheck() ausführen!
'	Local found:Int = 0
'	For Local i:Int = 0 Until Len(offen)
'		If offen[i] = Null Then
'			found = 1
'			offen[i] = TKnoten.Create(sX, sY, 0, 0, Null)
'			inOffen[sX, sY] = i + 1
'		EndIf
'	Next
'	If found = 0 Then
'		Local i:Int = Len(offen)
'		offen = offen[..i + 100] 'array um 100 felder erweitern.
'		offen[i] = TKnoten.Create(sX, sY, 0, 0, Null)
'		inOffen[sx, sy] = i + 1
'	EndIf
	offen.AddLast(TKnoten.Create(sX, sY, 0, eX, eY, Null))
	
	inOffen[sX, sY] = TKnoten(offen.last())'wird eh 1 sein^^
	
	'off.AddLast(offen[inOffen[sX, sY] - 1])
	off.AddLast(TKnoten(offen.Last()))
	
	Draw_Step(Null)
	
	Local knoten:TKnoten = _AStern_Knotencheck(eX, eY, offen, geschlossen, inOffen, inGeschlossen)
	
	If knoten = Null Then
		Print "Error. es wurde kein weg zum ziel gefunden! "
		Print "Länge offen / geschlossen: " + Len(offen) + " / " + Len(geschlossen)
		Print "tut mir ehrlich leid :)"
		StopTimer(timer)
		timer = CreateTimer(120)
		Return Null
	Else
	'	Print "ein weg wurde gefunden. :D Returne nun TVec-Array mit den wegpunkten."
		offen = Null
		geschlossen = Null
		inOffen = Null
		inGeschlossen = Null
		
		StopTimer(timer)
		timer = CreateTimer(120)
		Return _AStern_Generate_Wayarray(knoten)
	End If
	
	Function Draw_Step2(currKnoten:TKnoten)
		Cls
		
		'DrawRaster()
		DrawBorders()
		
		SetLineWidth(0.7)
		
		'SetAlpha(0.5)
		For Local _curr:TKnoten = EachIn curr
			SetColor(128, 0, 128)
			_curr.Draw()
		Next
		
		For Local _off:TKnoten = EachIn off
			SetColor(150, 150, 255)
			_off.Draw()
		Next
		
		For Local _clos:TKnoten = EachIn closed
			SetColor(255, 150, 150)
			_clos.Draw()
		Next
		

		If currKnoten Then
			SetColor(0, 255, 0)
			currKnoten.Draw()
		End If
		
		For Local _off:TKnoten = EachIn off
			_off.draw2()
		Next
		For Local _clos:TKnoten = EachIn closed
			_clos.draw2()
		Next
		If currKnoten Then currKnoten.draw2()
		
		'SetAlpha(1.0)
		SetColor(255, 255, 255)
		
		DrawText("Anzahl Offener einträge: " + cnt, -50, 5)
		Flip 1
		WaitTimer(timer)
		'WaitKey()
	End Function
	
	Function _AStern_Generate_Wayarray:TVec2[] (letzterKnoten:TKnoten)
		Local activeKnoten:TKnoten = letzterKnoten
		
		Local retArr:TVec2[] = [activeKnoten.pos]
		While 1
			If activeKnoten.prevLink = Null Then
				'letzter knoten -> startpunkt!
				Return retArr
			Else
				'es geht noch weiter.
			'	activeKnoten.pos.x
			'	activeKnoten.pos.y
				retArr = [activeKnoten.pos] + retArr
				activeKnoten = activeKnoten.prevLink
			End If
			
		Wend
	End Function
	
	Function _AStern_Knotencheck:TKnoten(endX:Int, endY:Int, offen:TList, geschlossen:TList, inOffen:TKnoten[,], inGeschlossen:Tknoten[,])
	
		Cls
			
		DrawRaster()
			
	
		'Abbruchsbedingung: Es ist kein weiterer knoten mehr in der liste.
		'da ich hier keinen simplen len check vorest machen kann, erstmal mit einer popeligen for-schleife
	'	Print "_Astern_Knotencheck! "
	'	Print "endX/Y: " + endX + "/" + endY + " - len(offen): " + Len(offen) + " - len(geschlossen): " + Len(geschlossen)
'		Local abbruch:Int = 1
'		For Local knoten:TKnoten = EachIn offen
'			abbruch = 0
'			Exit 'sollte direkt beim ersten knoten schon sinnlos sein
'		Next
'		If abbruch = 1 Then Return Null 'es wurde leider kein wegpuntk gefunden. wenn das passiert, ist die liste leer und es gibt nichtsmehr zu tun. 
		If offen.Count() = 0 Then Return Null
		
		'knoten auswählen.
		Local activeJoint:TKnoten
		Local lJoint:TKnoten
		
		Local kosten:Int = 100000000
		Local index:Int = 0
		Local i:Int = 0
		cnt = offen.Count()
		
		For Local k:TKnoten = EachIn offen
			If k.f < kosten Then
				activeJoint = k
				kosten = k.f
			End If
		Next
		
		If activeJoint = Null Then
			Return Null
'			
'			activeJoint = lJoint
		EndIf

		inOffen[activeJoint.pos.x, activeJoint.pos.y] = Null
		
		off.Remove(activeJoint)
		
	'	closed.AddLast(activeJoint)
		
		inGeschlossen[activeJoint.pos.x, activeJoint.pos.y] = activeJoint
		
		'der "günstigste" knoten sollte gefunden sein. Nun ab in die geschlossene mit ihm *g*
	'	offen[index] = Null
	'	geschlossen:+[activeJoint]
	'	inGeschlossen[activeJoint.pos.x, activeJoint.pos.y] = Len(geschlossen)
	'	inOffen[activeJoint.pos.x, activeJoint.pos.y] = 0 'wieder zurücksetzen.
		offen.Remove(activeJoint)
	'	geschlossen.AddLast(activeJoint)
			
		'jeden möglichen punkt ringsherum auftreiben und eventuell in die liste einfügen.
		Local x:Int, y:Int
		Local kX:Int = activeJoint.pos.x
		Local kY:Int = activeJoint.pos.y
		
		For x = kX - 1 To kX + 1
		For y = kY - 1 To kY + 1
			If x < 0 Or y < 0 Or x >= rSizeX + 2 Or y >= rSizeY + 2 Then Continue 'continue, falls es Arrayindex Outofbounds wäre.
			
			If x = endX And y = endY Then
				'hui, das ist der zielpunkt. nun heißt es also: einen knoten draus basteln und zurückgeben.
				Local dirX:Int = Sgn(x - kx)
				Local dirY:Int = Sgn(y - ky)
				
				If dirX = 1 And x > 0 And map[x - 1, y] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirX = -1 And x < rSizeX + 1 And map[x + 1, y] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirY = 1 And y > 0 And map[x, y - 1] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirY = -1 And y < rSizeY + 1 And map[x, y + 1] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				Return TKnoten.Create(x, y, activeJoint.g + 10, endX, endY, activeJoint)
			EndIf
			Local addG:Int = map[x, y] * 3
			If map[x, y] = 500 Then
				Continue 'hier ist keine freie fläche, ignorieren!
			EndIf

			
			If x = kX And y = kY Then Continue 'das ist der aktive punkt. continue.
			
			Local g:Int = 10 'Schrittkosten bestimmen.
			
			If x <> kX And y <> kY Then
				g = 14 'dieser Schritt wäre diagonal - schrittkosten sind der näherungswert 14 statt 10.
				'gucken, ob direkt anliegend eine wand ist!
				'erstmal schrittrichtung bestimmen.
				Local dirX:Int = Sgn(x - kx)
				Local dirY:Int = Sgn(y - ky)
				
				Rem
					DirX und Y sollten in die richtung zeigen, wo der schritt "hingehen" soll.
					Sollte der schritt nach oben links gehen, muss ich rechts und unten prüfen.
					Sollte der schritt nach unten rechts gehen, muss ich links und oben prüfen. Simpel as that :)
					
				end rem
				
				If dirX = 1 And x > 0 And map[x - 1, y] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirX = -1 And x < rSizeX + 1 And map[x + 1, y] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirY = 1 And y > 0 And map[x, y - 1] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
				If dirY = -1 And y < rSizeY + 1 And map[x, y + 1] = 500 Then
					curr.AddLast(TKnoten.Create(x, y, -1, x, y, Null))
					Continue
				EndIf
			EndIf
			
			g:+addG
			If inOffen[x, y] Then
				'dieser punkt ist in der "offen" liste!
				Local knoten:TKnoten = inOffen[x, y]
				If knoten.g > activeJoint.g + g Then
					knoten.prevLink = activeJoint 'link umschreiben 
				'	knoten.f:-knoten.g 'wegkosten runterrechnen - hier fügen wir gleich das neue g ein!: )
					knoten.g = activeJoint.g + g 'kosten umändern
				'	knoten.f:+knoten.g 'kosten wieder aufrechnen.
					knoten.f = knoten.g + knoten.h 'f wieder errechnen
				End If
				Continue
			End If
			
			'die "geschlossene" liste durchsuchen, ob hier bereits dieser punkt drin ist.
			If inGeschlossen[x, y] Then
				'Local knoten:TKnoten = geschlossen[inGeschlossen[x, y]]
				Continue
			End If
					
			'wenn das programm bis hierhin kommt, war der doofe punkt wohl tatsächlich nicht vorhanden. schade auch, also fügen wir ihn in die offene liste ein.
			Local newK:TKnoten = TKnoten.Create(x, y, activeJoint.g + g, endX, endY, activeJoint)
			offen.addfirst(newK)
			inOffen[x, y] = newK
			
			off.AddLast(newK)
			
			cnt = offen.Count()
'			Local found2:Int = 0
'			For Local i:Int = 0 Until Len(offen)
'				If offen[i] = Null Then
'					found2 = 1
'					offen[i] = TKnoten.Create(x, y, activeJoint.g + g, Abs(x - endx) + Abs(y - endy), activeJoint)
'					inOffen[x, y] = i + 1
'				EndIf
'			Next
'			If found2 = 0 Then
'				Local i:Int = Len(offen)
'				offen = offen[..i + 100] 'offen-array um 100 felder erweitern.
'				offen[i] = TKnoten.Create(x, y, activeJoint.g + g, Abs(x - endx) + Abs(y - endy), activeJoint)
'				inOffen[x, y] = i + 1
'			EndIf
		Next
		Next
		If KeyDown(KEY_ENTER) Then Draw_Step(activeJoint)
		Return _AStern_Knotencheck(endX, endY, offen, geschlossen, inOffen, inGeschlossen)
	End Function
End Function

Rem
	bbdoc: TUnit ist ein einfacher platzhalter für eine __COMMENT114__
end rem
Type TUnit
	Global list:TList = CreateList()
	
	Field slotX:Int
	Field slotY:Int
	Field posx:Float
	Field posy:Float
	
	Field zielX:Int
	Field zielY:Int
	
	Field zielList:TVec2[]
	Field tmpList:TVec2[] 'hier wird temporär die neue liste gespeichert. 
		
	Method Draw()
		SetColor(100, 100, 255) 'blau für waypoints
		Local lastVec:TVec2 = Null
		For Local vec:TVec2 = EachIn Self.zielList
			If lastVec = Null Then
				DrawLine(Self.posx + (tileSize / 2) + (Self.slotX * tileSize), Self.posy + (tileSize / 2) + (Self.slotY * tileSize), vec.x * tileSize + (tileSize / 2), vec.y * tileSize + (tileSize / 2))
				lastVec = vec
			Else
				DrawLine((lastVec.x * tileSize) + (tileSize / 2), (lastVec.y * tileSize) + (tileSize / 2), vec.x * tileSize + (tileSize / 2), vec.y * tileSize + (tileSize / 2))
				lastVec = vec
			End If
		Next
		
		SetColor(255, 0, 0) 'rot für unit
		DrawRect(Self.posx + 3 + (Self.slotX * tileSize), Self.posy + 3 + (Self.slotY * tileSize), tileSize - 5, tileSize - 5)
		
	'	SetColor(255, 255, 0) 'gelb für Aktuellen Zielpunkt
	'	DrawRect((Self.zielX * tileSize) + 3, (Self.zielY * tileSize) + 3, tileSize - 5, tileSize - 5)
	End Method
	
	Method Move:Int()
		Local i:Int = 0
		Local pos:TVec2 = Null
		
		For i = 0 Until Len(Self.zielList)
			If zielList[i] <> Null Then 'wenn ein Zielpunkt gefunden wurde (der erste in der liste, um genauzusein!)...
				pos = zielList[i] 'merker-variable pointern
				Exit 'und raus hier.
			End If
		Next
		
		If pos = Null Then 'pos = null, neuen Zielpunkt finden und raus hier
			'neuen zielpunkt bestimmen.
		'	Self.zielList = AStern(Self.slotX, Self.slotY, Rand(1, rSizeX - 2), Rand(1, rSizeY - 2))
			Self.zielList = Null
			Return 2
			
		Else 'pos <> null -> wir müssen uns bewegen.
			'moving vornehmen!
			
			'Test: Vor uns eine Wand? Miep! :(
			If map[pos.x, pos.y] = ASTERN_WALL Then
				'ohje, tatsächlich. eine Wand.
				'Todo: Aus dem Letzten Pos-eintrag die alte zielposition extrahieren und eine neue wegfindung registrieren.
				Local zielVec:TVec2 = Self.zielList[Len(Self.zielList) - 1]
				If zielVec Then
					Self.zielList = Null
					If Self.tmpList Then
						'oh wird haben mittlerweile eine Tmpliste -> erstmal die nutzen.
						Self.zielList = Self.tmpList
						Self.tmpList = Null
						
						Return 0
					End If
					
					TAStern2D.Create(map, Self.slotX, Self.slotY, zielVec.x, zielVec.y)
					Return 0
				EndIf
			End If
			
			Local dirX:Int = -Sgn(Self.slotX - pos.x) * 2
			Local dirY:Int = -Sgn(Self.slotY - pos.y) * 2
		
				Self.posx:+(dirX)
				Self.posy:+(dirY)
				
			If Self.posx >= tileSize Then
				Self.slotX:+1
				Self.posx:-tileSize
			ElseIf Self.posx <= - tileSize Then
				Self.slotX:-1
				Self.posx:+tileSize
			EndIf
			
			If Self.posy >= tileSize Then
				Self.slotY:+1
				Self.posy:-tileSize
			ElseIf Self.posy <= - tileSize Then
				Self.slotY:-1
				Self.posy:+tileSize
			EndIf
		
			If Self.slotX - pos.x = 0 And Self.slotY - pos.y = 0 Then
				'wir sind am zielpunkt.
				If Abs(Self.posx) < 1.1 And Abs(Self.posy) < 1.1 Then
					Self.zielList[i] = Null
					If Self.tmpList Then
						'eine neue wegpunktliste ist verfügbar. Umpointern :)
						'Anmerkung: aufgrund der verkrepelten bewege-routine muss dieser workarround her. Ausserdem ists doch schöner, seine arbeiten zu erledigen, bevor man was neues macht, oder? Wink
						Self.zielList = Self.tmpList
						Self.tmpList = Null 'pointer löschen, um nich ständig neu anzufangen :)
					EndIf
					Self.posx = 0
					Self.posy = 0
				End If
			End If
		EndIf
	End Method
	
	Function Create:TUnit(posX:Int, posY:Int)
		Local unit:TUnit = New TUnit
		
		Print "Unit wird mit X:" + posX + " Y:" + posY + " erstellt."
		unit.slotX = posx
		unit.slotY = posY
		
		'DrawRect((Self.slotX * tileSize + 50) + 3, (Self.slotY * tileSize + 50) + 3, tileSize - 5, tileSize - 5)
			
		TUnit.list.AddLast(unit)
		
		Return unit
	End Function
End Type

Type TKnoten
	Field f:Int 'wegkosten
	Field g:Int 'richtungskosten
	Field h:Int 'Kosten bis ziel
	
	Field pos:TVec2
	
	Field prevLink:TKnoten

	Function Create:TKnoten(x:Int, y:Int, g:Int, zielX:Int, zielY:Int, prevLink:TKnoten)
		Local knoten:TKnoten = New TKnoten
		Local distX:Int = Abs(x - zielX)
		Local distY:Int = Abs(y - zielY)
	
		Local h:Int' = 10 * (Abs(x - zielX) + Abs(y - zielY))
		h = 14 * Max(Abs(x - zielX), Abs(y - zielY))
	'	h = sqr((distX * distX) + (distY * distY))*14
		
'		If distX > distY
'			h = 14 * distY + 10 * (distX - distY)
'		Else
'			h = 14 * distX + 10 * (distY - distX)
'		End If
		
		knoten.f = g + h
		knoten.g = g
		knoten.h = h
		knoten.prevLink = prevLink
		
		knoten.pos = Vec2(x, y)
	'	Print "Knoten an pos "+x+"/"+y+" wurde erstellt. f: "+(g+h)
		Return knoten
	End Function
	
	Method Draw()
		Local x:Int = Self.pos.x * tileSize
		Local y:Int = Self.pos.y * tileSize
		DrawRect(x, y, tileSize, tileSize)
		
		SetColor(200, 200, 200)
		
'		DrawLine((Self.pos.x * tileSize) + 1, (Self.pos.y * tileSize) + 1, Self.pos.x * tileSize + tileSize - 2, Self.pos.y * tileSize + 1)
'		DrawLine((Self.pos.x + 1) * tileSize - 1, (Self.pos.y * tileSize) + 1, (Self.pos.x + 1) * tileSize - 1, Self.pos.y * tileSize + tileSize + 2)
'		
'		DrawText(Self.f, x + 1, y + 1)
'		DrawText(Self.g, x + 1, y + tileSize - 14)
'		DrawText(Self.h, x + tileSize - 25, y + tileSize - 14)

	End Method
	Method Draw2()
		If Self.prevLink Then
			SetColor(255, 255, 255)
			
			Local pX:Float = ((Self.prevLink.pos.x + 0.5) * tilesize - (Self.pos.x * tileSize + 0.5))
			Local pY:Float = ((Self.prevLink.pos.y + 0.5) * tilesize - (Self.pos.y * tileSize + 0.5))
			
			DrawLine((Self.pos.x + 0.5) * tileSize, (Self.pos.y + 0.5) * tileSize, Self.pos.x * tileSize + (pX), + Self.pos.y * tileSize + (pY))
			
		EndIf
	End Method
End Type
Type TVec2
	Field x:Int
	Field y:Int
End Type
Function Vec2:TVec2(x:Int, y:Int = 0)
	Local vec:TVec2 = New TVec2
	vec.x = x
	vec.y = y
	Return vec
End Function

Function DrawRaster()
	Local x:Int = 0, y:Int = 0
	Local posX:Int = 0, posY:Int = 0

	For x = 0 To rSizeX * tileSize + tileSize Step tileSize
	
		DrawLine(x, 0, x, tileSize * rSizeY + tileSize)
	
	Next
	
	For y = 0 To rSizeY * tileSize + tileSize Step tileSize
			DrawLine(0, y, tileSize * rSizeX + tileSize, y)
	Next
End Function
Function DrawBorders()
	SetColor(127, 127, 127)
	
	Local x:Int, y:Int
	For x = 0 Until rSizeX + 2
	For y = 0 Until rSizeY + 2
		If map[x, y] = 500 Then
			SetColor(127, 127, 127)
			DrawRect(x * tileSize - 1, y * tileSize - 1, tileSize + 2, tileSize + 2)
		ElseIf map[x, y] > 0 Then
			SetColor(map[x, y] * 23, map[x, y] * 14, 0)
			DrawRect(x * tileSize, y * tileSize, tileSize, tileSize)
		'	If map[x, y]= 500 Then SetColor(128, 128, 128)
		End If
	Next
	Next
'	
'	'obere kante
'	DrawRect(0, 0, tileSize * rSizeX + tileSize + 1, tileSize)
'	'untere kante
'	DrawRect(0, rSizeY * tileSize + 1, tileSize * rSizeX + tileSize + 1, tileSize)
'	
'	'linke kante
'	DrawRect(0, 0, tileSize, tileSize * rSizeY + tileSize + 1)
'	
'	'rechte kante!
'	DrawRect(rSizeX * tileSize + 1, 0, tileSize, tileSize * rSizeY + tileSize + 1)
	
	SetColor(255, 255, 255)
End Function

(ich weiß, viel ist auskommentiert - vieles sind zb Debugprints oder debugprints!)

Type TAStern2d:
BlitzMax: [AUSKLAPPEN] 

Const ASTERN_WALL:Int = 500

Type TAStern2D
	Global list:TList = CreateList()
	
	Field _toCheck:TList = CreateList()
	Field geschlossen:Byte[,]
	
	Field map:Short[,]
	
	Field endX:Int
	Field endY:Int
	
	Function Create:TAStern2D(mapArr:Short[,], startX:Int, startY:Int, zielX:Int, zielY:Int)
		Local aStern:TAStern2D = New TAStern2D
		
		aStern._toCheck.AddLast(TKnoten.Create(startX, startY, 0, zielX, zielY, Null))
		aStern.map = mapArr
		
		aStern.endX = zielX
		AStern.endY = zielY
		
		AStern.geschlossen = New Byte[mapArr.Dimensions()[0], mapArr.dimensions()[1]]
		
		TAStern2D.list.AddLast(aStern)
		
		Return aStern
	End Function
	
	Rem
		bbdoc: Die methode Update durchläuft mehrere knotenpunkten und versucht den weg zu finden. 
				sie returnt einen TVec2 array, sobald sie fertig ist, andernfalls null.
	end rem
	Method Update:TVec2[] (times:Int = 100)
	'	Print "Update wurde aufgerufen"
		DrawText("Anzahl der offenen suchbeiträge: " + Self._toCheck.Count(), -50, ResY - 250)
		Local knoten:TKnoten = Null
		For Local i:Int = 0 Until times
			
			knoten = Self._KnotenCheck()
			If Self._toCheck.Count() = 0 Then 'die suche war nichtmehr erfolgreich. Kein weg konnte gefunden werden!
				TAStern2D.list.Remove(Self) 'Sich selbst aus der liste kicken.
				Print "TAstern2D Algo konnte keinen Weg finden. Selbstmord :)"
				Return Null
			End If
		'	Draw_Step(Null)
			If knoten Then
				Print "Endknoten wurde gefunden!"
				'ende wurde erreicht. Vec-array erstellen und zurückgeben.
				Local arr:TVec2[]' = New TVec2[knoten.g / 10]
			'	Local i:Int = 0
				While 1
				'	i:+1
					If knoten.prevLink = Null Then
						Return arr
					End If
					arr = [knoten.prevLink.pos] + arr 'ich weiß, nicht grade schnell -.-
					knoten = knoten.prevLink
				Wend
			End If
		Next
		Return Null
	End Method
	
	Method _KnotenCheck:Tknoten()
	'	If Self._toCheck.count() = 0 Then Return Null 'wegfindung war erfolglos.
		
		' Nächstbesten knoten finden.
		Local kosten:Int = 100000
		Local _knoten:TKnoten = Null
		For Local knoten:TKnoten = EachIn Self._toCheck
			If knoten.f < kosten Then
	'			Print "Günstigerer knoten gefunden. Kosten momentan: " + kosten + " - gefunden wurde einer mit Kosten: " + knoten.f
				_knoten = knoten
				kosten = knoten.f
				
			End If
		Next
		
		If _knoten = Null Then Return Null 'es konnte nichts in der liste gefunden werden. Return :<
		
		' Knoten als "geschlossen" makieren
		Local rx:Int = _knoten.pos.x, ry:Int = _knoten.pos.y
		
		Self._toCheck.Remove(_knoten)
		
		Self.geschlossen[rx, ry] = 1
		off.Remove(_knoten)
		closed.AddLast(_knoten)
		Local mapSizeX:Int = Self.geschlossen.dimensions()[0]
		Local mapSizeY:Int = Self.geschlossen.dimensions()[1]
		' Gucken, ob der endpunkt drumrum liegt!
		If Abs(Self.endX - rx) < 2 And Abs(Self.endY - ry) < 2 Then
			'endpunkt liegt hier an! 
			Local dirX:Int = Sgn(rx - Self.endX)
			Local dirY:Int = Sgn(ry - Self.endY)
			Local found:Int = 0
			If dirX = 1 And rx > 0 And map[Self.endX - 1, Self.endY] = ASTERN_WALL Then
				found = 1
			EndIf
			If dirX = -1 And rx < mapSizeX And map[Self.endX + 1, Self.endY] = ASTERN_WALL Then
				found = 1
			EndIf
			If dirY = 1 And ry > 0 And map[Self.endX, Self.endY - 1] = ASTERN_WALL Then
				found = 1
			EndIf
			If dirY = -1 And ry < mapSizeY And map[Self.endX, Self.endY + 1] = ASTERN_WALL Then
				found = 1
			EndIf
			If found = 0 Then Return TKnoten.Create(rx, ry, _knoten.g + 10, Self.endX, Self.endY, _knoten)
		End If
		
		
		' Drumrum durchgehen :)
		Local X:Int, Y:Int
		
		For X = rx - 1 To rx + 1
		For Y = ry - 1 To ry + 1
		

			
			If X < 0 Or Y < 0 Or X > mapSizeX - 1 Or Y > mapSizeY - 1 Then
			'	Print "X: " + X + " Y: " + Y + " liegt ausserhalb der map."
				Continue 'Array index out of bounds: Continue
			EndIf
			If Self.map[X, Y] = ASTERN_WALL Then
			'	Print "X: " + X + " Y: " + Y + " ist eine Mauer."
				Continue 'Auf dem Slot ist eine Mauer: Continue
			EndIf
			If X = rx And Y = ry Then
			'	Print "X: " + X + " Y: " + Y + " ist der grade zu Prüfende knoten."
				Continue 'Von dem Slot aus suchen wir: Continue			
			EndIf
			
			Local g:Int = 10 'schrittkosten pro feld: 10
			
			If x <> rX And y <> rY Then
				g = 14 'dieser Schritt wäre diagonal - schrittkosten sind der näherungswert 14 statt 10.
				'gucken, ob direkt anliegend eine wand ist!
				'erstmal schrittrichtung bestimmen.
				Local dirX:Int = Sgn(x - rx)
				Local dirY:Int = Sgn(y - ry)

				If dirX = 1 And X > 0 And map[X - 1, Y] = ASTERN_WALL Then
					Continue
				EndIf
				If dirX = -1 And X < rSizeX + 1 And map[X + 1, Y] = ASTERN_WALL Then
				'	curr.AddLast(TKnoten.Create(X, Y, -1, X, Y, Null))
					Continue
				EndIf
				If dirY = 1 And Y > 0 And map[X, Y - 1] = ASTERN_WALL Then
					Continue
				EndIf
				If dirY = -1 And Y < rSizeY + 1 And map[X, Y + 1] = ASTERN_WALL Then
					Continue
				EndIf
			EndIf
			
			'Abfragen - knoten bereits verfügbar?
			
			'step1: In der "Offen" liste suchen (sollte bei kleineren wegen sehr schnell sein. Bei größeren maps kann es "mal" 500 einträge haben.)
			For Local _Offen:TKnoten = EachIn Self._toCheck
				If _Offen.pos.x = x And _Offen.pos.y = y Then
					'dieser knotenpunkt ist bereits in der liste. Prüfen ob der gefundene weg kürzer ist:
					If _Offen.g > _knoten.g + g Then
						'Print "X: " + X + " Y: " + Y + " ist bereits Offen - der puntk ist allerdings von dem Aktiven besser zu erreichen."
						'ja, der weg ist kürzer! umstellen:
						_Offen.g = _knoten.g + g
						_Offen.f = _Offen.g + _Offen.h
					End If
					
					g = -1
					Exit
				End If
			Next
			If g = -1 Then
				Continue 'wurde in der "in Offen" abfrage gebraucht und auf -1 gesetzt: Der knoten war verfügbar, weitermachen!
			EndIf
			
			If Self.geschlossen[X, Y] = 1 Then
			'	Print "X: " + X + " Y: " + Y + " ist ein Geschlossener punkt!"
				Continue 'ist in der "geschlossen" liste. Weitermachen!
			EndIf
		'	closed.AddLast(TKnoten.Create(X, Y, 0, 0, 0, Null))
			
			Local _knotenZuAdden:TKnoten = TKnoten.Create(X, Y, _knoten.g + g, Self.endX, Self.endY, _knoten)
			Self._toCheck.addfirst(_knotenZuAdden)
			off.AddFirst(_knotenZuAdden)
		'	Print "X: " + x + " Y: " + y + " wurde als ~qoffen~q eingetragen."
		Next
		Next

		Return Null
	End Method
End Type

	Function Draw_Step(currKnoten:TKnoten)
	'	Print "Draw step!"
		Cls
		
		'DrawRaster()
		DrawBorders()
		
		SetLineWidth(0.7)
		
		'SetAlpha(0.5)
		For Local _curr:TKnoten = EachIn curr
			SetColor(128, 0, 128)
			_curr.Draw()
		Next
		
		For Local _off:TKnoten = EachIn off
			SetColor(150, 150, 255)
			_off.Draw()
		Next
		
		For Local _clos:TKnoten = EachIn closed
			SetColor(255, 150, 150)
			_clos.Draw()
		Next
		

		If currKnoten Then
			SetColor(0, 255, 0)
			currKnoten.Draw()
		End If
		
		SetColor(255, 255, 255)
		
		If currKnoten Then currKnoten.draw2()
		For Local _off:TKnoten = EachIn off
		'	SetColor(150, 150, 255)
			_off.Draw2()
		Next
		
		For Local _clos:TKnoten = EachIn closed
		'	SetColor(255, 150, 150)
			_clos.Draw2()
		Next
		'SetAlpha(1.0)
		SetColor(255, 255, 255)
		
		DrawText("Anzahl Offener einträge: " + cnt, -50, 5)
		Flip 1
	'	WaitTimer(timer)
		WaitKey()
	End Function

Ausserdem ist beim Type auch eine Debug-print methode drinne. Diese braucht allerdings 3 listen, deren füllung im AStern algo deaktiviert ist.

mpmxyz

 BeitragFr, Okt 07, 2011 17:00
Antworten mit Zitat
Benutzer-Profile anzeigen
Ich habe mich mal um (1), (3), (4) und (6) gekümmert. Wink
Ja, der Algorithmus scheint A* zu sein, aber es gibt eine große Perforancebremse: die offene Liste.
Es ist wichtig, dass dort bekannt ist, welcher Eintrag der "beste" ist.
Dazu kann man entweder suchen oder sortieren.
Das Problem: Bei verketteten Listen als auch bei Arrays braucht das bei doppelt so viel Einträgen auch jeweils doppelt so viel Zeit. (bei 3facher Anzahl die 3fache Zeit usw., bei Wikipedia auch im Abschnitt "naive Implementierung" zu finden Wink)
Es gibt aber noch eine wichtige dritte Möglichkeit: Bäume. (In BlitzMax werden sie in "TMap" verwendet.)
In ihnen werden die Einträge automatisch schnell und richtig sortiert.
Hier gibt es eine Implementierung für eine solche Prioritätswarteschlange:
https://www.blitzforum.de/foru...p?p=313906
Die für dich wichtigen Operationen sind: add, isEmpty und removeHighest
mfG
mpmxyz
Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer
 

PhillipK

 BeitragFr, Okt 07, 2011 17:05
Antworten mit Zitat
Benutzer-Profile anzeigen
TMap *grübel*
Klar, ich weiß was das ist. Aber, jetzt ohne HamZta's beitrag (dein Link Razz) gelesen zu haben, erschließt sich mir noch nicht, wie ich DAS bitte nutzen sollte.

Vielleicht ergibt sich mir ja mehr, sobald ich diesen durchgelesen hab.

Die einzige idee die ich hatte, den "besten" eintrag zu kennen, würde am ende sogar langsamer sein und noch dazu den Ram sprengen. Bin mal lesen und editier dann hier mal rein *g*

Edit:

Hmpf, es erschließt sich mir immernoch nicht ganz.
Das problem ist, das die Priorität variabel ist. Ich habe keine ahnung, wie HamZta's funktion läuft, das geht über meinen verstand hinaus Sad
Ausserdem brauche ich auch zugriff auf die Punkte an einer gewissne position - eine möglichkeit, alle einträge in HamZta's objekt durchzugehen, sehe ich so auf die schnelle nicht.

Muss mich da wohl erstmal reinlesen :<
Vielleicht kann ich ja ein paar methoden Adden, zb um eine Priorität zu ändern. Wenn ich das richtig verstanden habe, könnte ich mir die THeapNodes speichern und nach dem ändern der Priorität _heapify() aufrufen. Smile
 

PhillipK

 BeitragFr, Okt 07, 2011 19:15
Antworten mit Zitat
Benutzer-Profile anzeigen
Mist.
Ich habe mir eine Methode gebastelt, die ein Obj in der Data - liste sucht und seine priorität ändert. Allerdings klappt es so auch nicht wirklich.

Wo genau das problem liegt, weiß ich nicht. Es ist nur unheimlich langsam, je komplexer die wegfindung wird - grund hierfür ist eine falsche abfrage, welche ich noch finden muss. Eben hatte eine liste, die jeden "offen" eintrag hält, über 6000 einträge. Meine map mit 75x75 tiles hat aber nur was bei 5600 felder Very Happy Irgendwo ist da also ein bug.
Ich benötige noch ein paar mehr ideen und wissen über die funktion dieses Type's von HamZta, aber damit dürfte es in der Tat schneller werden.
Leider ist die Priorität ziemlich statisch darin verankert, deswegen werde ich da auch nichts neu schreiben können. Hoffentlich ist das neusortieren eines Node's nicht zu langsam - aber rein vom code her, dürfte das nicht sein Very Happy

Xeres

Moderator

BeitragFr, Okt 07, 2011 19:25
Antworten mit Zitat
Benutzer-Profile anzeigen
PhillipK: Auch du bist dazu angehalten, keine Doppelposts zu produzieren und wenn nötig stattdessen deine Beiträge zu editieren.

Haben Sie vielen Dank für Ihr Verständnis!
Win10 Prof.(x64)/Ubuntu 16.04|CPU 4x3Ghz (Intel i5-4590S)|RAM 8 GB|GeForce GTX 960
Wie man Fragen richtig stellt || "Es geht nicht" || Video-Tutorial: Sinus & Cosinus
THERE IS NO FAIR. THERE IS NO JUSTICE. THERE IS JUST ME. (Death, Discworld)
 

PhillipK

 BeitragFr, Okt 07, 2011 19:55
Antworten mit Zitat
Benutzer-Profile anzeigen
Entschuldige, da war ich wohl blöd. Das mach ich manchmal zwar absichtlich, allerdings diesmal nicht.

Wie wärs mit einer Merge-funktion für 2 hintereinanderliegende Beiträge vom selben poster? *g* Wenn mans bemerkt, vermerkt man, das man seinen beitrag mit dem vorherigen zusammenfügen möchte und zack, inhalt aus 2) wird in inhalt von 1) eingefügt, 2) wird gelöscht.

*hust*


Mittlerweile habe ich mein Problem gefunden. Er findet nun wieder wege, aber entgegen der erwartungen: Langsamer als mit den TList.
Das liegt vllt am stetigen neusortieren des Arrays - da ich gute 5 Knoten pro durchlauf adde, dürfte das einfach zu viel sein.
Wenn ich durch das System durchgestiegen bin, passe ich es eventuell auf meinen A* algorythmus an - mehrere Arrays für verschiedene Prioritätstiefen. dann müssen nur ein wertebereich neu sortiert werden.
Mit einem Array of Arrays sollte das kein akt sein Smile

Neue Antwort erstellen


Übersicht BlitzMax, BlitzMax NG Beginners-Corner

Nach Oben

Gehe zu:

Powered by phpBB © 2001 - 2006, phpBB Group