F(x)=g(x)+h(x)...und nun in eine Liste. Bahnhof?

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

	OldSkool90 Betreff: F(x)=g(x)+h(x)...und nun in eine Liste. Bahnhof?	Do, Mai 13, 2010 23:56 Antworten mit Zitat
Tja lieb Gemeinschaft, Tut mir leid wieder zu stören, aber ich habe ein Problem. Eigentlich 2, aber egal. Ich versuche mich an Wegfindung (immernoch) und stecke fest. Mein Problem ist folgendes: Ich habe G(x) und H(x) [laut Manhattan Heuristik müsste es stimmen ] und folglich auch f(x). Das eigentliche PRoblem ist, dass mir ein Ansatz fehlt, wie ich alle nötigen Variablen und Datenfelder in eine Liste speicher und diese später auslese. Normalerweise würde ich es wieder 12 Stunden lang selbst probieren, aber es ist schon spät und wieder paar Biere später und bin unmotiviert. Hier mein Code: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] SuperStrict Type Waypoint Field Wx:Float[10] Field Wy:Float[10] Field G:Int[8] Field H:Int[8] Field F:Int[8] Global wpList:TList = CreateList() EndType Type Tile Extends Waypoint Field tx:Int[15] Field ty:Int[10] Field tID:Byte[256] EndType Type Target Extends Tile Field tgx:Int=9 Field tgy:Int=7 EndType Type Player Extends Target Field px:Byte = 5 Field py:Byte = 5 Method DisplayTiles() For Local xcount:Byte = 0 To 14 tx[xcount] = xcount32 For Local ycount:Byte = 0 To 9 ty[ycount] = ycount32 SetColor 255,255,255 DrawRect tx[xcount]+2,ty[ycount]+2,30,30 Next Next SetColor 255,0,0 DrawRect px32+2,py32+2,30,30 SetColor 0,255,0 DrawRect tgx32+2,tgy32+2,30,30 EndMethod Method MakeWaypoint() For Local i:Byte = 0 To 7 wx[i]=((Floor(Sin(i45)+0.5))+px) wy[i]=((Floor(Cos(i45)+0.5))+py) G[i] = Abs(px-(wx[i]))+Abs(py-(wy[i])) H[i] = Abs(wx[i]-tgx)+Abs(wy[i]-tgy) F[i] = G[i] + H[i] SetColor 200,200,200 DrawRect wx[i]32+2,wy[i]32+2,30,30 SetColor 0,0,0 DrawText G[i],wx[i]32+2,wy[i]32+2+30-12 DrawText H[i],wx[i]32+32-10,wy[i]32+2+30-12 DrawText F[i],wx[i]32+2,wy[i]32+2 Next EndMethod Function Create:Player() Local a:Player = New Player Return a EndFunction EndType Local Render:Player Render = Player.Create() Graphics 482,322,0 While Not KeyHit(key_escape) Cls Render.DisplayTiles() Render.MakeWaypoint() FlushKeys() Flip Wend EndGraphics Einiges mag merkwürdig erscheinen, aber ich bin ja auch längst nich fertig. Hoffe, dass mir jemand helfen kann. mfg, OldSkool90

OldSkool90

Betreff: F(x)=g(x)+h(x)...und nun in eine Liste. Bahnhof?

Do, Mai 13, 2010 23:56
Antworten mit Zitat

Tja lieb Gemeinschaft,
Tut mir leid wieder zu stören, aber ich habe ein Problem. Eigentlich 2, aber egal.
Ich versuche mich an Wegfindung (immernoch) und stecke fest. Mein Problem ist folgendes:
Ich habe G(x) und H(x) [laut Manhattan Heuristik müsste es stimmen Very Happy

] und folglich auch f(x).
Das eigentliche PRoblem ist, dass mir ein Ansatz fehlt, wie ich alle nötigen Variablen und Datenfelder in eine Liste speicher und diese später auslese.
Normalerweise würde ich es wieder 12 Stunden lang selbst probieren, aber es ist schon spät und wieder paar Biere später und bin unmotiviert. Very Happy

Hier mein Code:
BlitzMax: [AUSKLAPPEN]

