AStar A* Pathfinding Algorithmus - Umsetzungs Probleme

Übersicht

BlitzBasic

Allgemein

	Schrolli Betreff: AStar A* Pathfinding Algorithmus - Umsetzungs Probleme	Sa, Dez 25, 2010 21:35 Antworten mit Zitat
Schönen Guten Abend und ein Frohes Fest Follgendes Problem: http://www.policyalmanac.org/g...al_de.html Schöne Seite - Schön verständlich ... Nur an der Umsetzung hapert es ein wenig. Der Beispiel code der dort downloadbar ist entzieht sich völlig meinem Verständniss, daher würde ich das ganze gerne Stück für Stück selbst zusammenfrickeln. Es läuft ja alles nach einem sich immer wieder wiederholenden Muster ab. Vondaher sollte das auch für mich machbar sein. Nur am Arbeitskonzept hapert es ein wenig. Evtl könnte mir ja jmd ein wenig unter die Arme greifen. Im moment verzwifel ich an dieser rekursifen Funktion welche immer die Felder um das momentane durchsucht und mir die G,H und F Werte errechnet. Mir fehlt einfach ein Ansatz. Danke schonmal Basti

Schrolli

Betreff: AStar A* Pathfinding Algorithmus - Umsetzungs Probleme

Sa, Dez 25, 2010 21:35
Antworten mit Zitat

Schönen Guten Abend und ein Frohes Fest Smile

Follgendes Problem:
http://www.policyalmanac.org/g...al_de.html
Schöne Seite - Schön verständlich ... Nur an der Umsetzung hapert es ein wenig.

Der Beispiel code der dort downloadbar ist entzieht sich völlig meinem Verständniss, daher würde ich das ganze gerne Stück für Stück selbst zusammenfrickeln. Es läuft ja alles nach einem sich immer wieder wiederholenden Muster ab. Vondaher sollte das auch für mich machbar sein. Nur am Arbeitskonzept hapert es ein wenig.

Evtl könnte mir ja jmd ein wenig unter die Arme greifen. Im moment verzwifel ich an dieser rekursifen Funktion welche immer die Felder um das momentane durchsucht und mir die G,H und F Werte errechnet.

Mir fehlt einfach ein Ansatz. Danke schonmal
Basti Smile

	Ana	Sa, Dez 25, 2010 23:41 Antworten mit Zitat
Ja nachdem Tutorial hab ich auch meinen A* geschrieben. Woran mangelst denn nun genau? Dir ist klar was eine rekursive Funktion ist und du verstehst wie der Algorithmus arbeitet? Dann wird das ganze solange ausgeführt, bis man am Ziel ist und dann werden die Alternativen überprüft. Ich helf würd dir gern helfen, aber ein bisschen mehr ansatz wäre schon gut.
Don't only practice your art, but force your way into its secrets, for it and knowledge can raise human to divine

Ana

Sa, Dez 25, 2010 23:41
Antworten mit Zitat

Ja nachdem Tutorial hab ich auch meinen A* geschrieben. Woran mangelst denn nun genau? Dir ist klar was eine rekursive Funktion ist und du verstehst wie der Algorithmus arbeitet? Dann wird das ganze solange ausgeführt, bis man am Ziel ist und dann werden die Alternativen überprüft. Ich helf würd dir gern helfen, aber ein bisschen mehr ansatz wäre schon gut.

Don't only practice your art,
but force your way into its secrets,
for it and knowledge
can raise human to divine

	Schrolli	So, Dez 26, 2010 1:40 Antworten mit Zitat
Oke Ich habe mir erst mal 2 Types erstellt, eben diese offene und diese geschlossene Liste. Dann trag ich zu Beginn den Startpunkt in die offene ein... und ab hier müsste ja dann die rekursive funktion beginnen richtig? Umliegende Felder ermitteln. Prüfen ob begehbar. In offene Liste. Soweit auch Richtig? Aber bei der konstruktion dieser rekursiven funktion scheiter ich ein wenig BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] For i = -1 To 1 Step 1 For j = -1 To 1 Step 1 If feld(x+i,y+j) <> 1 Then info.offen = New offen info\x = x+i info\y = y+j info\startx = x info\starty = y EndIf Next Next das wären jetzt erst mal alles außen rum. Ich übergeb an den Type seine Position und von wo das Feld angesprungen wurde... Ab da hört mein Ansatz dann ungf auf. Denkanstöße gewünscht Brauch jetzt ja noch diese Wegkosten. Also die geschätzte Entfernung zum Ziel und pro geprüften Feld die Wegkosten bis dahin um den besten Weg zu finden. Weis nicht wie ich das in der Schleife einbauen soll. Danke schon mal.... Basti

