Verständnisfrage zur Pathfinding-Methode A*

Übersicht

Sonstiges

Smalltalk

	Skabus Betreff: Verständnisfrage zur Pathfinding-Methode A*	Di, März 11, 2008 18:52 Antworten mit Zitat
Hallo^^ Ich beschäftige mich momentan mit ein paar Programmiertechniken und wollte mich des Interesses halber mal mit Pathfinding-Routinen beschäftigen. Dazu habe ich unter anderem dieses recht ordentliche Tutorial gefunden: http://www.blitzbase.de/artikel/path_1.htm Mein Problem dabei ist allerdings, dass ich da ein (kleines) Verständnisproblem bezüglich der Bewegungskostenrechnung habe....Laut etlichen Tutorials gilt ja hier die Formel: F=G+H F...Gesamt-Wegkosten G...Wegkosten vom Startpunkt (vererbt+1) H...Wegkosten zum Endpunkt (geschätzt) Soweit so gut.Das die Wegkosten vom Startpunkt pro Knotenpunkt um 1 erhöht wird leuchtet mir ein, was ich nicht verstehe ist folgendes: Der Wert H wird folgendermaßen abgeschätzt: Man addiert einfach die Höhen und Breiten-Differenz vom Knotenpunkt zum Zielpunkt. Also nach dieser Formel: H=ABS(KnotenX-ZielX)+ABS(KnotenY-ZielY) Ich verstehe erstens nicht wozu ich die theoretische Entfernung messen soll und warum ich sie mit meinen Wegkosten vom Startpunkt addieren soll. Ich habe bereits einige Skizzen gemacht und einiges durchgerechnet aber mir will nicht einleuchten wozu ich H dazuaddieren soll und was mir diese Größe sagt. Ich würde mich freuen wenn mir das jemand vielleicht etwas näher erläutern könnte, weil ich wie gesagt auf keine Lösung gestoßen bin! Danke im vorraus!^^ 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

Betreff: Verständnisfrage zur Pathfinding-Methode A*

Di, März 11, 2008 18:52
Antworten mit Zitat

Hallo^^

Ich beschäftige mich momentan mit ein paar Programmiertechniken und wollte mich des
Interesses halber mal mit Pathfinding-Routinen beschäftigen.
Dazu habe ich unter anderem dieses recht ordentliche Tutorial gefunden:

http://www.blitzbase.de/artikel/path_1.htm

Mein Problem dabei ist allerdings, dass ich da ein (kleines) Verständnisproblem bezüglich der
Bewegungskostenrechnung habe....Laut etlichen Tutorials gilt ja hier die Formel:

F=G+H

F...Gesamt-Wegkosten
G...Wegkosten vom Startpunkt (vererbt+1)
H...Wegkosten zum Endpunkt (geschätzt)

Soweit so gut.Das die Wegkosten vom Startpunkt pro Knotenpunkt um 1 erhöht wird leuchtet mir ein,
was ich nicht verstehe ist folgendes:

Der Wert H wird folgendermaßen abgeschätzt: Man addiert einfach die Höhen und Breiten-Differenz vom Knotenpunkt zum Zielpunkt. Also nach dieser Formel:

H=ABS(KnotenX-ZielX)+ABS(KnotenY-ZielY)

Ich verstehe erstens nicht wozu ich die theoretische Entfernung messen soll und warum ich sie mit
meinen Wegkosten vom Startpunkt addieren soll.

Ich habe bereits einige Skizzen gemacht und einiges durchgerechnet aber mir will nicht einleuchten wozu ich H dazuaddieren soll und was mir diese Größe sagt.

Ich würde mich freuen wenn mir das jemand vielleicht etwas näher erläutern könnte, weil
ich wie gesagt auf keine Lösung gestoßen bin!

Danke im vorraus!^^

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

	BladeRunner Moderator	Di, März 11, 2008 21:28 Antworten mit Zitat