SuperStrict

Type Waypoint
	Field Wx:Float[10]
	Field Wy:Float[10]
	Field G:Int[8]
	Field H:Int[8]
	Field F:Int[8]
	
	Global wpList:TList = CreateList()

EndType

Type Tile Extends Waypoint
	Field tx:Int[15]
	Field ty:Int[10]
	Field tID:Byte[256]
EndType

Type Target Extends Tile
	Field tgx:Int=9
	Field tgy:Int=7
EndType

Type Player Extends Target
	Field px:Byte = 5
	Field py:Byte = 5
	
	Method DisplayTiles()
		For Local xcount:Byte = 0 To 14
			tx[xcount] = xcount*32
		For Local ycount:Byte = 0 To 9
			ty[ycount] = ycount*32
				SetColor 255,255,255
				DrawRect tx[xcount]+2,ty[ycount]+2,30,30
		Next
		Next
			SetColor 255,0,0
			DrawRect px*32+2,py*32+2,30,30
			SetColor 0,255,0
			DrawRect tgx*32+2,tgy*32+2,30,30
	EndMethod
	
	Method MakeWaypoint()
		For Local i:Byte = 0 To 7
		
		
			wx[i]=((Floor(Sin(i*45)+0.5))+px)
			wy[i]=((Floor(Cos(i*45)+0.5))+py)
			G[i] = Abs(px-(wx[i]))+Abs(py-(wy[i]))
			H[i] = Abs(wx[i]-tgx)+Abs(wy[i]-tgy)
			F[i] = G[i] + H[i]
			
			SetColor 200,200,200
				DrawRect wx[i]*32+2,wy[i]*32+2,30,30
			SetColor 0,0,0
				DrawText G[i],wx[i]*32+2,wy[i]*32+2+30-12
				DrawText H[i],wx[i]*32+32-10,wy[i]*32+2+30-12
				DrawText F[i],wx[i]*32+2,wy[i]*32+2
			Next
	EndMethod	
		
	Function Create:Player()
		Local a:Player = New Player
		Return a
	EndFunction
	
EndType

Local Render:Player
Render = Player.Create()

Graphics 482,322,0
While Not KeyHit(key_escape)
Cls
	
Render.DisplayTiles()
Render.MakeWaypoint()

FlushKeys()
Flip
Wend
EndGraphics

Einiges mag merkwürdig erscheinen, aber ich bin ja auch längst nich fertig.
Hoffe, dass mir jemand helfen kann.
mfg,
OldSkool90

	Skabus	Fr, Mai 14, 2010 1:50 Antworten mit Zitat
Naja wenn du einen A*-Algorithmus implementieren willst, hast du ja stehts folgende Datenstrukturen: Eine Datenstruktur für dein Feld, in dem die Informationen für begehbare und nicht begehbare Felder drinstehen, sowie(ganz wichtig) Startpunkt und Endpunkt deiner Routine! Zum errechnen des Wege benötigst du dann eine sog. "Open List" und eine "Closed List", in denen dann der Algorithmus die Zwischenschritte speichert bzw. die letzendlichen Wegpunkte enthält. Wichtig für die ClosedList wäre noch, dass jeder Wegpunkt der ClosedList ihren Vorgänger kennt. Das wird später nötig, damit bei Mehrdeutigkeiten der optimale Pfad zurückverfolgt wird... Es gibt für B3D ein tolles Tutorial, mit dem ich damals recht problemlos sowas implementiert bekommen habe: http://www.policyalmanac.org/g...al_de.html Jetzt verstehe ich nur dein konkretes Problem nicht.Dein 2D-Feld(bei 3D hab ich kA,müsste aber ähnlich gehen, nur dass dort nicht zwangsläufig ein Feld mit homogenen Informationen ist und da afaik eh andere Algos relevant sind) speicherst du als Array ab(haste ja bereits denke ich), deine OpenList und ClosesList sollte Punkte(x,y) als Daten aufnehmen, die aktuellen Wegkosten sollten beachtet werden und die Elemente der ClosedList sollten den Vorgängerknoten aufnehmen können.... Ich hoffe das hilft dir erstmal weiter, wenn nicht einfach weiterfragen^^ MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Fr, Mai 14, 2010 1:50
Antworten mit Zitat