Schrolli

So, Dez 26, 2010 1:40
Antworten mit Zitat

Oke

Ich habe mir erst mal 2 Types erstellt, eben diese offene und diese geschlossene Liste. Dann trag ich zu Beginn den Startpunkt in die offene ein... und ab hier müsste ja dann die rekursive funktion beginnen richtig?

Umliegende Felder ermitteln. Prüfen ob begehbar. In offene Liste. Soweit auch Richtig?

Aber bei der konstruktion dieser rekursiven funktion scheiter ich ein wenig
BlitzBasic: [AUSKLAPPEN]

	For i = -1 To 1 Step 1
		For j = -1 To 1 Step 1
			
			If feld(x+i,y+j) <> 1 Then
					info.offen = New offen 
					info\x = x+i
					info\y = y+j
					info\startx = x
					info\starty = y
				EndIf	
			
		Next
	Next

das wären jetzt erst mal alles außen rum. Ich übergeb an den Type seine Position und von wo das Feld angesprungen wurde... Ab da hört mein Ansatz dann ungf auf. Denkanstöße gewünscht Smile

Brauch jetzt ja noch diese Wegkosten. Also die geschätzte Entfernung zum Ziel und pro geprüften Feld die Wegkosten bis dahin um den besten Weg zu finden. Weis nicht wie ich das in der Schleife einbauen soll.

Danke schon mal....
Basti

	Ana	So, Dez 26, 2010 4:37 Antworten mit Zitat
Das problem wenn du es so löst ist, dass du nun in jedemfall einen neuen Type erstellst, egal ob du das feld kennst oder nicht. Es ist einfacher, wenn du ein Array von Types in größe und breite der felder anlegst. BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Type Feld Field Begehbar Field openlist Field closelist Field distance Field vorgaenger.feld End Type Dim Array.feld(Breite,Hoehe) Nun verwendest du eine Funktion die die distance für jedes umliegende feld berechnet, falls es begehbar ist und nicht closelist = true ist und falls es Openlist = true hat, musst du noch überprüfen ob die distance nun geringer ist als vorher, wenn ja wird der verweis vorgaenger auf das aktuelle feld gestellt. Für den Fall, das es sich um ein unberührtes Feld handelt wird die distance ausgerechnet, vorgaenger wird auf die aktuelle position gesetzt. Nach dem alle felder überprüft wurden, wird das aktuelle auf die closelist gesetzt und das mit der geringsten distance, wird das neue aktuelle feld und drauf wird wieder die funktion angewendet.
Don't only practice your art, but force your way into its secrets, for it and knowledge can raise human to divine

Ana

So, Dez 26, 2010 4:37
Antworten mit Zitat

Das problem wenn du es so löst ist, dass du nun in jedemfall einen neuen Type erstellst, egal ob du das feld kennst oder nicht. Es ist einfacher, wenn du ein Array von Types in größe und breite der felder anlegst.
BlitzBasic: [AUSKLAPPEN]

Type Feld
        Field Begehbar
	Field openlist
	Field closelist
	Field distance
	Field vorgaenger.feld
End Type

Dim Array.feld(Breite,Hoehe)

Nun verwendest du eine Funktion die die distance für jedes umliegende feld berechnet, falls es begehbar ist und nicht closelist = true ist und falls es Openlist = true hat, musst du noch überprüfen ob die distance nun geringer ist als vorher, wenn ja wird der verweis vorgaenger auf das aktuelle feld gestellt.
Für den Fall, das es sich um ein unberührtes Feld handelt wird die distance ausgerechnet, vorgaenger wird auf die aktuelle position gesetzt.
Nach dem alle felder überprüft wurden, wird das aktuelle auf die closelist gesetzt und das mit der geringsten distance, wird das neue aktuelle feld und drauf wird wieder die funktion angewendet.

Don't only practice your art,
but force your way into its secrets,
for it and knowledge
can raise human to divine

	Schrolli	So, Dez 26, 2010 12:10 Antworten mit Zitat
Ana hat Folgendes geschrieben: Es ist einfacher, wenn du ein Array von Types in größe und breite der felder anlegst. An sich verständlich... Nur was das sein soll weis ich nicht? Was meinst du mir Array von Types? Evtl kleines Code bsp. dazu um funktionsweise deutlich zu machen? Danke Basti

Schrolli

So, Dez 26, 2010 12:10
Antworten mit Zitat

Ana hat Folgendes geschrieben:

Es ist einfacher, wenn du ein Array von Types in größe und breite der felder anlegst.

An sich verständlich... Nur was das sein soll weis ich nicht? Was meinst du mir Array von Types? Evtl kleines Code bsp. dazu um funktionsweise deutlich zu machen?

Danke
Basti

	Matthias	So, Dez 26, 2010 14:11 Antworten mit Zitat
Hay. @Schrolli Ich hatte damals mal ein Beispiel Programmiert wie mann A*Star Pathfinding einsetzen kann. Vieleicht hilft es dir weiter. https://www.blitzforum.de/foru...athfinding

Matthias

So, Dez 26, 2010 14:11
Antworten mit Zitat

Hay. @Schrolli

Ich hatte damals mal ein Beispiel Programmiert wie mann A*Star Pathfinding
einsetzen kann.

Vieleicht hilft es dir weiter. Smile

https://www.blitzforum.de/foru...athfinding

	Schrolli	So, Dez 26, 2010 14:19 Antworten mit Zitat
Könnte ich jetzt zwar verwenden, aber ganz nachvollziehen kann ichs nicht. Am liebsten wäre es mit echt, das ganze mit eurer Hilfe Stück für Stück selbst zusammenm zu frickeln. Dann weis ich wenigsten was passiert und kann auch was ändern. Trotzdem danke Matthias Basti

Schrolli

So, Dez 26, 2010 14:19
Antworten mit Zitat

Könnte ich jetzt zwar verwenden, aber ganz nachvollziehen kann ichs nicht.
Am liebsten wäre es mit echt, das ganze mit eurer Hilfe Stück für Stück selbst zusammenm zu frickeln.

Dann weis ich wenigsten was passiert und kann auch was ändern.

Trotzdem danke Matthias

Basti

	Ana	So, Dez 26, 2010 23:30 Antworten mit Zitat
Naja technisch gesehen ist ein Array genau wie eine Variable eine Adresse in deinem Speicher. Der Unterschied ist nur, dass ein Array dem Index entsprechend mehrfach den Speicher reserviert, und die Adressierung von "innen stehenden" Speicheradressen durch index * typelänge berechnet werden kann, und du keine liste oder keinen baum brauchst wenn du die types in einem eindeutigen Raster anordnest. Im klar Text wenn du den type auf der Position 4 runter 5 nach rechts haben willst, dann weißt du wo du im array suchen musst, und alle drum herumliegenden sind ebenfalls einfach zu erhalten. So kannst du die Types direkt adressieren, das ist bequemer und schneller. Und als Code, gehen wir davon aus, dass du den Weg als String speichern müsstest und eine Funktion hast, die den Weg zurück gibt, wenn du ihr die beiden Felder-Types übergibst. Hier mal der Weg von 4,5 nach 8,9 BlitzBasic: [AUSKLAPPEN] [EINKLAPPEN] Weg$ = Get_Way(Type_Array(4,5),Type_Array(8,9)) Function Get_way$(Start.Feld,Ziel.Feld) If Ziel.begehbar = False Or Start.begehbar = False Then Return "" ASTar(Start,Ziel) Return Pointer_direction$(s.feld,z.feld) End Function Function AStar(S.Feld,Z.Feld) S.closelist = True New_S.feld = Get_lowest_distance(s,z) If New_s = Null Then Astar(s.vorgaenger,z) Else Astar(new_S,z) EndIf End Function Function Pointer_direction$(s.feld,z.feld) ; nutzt vorgaenger um die relative position wieder zu geben und geht rekursiv den weg zurück Function Get_lowest_distance(s.feld,z.feld) ; ermittelt das umliegende Feld das nach schätzungen zum kürzesten Weg führt und setzt falls vorher kein kürzerer Weg ermittelt wurde, den vorgänger = s von dem neuen feld Dem Code fehlt natürlich noch einiges, z.B findet er so höchstens einen Weg nicht den kürzesten, aber du willst ihn ja selbst schreiben (find ich super!), sonst könntest du ja auch einfach wie mathias den von blitzbase kopieren.
Don't only practice your art, but force your way into its secrets, for it and knowledge can raise human to divine

Ana

So, Dez 26, 2010 23:30
Antworten mit Zitat

Naja technisch gesehen ist ein Array genau wie eine Variable eine Adresse in deinem Speicher. Der Unterschied ist nur, dass ein Array dem Index entsprechend mehrfach den Speicher reserviert, und die Adressierung von "innen stehenden" Speicheradressen durch index * typelänge berechnet werden kann, und du keine liste oder keinen baum brauchst wenn du die types in einem eindeutigen Raster anordnest. Im klar Text wenn du den type auf der Position 4 runter 5 nach rechts haben willst, dann weißt du wo du im array suchen musst, und alle drum herumliegenden sind ebenfalls einfach zu erhalten. So kannst du die Types direkt adressieren, das ist bequemer und schneller.