Du beginnst mit wegkosten von Null. Die geschätzten Wegekosten entsprechen von hier den addierten Abständen auf beiden Achsen. (Oder, um genauer zu sein, der Wurzel der Abstandsquatrate als summe - das wäre der Pythagoras). Nun schaust du auf allen Nachbarfeldern wie sich die Wegekosten dort ergeben: dort ist es 1 (für den Weg) + der Abstände. Der geringste Wert ist der präferierte Weg. Auf jedem folgenden Feld wiederholt sich dieses Spiel nun, wobei immer die reinen (Also tatsächlich aufgebrachten) Wegekosten bis zu diesem Feld gespeichert werden und beim nächsten Feld herangezogen werden. Zudem wird bei jedem Feld überprüft ob es schon in der Liste besuchter Felder ist, denn dann ist eine Überprüfung idR nicht mehr notwendig (es wird ja schon mit geringeren Wegekosten von woanders erreicht). Beispiel Start ist 0,0, ziel 3,2 WK = WegeKosten bis zu diesem Feld (G) WG = geschätzte Kosten bis zum Ziel (H) 0,0 WK 0 WG 3+2=5 0,1 WK 1 WG 3,1 =4 1,0 WK 1 WG 2,2 = 4 A* nimmt den kürzesten in der Liste, und davon den ersten, also 0,1, von hier aus: 0,0 SCHON besucht 0,2 WK 2 WG 3,0 = 3 (WK 1+die gespeicherten 1 vom ersten Schritt) 1,1 WK 2 WG 2,1 = 3 selbes Spiel, 0,2 wird genommen: 0,1 schon besucht 0,3 WK 3 WG 3,1 = 4 1,2 WK 3 WG 2,0 = 2 Hier ist augenscheinlich der 2e Knoten (1,2) der bessere mit den geringsten Kosten. ...und so fort und so fort.
Zu Diensten, Bürger. Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3 Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64 B3D BMax MaxGUI Stolzer Gewinner des BAC#48, #52 & #92

BladeRunner

Moderator

Di, März 11, 2008 21:28
Antworten mit Zitat

Du beginnst mit wegkosten von Null. Die geschätzten Wegekosten entsprechen von hier den addierten Abständen auf beiden Achsen. (Oder, um genauer zu sein, der Wurzel der Abstandsquatrate als summe - das wäre der Pythagoras).
Nun schaust du auf allen Nachbarfeldern wie sich die Wegekosten dort ergeben: dort ist es 1 (für den Weg) + der Abstände. Der geringste Wert ist der präferierte Weg. Auf jedem folgenden Feld wiederholt sich dieses Spiel nun, wobei immer die reinen (Also tatsächlich aufgebrachten) Wegekosten bis zu diesem Feld gespeichert werden und beim nächsten Feld herangezogen werden. Zudem wird bei jedem Feld überprüft ob es schon in der Liste besuchter Felder ist, denn dann ist eine Überprüfung idR nicht mehr notwendig (es wird ja schon mit geringeren Wegekosten von woanders erreicht).

Beispiel
Start ist 0,0, ziel 3,2
WK = WegeKosten bis zu diesem Feld (G)
WG = geschätzte Kosten bis zum Ziel (H)
0,0 WK 0 WG 3+2=5
0,1 WK 1 WG 3,1 =4
1,0 WK 1 WG 2,2 = 4
A* nimmt den kürzesten in der Liste, und davon den ersten, also 0,1, von hier aus:
0,0 SCHON besucht
0,2 WK 2 WG 3,0 = 3 (WK 1+die gespeicherten 1 vom ersten Schritt)
1,1 WK 2 WG 2,1 = 3
selbes Spiel, 0,2 wird genommen:
0,1 schon besucht
0,3 WK 3 WG 3,1 = 4
1,2 WK 3 WG 2,0 = 2
Hier ist augenscheinlich der 2e Knoten (1,2) der bessere mit den geringsten Kosten.
...und so fort und so fort.