Naja wenn du einen A*-Algorithmus implementieren willst, hast du ja stehts folgende Datenstrukturen:

Eine Datenstruktur für dein Feld, in dem die Informationen für begehbare und nicht begehbare Felder
drinstehen, sowie(ganz wichtig) Startpunkt und Endpunkt deiner Routine!

Zum errechnen des Wege benötigst du dann eine sog. "Open List" und eine "Closed List", in denen
dann der Algorithmus die Zwischenschritte speichert bzw. die letzendlichen Wegpunkte enthält.

Wichtig für die ClosedList wäre noch, dass jeder Wegpunkt der ClosedList ihren Vorgänger kennt.
Das wird später nötig, damit bei Mehrdeutigkeiten der optimale Pfad zurückverfolgt wird...

Es gibt für B3D ein tolles Tutorial, mit dem ich damals recht problemlos sowas implementiert bekommen habe:

http://www.policyalmanac.org/g...al_de.html

Jetzt verstehe ich nur dein konkretes Problem nicht.Dein 2D-Feld(bei 3D hab ich kA,müsste aber ähnlich gehen, nur dass dort nicht zwangsläufig ein Feld mit homogenen Informationen ist und da afaik
eh andere Algos relevant sind) speicherst du als Array ab(haste ja bereits denke ich),
deine OpenList und ClosesList sollte Punkte(x,y) als Daten aufnehmen, die aktuellen Wegkosten sollten beachtet werden und die Elemente der ClosedList sollten den Vorgängerknoten aufnehmen können....

Ich hoffe das hilft dir erstmal weiter, wenn nicht einfach weiterfragen^^

MfG Ska

"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat

aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit!
Ein SNES-RPG mit Handels- und Wirtschaftselemente.
Infos?Hier: http://www.blitzforum.de/worklogs/234/
Besucht meine Seite:
www.seelenfriedhof.de.vu

	OldSkool90	Fr, Mai 14, 2010 11:27 Antworten mit Zitat
hmmm. Ein Problem ist, dass ich nicht in der Lage bin etwas in eine Liste zu speichern. Bmax meckert ständig rum: "määää das isn float...määä das isn type....määää ich will nen object". Ja, aber was bitte ist ein Object? Ist es denn in Bmax nicht möglich, einfach mal Koordinaten in eine Liste zu werfen?

OldSkool90

Fr, Mai 14, 2010 11:27
Antworten mit Zitat

hmmm. Ein Problem ist, dass ich nicht in der Lage bin etwas in eine Liste zu speichern. Bmax meckert ständig rum: "määää das isn float...määä das isn type....määää ich will nen object". Ja, aber was bitte ist ein Object? Ist es denn in Bmax nicht möglich, einfach mal Koordinaten in eine Liste zu werfen?

	Skabus	Fr, Mai 14, 2010 11:29 Antworten mit Zitat
Hm das klingt für mich, als würdest du irgendwas mit den Types falsch machen... Zeig doch einfach mal den Fehler und die entsprechende Codezeile, dann kann man das ganze auch besser nachvollziehen^^ Mein A*-Algo für Aves Certim funztin BMax wunderbar, an BMax solls also net liegen MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Fr, Mai 14, 2010 11:29
Antworten mit Zitat

Hm das klingt für mich, als würdest du irgendwas mit den Types falsch machen...

Zeig doch einfach mal den Fehler und die entsprechende Codezeile, dann kann man das ganze auch besser
nachvollziehen^^

Mein A*-Algo für Aves Certim funztin BMax wunderbar, an BMax solls also net liegen Very Happy

MfG Ska

	OldSkool90	Fr, Mai 14, 2010 11:34 Antworten mit Zitat
Ich habe ja in meinem Code oben nen Haufen Types und im letzten Type eine For Next Schleife in der die Wegpunkte erstellt und bewertet werden. Vorher Habe ich eine Liste erstellt: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Global wpList:TList = CreateList() Und jetzt möchte ich die Koordinaten der Wegpunkte bei Jedem For Next Zyklus abspeichern: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] ListAddLast(wpList,wx[i]) macht er aber nich, weil es kein Object is. Wie mache ich denn aus einem Array ein Object? Oder allgemein aus Variablen?