Und als Code, gehen wir davon aus, dass du den Weg als String speichern müsstest und eine Funktion hast, die den Weg zurück gibt, wenn du ihr die beiden Felder-Types übergibst. Hier mal der Weg von 4,5 nach 8,9
BlitzBasic: [AUSKLAPPEN]

Weg$ = Get_Way(Type_Array(4,5),Type_Array(8,9))

Function Get_way$(Start.Feld,Ziel.Feld)

	If Ziel.begehbar = False Or Start.begehbar = False Then Return ""
	
	ASTar(Start,Ziel)
	Return Pointer_direction$(s.feld,z.feld)
	
End Function


Function AStar(S.Feld,Z.Feld)
	S.closelist = True
	New_S.feld = Get_lowest_distance(s,z)
	If New_s = Null Then 
		Astar(s.vorgaenger,z)
	Else
		Astar(new_S,z)
	EndIf
End Function


	
Function Pointer_direction$(s.feld,z.feld) ; nutzt vorgaenger um die relative position wieder zu geben und geht rekursiv den weg zurück

Function Get_lowest_distance(s.feld,z.feld) ; ermittelt das umliegende Feld das nach schätzungen zum kürzesten Weg führt und setzt falls vorher kein kürzerer Weg ermittelt wurde, den vorgänger = s von dem neuen feld

Dem Code fehlt natürlich noch einiges, z.B findet er so höchstens einen Weg nicht den kürzesten, aber du willst ihn ja selbst schreiben (find ich super!), sonst könntest du ja auch einfach wie mathias den von blitzbase kopieren.

Don't only practice your art,
but force your way into its secrets,
for it and knowledge
can raise human to divine

	Schrolli	Mo, Dez 27, 2010 22:59 Antworten mit Zitat
Ich kann der ganzen Sache iwie nicht so ganz folgen, evtl ist es noch zu früh um über Pathfinding nachzudenken. Ich versteh den Ansatz Code technisch nicht ganz, etwas verwirrend alles... Basti Trotzdem Danke für eure Bemühungen

Schrolli

Mo, Dez 27, 2010 22:59
Antworten mit Zitat

Ich kann der ganzen Sache iwie nicht so ganz folgen, evtl ist es noch zu früh um über Pathfinding nachzudenken. Ich versteh den Ansatz Code technisch nicht ganz, etwas verwirrend alles...

Basti

Trotzdem Danke für eure Bemühungen

	Ana	Mo, Dez 27, 2010 23:25 Antworten mit Zitat
Eventuell, aber mit einer spezifischen Frage, kann ich dir auch eine spezifischere Antwort geben, bisher hab ich ja nur so halb geraten, was deine Probleme sein könnten.
Don't only practice your art, but force your way into its secrets, for it and knowledge can raise human to divine

Ana

Mo, Dez 27, 2010 23:25
Antworten mit Zitat

Eventuell, aber mit einer spezifischen Frage, kann ich dir auch eine spezifischere Antwort geben, bisher hab ich ja nur so halb geraten, was deine Probleme sein könnten.

Don't only practice your art,
but force your way into its secrets,
for it and knowledge
can raise human to divine

	Schrolli	Di, Dez 28, 2010 0:03 Antworten mit Zitat
Danke aber ich glaube das die Sache mit dem Pathfinding im moment doch noch etwas zu hoch ist. Und bevor ich mich ins Unglück stürze ... Ich habe begonnen einfach mal eine kleine Tile-Engine zu schreiben und versuche dabei noch ein paar Erfahrungen zu sammeln, bevor ich mich dann evtl nochmal an pathfinding herran wage. Basti

Schrolli

Di, Dez 28, 2010 0:03
Antworten mit Zitat

Danke

aber ich glaube das die Sache mit dem Pathfinding im moment doch noch etwas zu hoch ist. Und bevor ich mich ins Unglück stürze ... Very Happy

Ich habe begonnen einfach mal eine kleine Tile-Engine zu schreiben und versuche dabei noch ein paar Erfahrungen zu sammeln, bevor ich mich dann evtl nochmal an pathfinding herran wage.

Basti Smile

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

AStar A* Pathfinding Algorithmus - Umsetzungs Probleme

Betreff: AStar A* Pathfinding Algorithmus - Umsetzungs Probleme