Zu Diensten, Bürger.
Intel T2300, 2.5GB DDR 533, Mobility Radeon X1600 Win XP Home SP3
Intel T8400, 4GB DDR3, Nvidia GF9700M GTS Win 7/64
B3D BMax MaxGUI
Stolzer Gewinner des BAC#48, #52 & #92

	BIG BUG	Di, März 11, 2008 21:42 Antworten mit Zitat
Das mit dem Wegkosten abschätzen musst Du nicht unbedingt machen, sondern es dient zur Beschleunigung des Wegfindeprozesses. Knoten, die in Summe geringer erscheinen, werden hierzu einfach bevorzugt behandelt. Wenn Du weiter im Tutorial kuckst, wird das bestimmt klarer: Durch dieses Abschätzen arbeitet sich hier der Algorithmus bevorzugt in Richtung Ziel vor. Hier würde mit dem 1er ganz links also wirklich erst am Schluß weitergesucht werden, falls es vorne wirklich nicht weitergeht. So kannst Du die in den meisten Fällen die Abfragen deutlich reduzieren und die durchschnittliche Geschwindigkeit verbessern. [EDIT] zu spät
B3D-Exporter für Cinema4D!(V1.4) MD2-Exporter für Cinema4D!(final)

BIG BUG

Di, März 11, 2008 21:42
Antworten mit Zitat

Das mit dem Wegkosten abschätzen musst Du nicht unbedingt machen, sondern es dient zur Beschleunigung des Wegfindeprozesses.
Knoten, die in Summe geringer erscheinen, werden hierzu einfach bevorzugt behandelt.

Wenn Du weiter im Tutorial kuckst, wird das bestimmt klarer:
user posted image

Durch dieses Abschätzen arbeitet sich hier der Algorithmus bevorzugt in Richtung Ziel vor. Hier würde mit dem 1er ganz links also wirklich erst am Schluß weitergesucht werden, falls es vorne wirklich nicht weitergeht. So kannst Du die in den meisten Fällen die Abfragen deutlich reduzieren und die durchschnittliche Geschwindigkeit verbessern.

[EDIT] zu spät Smile

B3D-Exporter für Cinema4D!(V1.4)
MD2-Exporter für Cinema4D!(final)

	TheShadow Moderator	Di, März 11, 2008 23:22 Antworten mit Zitat
yup - genauer geht es mit pythagoras - anstatt B+H... wobei pythagoras langsamer ist
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Di, März 11, 2008 23:22
Antworten mit Zitat

yup - genauer geht es mit pythagoras - anstatt B+H... wobei pythagoras langsamer ist

AMD64 3500+ | GeForce6600GT 128MB | 1GB DDR | WinXPsp2

	Skabus	Di, März 11, 2008 23:43 Antworten mit Zitat
Ah jetzt verstehe ich den Sinn, vielen Dank an BladeRunner und auch an BIG BUG und TheShadow(mehr oder weniger XD). Ich hatte verstanden, das man H immer von Startpunkt abschätzt und da würde ja stehts ein konstanter Wert rauskommen was ja keinen Sinn machne würde, aber wenn man immer vom aktuellen Knotenpunkt ausgeht macht das natürlich Sinn.... Nun, dann kann ich ja endlich mal was dazu proggen^^ Danke nochmals! 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

Di, März 11, 2008 23:43
Antworten mit Zitat

Ah jetzt verstehe ich den Sinn, vielen Dank an BladeRunner und auch an BIG BUG und TheShadow(mehr oder weniger XD).

Ich hatte verstanden, das man H immer von Startpunkt abschätzt und da würde ja stehts ein konstanter Wert rauskommen was ja keinen Sinn machne würde, aber wenn man immer vom aktuellen Knotenpunkt ausgeht macht das natürlich Sinn....

Nun, dann kann ich ja endlich mal was dazu proggen^^

Danke nochmals!

MfG Ska

Übersicht

Sonstiges

Smalltalk

Nach Oben

BlitzBasic Portal

Verständnisfrage zur Pathfinding-Methode A*

Skabus

Betreff: Verständnisfrage zur Pathfinding-Methode A*

BladeRunner

BIG BUG

TheShadow

Skabus