OldSkool90

Fr, Mai 14, 2010 11:34
Antworten mit Zitat

Ich habe ja in meinem Code oben nen Haufen Types und im letzten Type eine For Next Schleife in der die Wegpunkte erstellt und bewertet werden. Vorher Habe ich eine Liste erstellt:
BlitzMax: [AUSKLAPPEN]

	Global wpList:TList = CreateList()

Und jetzt möchte ich die Koordinaten der Wegpunkte bei Jedem For Next Zyklus abspeichern:
BlitzMax: [AUSKLAPPEN]

ListAddLast(wpList,wx[i])

macht er aber nich, weil es kein Object is. Wie mache ich denn aus einem Array ein Object? Oder allgemein aus Variablen?

	mpmxyz	Fr, Mai 14, 2010 11:46 Antworten mit Zitat
Ich fange erst einmal von einer anderen Richtung an: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Field Wx:Float[10] Field Wy:Float[10] Field G:Int[8] Field H:Int[8] Field F:Int[8] Das verstehe ich nicht ganz. Hast du so viel getrunken, dass du jeden Waypoint 10fach gesehen hast und dir dachtest denen 10 Positionen zu geben? Warum gibt es für die Wegsuche dann nur 8 Datensätze? Damit man es mit der Wegsuche relativ einfach hat, sollte jeder Waypoint nur eine Position haben. Zu "Object": "Object" ist eine Art Oberbegriff der Klassen. Jedes Objekt einer Klasse ist auch ein "Object". Es verhält sich bei jeder Klasse so, als wenn sie von "Object" erbt. Arrays sind Objekte. Du möchtest aber Zahlen abspeichern. Dafür musst du dir eine eigene Klasse schreiben. BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Type TFloat Field value:Float EndType Aber: Ich habe bei A-Star keinen Type für Zahlen gebraucht. Ich nutze dort Knoten und Verbindungen. Viel mehr braucht man eigentlich nicht, da diese dann in die entsprechenden Listen geschrieben werden. mfG mpmxyz
Moin Moin! Projekte: DBPC CodeCruncher Mandelbrot-Renderer

mpmxyz

Fr, Mai 14, 2010 11:46
Antworten mit Zitat

Ich fange erst einmal von einer anderen Richtung an:
BlitzMax: [AUSKLAPPEN]

	Field Wx:Float[10]
	Field Wy:Float[10]
	Field G:Int[8]
	Field H:Int[8]
	Field F:Int[8]

Das verstehe ich nicht ganz. Hast du so viel getrunken, dass du jeden Waypoint 10fach gesehen hast und dir dachtest denen 10 Positionen zu geben? Wink

Warum gibt es für die Wegsuche dann nur 8 Datensätze?
Damit man es mit der Wegsuche relativ einfach hat, sollte jeder Waypoint nur eine Position haben.

Zu "Object":
"Object" ist eine Art Oberbegriff der Klassen. Jedes Objekt einer Klasse ist auch ein "Object".
Es verhält sich bei jeder Klasse so, als wenn sie von "Object" erbt.

Arrays sind Objekte.
Du möchtest aber Zahlen abspeichern.
Dafür musst du dir eine eigene Klasse schreiben.
BlitzMax: [AUSKLAPPEN]

Type TFloat
   Field value:Float
EndType

Aber:
Ich habe bei A-Star keinen Type für Zahlen gebraucht.
Ich nutze dort Knoten und Verbindungen. Viel mehr braucht man eigentlich nicht, da diese dann in die entsprechenden Listen geschrieben werden.
mfG
mpmxyz

Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

	OldSkool90	Fr, Mai 14, 2010 11:55 Antworten mit Zitat
Ups naja die 10 war zu viel Aber nur eine? Ich wollte immer 8 nehmen, weil ich ja eh in 8 RIchtungen abtaste. Soll ich nur eine position nehmen und den Wegpunkt immer wieder neu erschaffen? Und wie löst man das ohne Types? Einfach ein 2D Array erstellen? Also Arr[x,y] und den G-score und H-score erst nach der Positionierung des Wegpunktes errechnen?

OldSkool90

Fr, Mai 14, 2010 11:55
Antworten mit Zitat

Ups naja die 10 war zu viel Very Happy

Aber nur eine? Ich wollte immer 8 nehmen, weil ich ja eh in 8 RIchtungen abtaste.
Soll ich nur eine position nehmen und den Wegpunkt immer wieder neu erschaffen?

Und wie löst man das ohne Types? Einfach ein 2D Array erstellen? Also Arr[x,y] und den G-score und H-score erst nach der Positionierung des Wegpunktes errechnen?

	Skabus	Fr, Mai 14, 2010 12:16 Antworten mit Zitat
Du solltest dir evtl. die Bedeutung von Types nochmal in Erinnerung rufen: Types definiert einen mehr oder weniger "eigenen Datentypen"...da z.B. nen Int eben nur exakt einen Wert speichern kann...willst du z.B. nen Punkt mit mehreren Komponenten(x,y,z,u,v,w,bla) dann musst du eben nen Type definieren, falls es die Datenstruktur net schon gibt... Bei dem Wegfindungsproblem benötigst du wie gesagt am besten Listen, da du im dynamischen Falle, dass sich Start oder Endpunkt ändern nicht weißt wie viele Objekte deine Liste enthält...können 2 sein, können auch hundert sein, je nach Größe des Feldes und den Positionen... Dass du alle 8 Richtungen abtasten willst hat nicht zwangsläufig was mit deiner Datenstruktur zu tun. Du willst ja ausgehend vom Startpunkt in alle 8 Richtungen gehen.Das kann dein Algo für dich erledigen! Die Datenstruktur der OpenList udn ClosedList braucht nur Wissen über: "X-Koordinate" "Y-Koordinate" "Wegkosten bis zu diesem Punkt"...heißt: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Type WayPoint Field x; Field y; Field cost; End Type Deine Liste an sich kannst du dann mit den Waypoints füllen und mit einer For-Each-Schleife kannst du sie nach belieben auslesen lassen: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Graphics 800,600 Global list:TList =CreateList() Type bla Field value:Int End Type Local bla1:bla = New bla Local bla2:bla = New bla Local bla3:bla = New bla Local bla4:bla = New bla bla1.value = 1 bla2.value = 2 bla3.value = 3 bla4.value = 4 'Elemente werden zur Liste hinzugefügt ListAddLast(list,bla1) ListAddLast(list,bla2) ListAddLast(list,bla3) ListAddLast(list,bla4) For b:bla = EachIn list Print String(b.value) Next Wenn du es nicht ganz so kompliziert haben willst und kein Prob mit Speicherverschwendung hast, kannst du für OpenList und ClosedList auch einen Array mit deinen WayPoint-Type machen. Also: BlitzMax: [AUSKLAPPEN] [EINKLAPPEN] Local/Global closedList:WayPoint[dimensionOfMap*dimensionOfMap] Ist aber net so die feinste Programmierart^^ MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Fr, Mai 14, 2010 12:16
Antworten mit Zitat

Du solltest dir evtl. die Bedeutung von Types nochmal in Erinnerung rufen:

Types definiert einen mehr oder weniger "eigenen Datentypen"...da z.B. nen Int eben nur exakt einen Wert speichern kann...willst du z.B. nen Punkt mit mehreren Komponenten(x,y,z,u,v,w,bla) dann musst du
eben nen Type definieren, falls es die Datenstruktur net schon gibt...

Bei dem Wegfindungsproblem benötigst du wie gesagt am besten Listen, da du im dynamischen Falle, dass sich Start oder Endpunkt ändern nicht weißt wie viele Objekte deine Liste enthält...können 2 sein, können
auch hundert sein, je nach Größe des Feldes und den Positionen...

Dass du alle 8 Richtungen abtasten willst hat nicht zwangsläufig was mit deiner Datenstruktur zu tun.
Du willst ja ausgehend vom Startpunkt in alle 8 Richtungen gehen.Das kann dein Algo für dich erledigen!

Die Datenstruktur der OpenList udn ClosedList braucht nur Wissen über: "X-Koordinate" "Y-Koordinate" "Wegkosten bis zu diesem Punkt"...heißt:

BlitzMax: [AUSKLAPPEN]



Type WayPoint

Field x;
Field y;
Field cost;

End Type

Deine Liste an sich kannst du dann mit den Waypoints füllen und mit einer For-Each-Schleife kannst du sie nach belieben auslesen lassen:

BlitzMax: [AUSKLAPPEN]


Graphics 800,600 

Global list:TList =CreateList()

Type bla

Field value:Int


End Type

Local bla1:bla = New bla
Local bla2:bla = New bla
Local bla3:bla = New bla
Local bla4:bla = New bla

bla1.value = 1
bla2.value = 2
bla3.value = 3
bla4.value = 4




'Elemente werden zur Liste hinzugefügt
ListAddLast(list,bla1)
ListAddLast(list,bla2)
ListAddLast(list,bla3)
ListAddLast(list,bla4)


For b:bla = EachIn list

Print String(b.value)

Next

Wenn du es nicht ganz so kompliziert haben willst und kein Prob mit Speicherverschwendung hast, kannst du für OpenList und ClosedList auch einen Array mit deinen WayPoint-Type machen.
Also:

BlitzMax: [AUSKLAPPEN]



Local/Global closedList:WayPoint[dimensionOfMap*dimensionOfMap]

Ist aber net so die feinste Programmierart^^

MfG Ska

	mpmxyz	Fr, Mai 14, 2010 12:18 Antworten mit Zitat
Jeder Wegpunkt hat eine Position, da er nicht an mehreren Orten gleichzeitig sein kann. Darin kann man sich einig sein, oder? Verbindungen zwischen Wegpunkten würde ich nicht über weitere Positionen herstellen. Stattdessen nimmst du einfach pro Wegpunkt eine Liste, in der steht, mit welchen anderen Wegpunkten er verbunden ist. Jeder Wegpunkt hat genau ein "g", die Länge des momentan kürzesten bekannten Weges zum Punkt, ein "h", die Abschätzung des restlichen Weges, und ein Feld, das auf den Vorgängerpunkt des kürzesten bekannten Weges zeigt, wenn schon ein Weg zu diesem Punkt führt. Die bekannten und noch nicht abgeschlossenen Wegpunkte sind in der Open List gespeichert. Wenn man es richtig macht, braucht man sogar keine Closed List. mfG mpmxyz Edit: Wie sieht es eigentlich mit deinem Verständnis zu A-Star aus? Soll ich etwas weiter beim "Urschleim" anfangen?
Moin Moin! Projekte: DBPC CodeCruncher Mandelbrot-Renderer

mpmxyz

Fr, Mai 14, 2010 12:18
Antworten mit Zitat

Jeder Wegpunkt hat eine Position, da er nicht an mehreren Orten gleichzeitig sein kann. Darin kann man sich einig sein, oder?
Verbindungen zwischen Wegpunkten würde ich nicht über weitere Positionen herstellen.
Stattdessen nimmst du einfach pro Wegpunkt eine Liste, in der steht, mit welchen anderen Wegpunkten er verbunden ist.
Jeder Wegpunkt hat genau ein "g", die Länge des momentan kürzesten bekannten Weges zum Punkt, ein "h", die Abschätzung des restlichen Weges, und ein Feld, das auf den Vorgängerpunkt des kürzesten bekannten Weges zeigt, wenn schon ein Weg zu diesem Punkt führt.
Die bekannten und noch nicht abgeschlossenen Wegpunkte sind in der Open List gespeichert.
Wenn man es richtig macht, braucht man sogar keine Closed List.
mfG
mpmxyz
Edit: Wie sieht es eigentlich mit deinem Verständnis zu A-Star aus? Soll ich etwas weiter beim "Urschleim" anfangen? Wink

Moin Moin!
Projekte: DBPC CodeCruncher Mandelbrot-Renderer

	OldSkool90	Fr, Mai 14, 2010 12:35 Antworten mit Zitat
Naja ich hab von Anfang an mit dem A* Tutorial gearbeitet. Aber da es da keinen Code gibt, musste ich selber nachdenken (was auch gut so is) Ich erschaffe ja in alle Richtungen je einen Waypoint und berechne die Kosten, um diesen zu erreichen und addiere sie mit den Kosten vom jeweiligen Waypoint zum Ziel. also F(x) = G(x) + H(x) Für H(x) hab ich einfach die Distanz in x und y Richtung genommen, weil es erstmal simpler ist. Ich muss meine Wegpunkte also in eine Liste speichern. Die Wegpunkte, die ich bereits abgewandert bin kommen dann in die closedlist. Also kommen in die closedlist nur die relevanten Wegpunkte. Soweit richtig?^^ EDIT: Jetz hab ich ganz vergessen Skabus für seine Listen erklärung zu danken Also danke Skabus, ich seh da jetz bissl besser durch und schreib den Code komplett neu. Schritt für Schritt...AuBacke

OldSkool90

Fr, Mai 14, 2010 12:35
Antworten mit Zitat

Naja ich hab von Anfang an mit dem A* Tutorial gearbeitet. Aber da es da keinen Code gibt, musste ich selber nachdenken Very Happy

(was auch gut so is)

Ich erschaffe ja in alle Richtungen je einen Waypoint und berechne die Kosten, um diesen zu erreichen und addiere sie mit den Kosten vom jeweiligen Waypoint zum Ziel.
also F(x) = G(x) + H(x)
Für H(x) hab ich einfach die Distanz in x und y Richtung genommen, weil es erstmal simpler ist.

Ich muss meine Wegpunkte also in eine Liste speichern. Die Wegpunkte, die ich bereits abgewandert bin kommen dann in die closedlist. Also kommen in die closedlist nur die relevanten Wegpunkte.

Soweit richtig?^^

EDIT:
Jetz hab ich ganz vergessen Skabus für seine Listen erklärung zu danken Very Happy

Also danke Skabus, ich seh da jetz bissl besser durch und schreib den Code komplett neu.
Schritt für Schritt...AuBacke Very Happy

	Skabus	Fr, Mai 14, 2010 12:50 Antworten mit Zitat
Sollte soweit korrekt sein... Die Heueristik ist in der Mannhatten-Distanz afaik, die Luftline zwischen Strat und Endpunkt. Somit ist H(x) mit f = x +y schon dafür richtig. Du speicherst ausgehend von deinem aktuellen Punkt erstmal alle Punkte in die openList oder wie auch immer du das nennen willst.Für jeden Punkt errechnest du die Kosten, welche sich ja aus den aktuell bereits gemachten Kosten und den Kosten für Bewegung + Heueristik errechnet. Dann prüfst du welche von den aktuellen Punkten am günstigen ist, speicherst das Ergebnis in die closedList und machst weiter. Das Problem ist aber, dass der Algorithmus stellenweise mehr Elemente in der ClosedList hat als nötig. Beispiel Startpunkt: Da es hier noch keine Kosten gibt kommen erstmal alle Punkte deren Werte günstig sind in die closedList. Erst im 2 Schritt merkt der Algo, dass er an einer Stelle in die falsche Richtung geht. Dann verlässt er diesen Pfad zwar, hat aber noch Elemente an stellen die nicht zum optimalen Pfad gehören. Darum mein Tipp: Speicher neben Position und Kosten noch den Vorgänger.Dann kannste dir komplett sparen den Rückweg irgendwie zu vermurksten.Du gehst vom Endpunkt einfach rückwärts und hast was du willst^^ MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Fr, Mai 14, 2010 12:50
Antworten mit Zitat

Sollte soweit korrekt sein...

Die Heueristik ist in der Mannhatten-Distanz afaik, die Luftline zwischen Strat und Endpunkt.
Somit ist H(x) mit f = x +y schon dafür richtig.

Du speicherst ausgehend von deinem aktuellen Punkt erstmal alle Punkte in die openList oder wie auch immer du das nennen willst.Für jeden Punkt errechnest du die Kosten, welche sich ja aus den aktuell bereits gemachten Kosten und den Kosten für Bewegung + Heueristik errechnet.

Dann prüfst du welche von den aktuellen Punkten am günstigen ist, speicherst das Ergebnis in die closedList und machst weiter.

Das Problem ist aber, dass der Algorithmus stellenweise mehr Elemente in der ClosedList hat als nötig.
Beispiel Startpunkt:

Da es hier noch keine Kosten gibt kommen erstmal alle Punkte deren Werte günstig sind in die closedList.
Erst im 2 Schritt merkt der Algo, dass er an einer Stelle in die falsche Richtung geht.
Dann verlässt er diesen Pfad zwar, hat aber noch Elemente an stellen die nicht zum optimalen
Pfad gehören.

Darum mein Tipp: Speicher neben Position und Kosten noch den Vorgänger.Dann kannste dir
komplett sparen den Rückweg irgendwie zu vermurksten.Du gehst vom Endpunkt einfach rückwärts und hast was du willst^^

MfG Ska

	OldSkool90	Fr, Mai 14, 2010 12:56 Antworten mit Zitat
Also immer zusätzlich x und y des Vorgängers speichern und im Falle einer Verfrickelung einfach zurückgehen?

OldSkool90

Fr, Mai 14, 2010 12:56
Antworten mit Zitat

Also immer zusätzlich x und y des Vorgängers speichern und im Falle einer Verfrickelung einfach zurückgehen?

	Skabus	Fr, Mai 14, 2010 13:00 Antworten mit Zitat
OldSkool90 hat Folgendes geschrieben: Also immer zusätzlich x und y des Vorgängers speichern und im Falle einer Verfrickelung einfach zurückgehen? Nein besser ist du speicherst den gesamten Vorgängerknoten....oder du arbeitest mit LinkList, das sollte auf das selbe rauskommen. Der Sinn ist ja nicht zu wissen, welche Position der Vorgängerknoten hat, sondern sich dann an den Knoten rückwärts entlangzuhangeln um den optimalen Pfad zu finden.... Steht wie gesagt auch alles in dem Tutorial was ich gepostet habe MfG Ska
"In einer so verrückten Welt, kann man um in ihr zu überleben nur eines tun, nämlich eben jenes werden: Ein Verrückter!" -Selbstzitat aktuelles Projekt: Aves Certim - Der Galgen ist nicht weit! Ein SNES-RPG mit Handels- und Wirtschaftselemente. Infos?Hier: http://www.blitzforum.de/worklogs/234/ Besucht meine Seite: www.seelenfriedhof.de.vu

Skabus

Fr, Mai 14, 2010 13:00
Antworten mit Zitat

OldSkool90 hat Folgendes geschrieben:

Also immer zusätzlich x und y des Vorgängers speichern und im Falle einer Verfrickelung einfach zurückgehen?

Nein besser ist du speicherst den gesamten Vorgängerknoten....oder du arbeitest mit LinkList, das sollte
auf das selbe rauskommen.

Der Sinn ist ja nicht zu wissen, welche Position der Vorgängerknoten hat, sondern sich dann an den Knoten rückwärts entlangzuhangeln um den optimalen Pfad zu finden....

Steht wie gesagt auch alles in dem Tutorial was ich gepostet habe Wink

MfG Ska

	OldSkool90	Fr, Mai 14, 2010 13:04 Antworten mit Zitat
Ja mit dem Tutorial habe ich ja von Anfang an gearbeitet. Habe mich aber in den Bildchen verloren Hmm ich teste das mit den Listen erstmal durch und schaue wie ich die Daten korrekt auslese^^

OldSkool90

Fr, Mai 14, 2010 13:04
Antworten mit Zitat

Ja mit dem Tutorial habe ich ja von Anfang an gearbeitet. Habe mich aber in den Bildchen verloren Very Happy

Hmm ich teste das mit den Listen erstmal durch und schaue wie ich die Daten korrekt auslese^^

Übersicht

BlitzMax, BlitzMax NG

Beginners-Corner

Nach Oben

BlitzBasic Portal

F(x)=g(x)+h(x)...und nun in eine Liste. Bahnhof?

Betreff: F(x)=g(x)+h(x)...und nun in eine Liste. Bahnhof?