Pathfinding

Übersicht

BlitzBasic

Allgemein

	girgl Betreff: Pathfinding	Do, Jan 29, 2004 16:35 Antworten mit Zitat
Servus,kann mir bitte jemand kurz mit eigenen Worten erklären wie das so mit Pathfinding is. Man braucht dafür irgendwelche Knoten an denen sich die Figur orientiert oder so ,weiss das aber net genau.Auf das Tutorial auf blitzbase.de braucht ihr net verweisen.Mir wärs lieber wenn jemand kurz erklärt wie man das der reihe nach macht.Ohne Code nur mit Worten

girgl

Betreff: Pathfinding

Do, Jan 29, 2004 16:35
Antworten mit Zitat

Servus,kann mir bitte jemand kurz mit eigenen Worten erklären wie das so mit Pathfinding is.
Man braucht dafür irgendwelche Knoten an denen sich die Figur orientiert oder so Rolling Eyes

,weiss das aber net genau.Auf das Tutorial auf blitzbase.de braucht ihr net verweisen.Mir wärs lieber wenn jemand kurz erklärt wie man das der reihe nach macht.Ohne Code nur mit Worten

	sidolin	Do, Jan 29, 2004 16:48 Antworten mit Zitat
-> nimm ein objekt und lasse es auf eine xyz koordinate schauen und lass es losbewegen -> wenn es da angekommen ist schaut es wieder auf ne andere xyz koordinate und wieder losbewegen lassen -> und so weiter und so weiter ...

sidolin

Do, Jan 29, 2004 16:48
Antworten mit Zitat

-> nimm ein objekt und lasse es auf eine xyz koordinate schauen und lass es losbewegen
-> wenn es da angekommen ist schaut es wieder auf ne andere xyz koordinate und wieder losbewegen lassen
-> und so weiter und so weiter ...

	TheShadow Moderator	Do, Jan 29, 2004 21:41 Antworten mit Zitat
das ist mehr oder weniger blödsinn, was sidolin gesagt hat... blitzbase-tutorial ist eigentlich das einfachste was es gibt...
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Do, Jan 29, 2004 21:41
Antworten mit Zitat

das ist mehr oder weniger blödsinn, was sidolin gesagt hat...

blitzbase-tutorial ist eigentlich das einfachste was es gibt...

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

	girgl	Fr, Jan 30, 2004 14:20 Antworten mit Zitat
ja,aber den code will ich mir net unbedingt durchschaun,weil ich ihn auch nich wirklich versteh. Kann vielleicht jemand sagen,wie die einzelnen schritte aussehen,also was ich zuerst berechnen muss usw. ?

girgl

Fr, Jan 30, 2004 14:20
Antworten mit Zitat

ja,aber den code will ich mir net unbedingt durchschaun,weil ich ihn auch nich wirklich versteh.
Kann vielleicht jemand sagen,wie die einzelnen schritte aussehen,also was ich zuerst berechnen muss usw. ?

	Edlothiol	Fr, Jan 30, 2004 14:37 Antworten mit Zitat
Also, A* funktioniert soviel ich weiß in etwa so: Du fängst an einem Punkt (Startpunkt) an. Für jedes Nachbarfeld (ob diagonal auch kannst du dir aussuchen), das begehbar ist, berechnest du: 1. Die Kosten vom Startfeld an, d.h. diese Kosten vom Feld dessen Nachbarn du grade berechnest + Kosten dieses Feldes (normal 1). Also z.B. wenn du grad beim Startfeld bist dessen Kosten vom Startfeld an sind natürlich 0, da es das Startfeld ist. Dazu addierst du dann z.B. 1 und speicherst es für das Feld. 2. Die Kosten von diesem Feld bis zum Ziel. Da du die natürlich noch nicht wissen kannst, musst du eine Schätz - Funktion schreiben. Das kann z.B. einfach die Anzahl der Felder zwischen diesem Feld und dem Zielfeld sein, das erzielt schon ganz gute Ergebnisse. 3. Für alle Felder addierst du diese beiden Werte, und schaust dann nach, welches (noch nicht getestete) Feld den kleinsten Wert besitzt. Nun machst du die gleiche Prozedur (Nachbarfelder checken) für dieses Feld, usw. Ausserdem musst du für jedes Feld speichern, von wo du dieses Feld gecheckt hast. Wenn du ein Feld checkst, das schon von einer anderen Seite gecheckt wurde, schaust du nach, ob die Kosten vom Startfeld bis hierhin damit kleiner sind als da schon steht, wenn ja, überschreibst du den Wert woher du auf das Feld kamst. Sobald du das Zielfeld erreicht hast, brichst du ab. Damit wirst du nicht unbedingt den kürzesten Weg gefunden haben, aber einen Weg. Das kommt ganz auf die Schätzfunktion an. Wenn ich einen Fehler gemacht habe, berichtigt mich bitte. Ich weiß dass ich das nicht sonderlich gut erkärt habe aber einen Versuch ists wert. PS.: Das funktioniert natürlich nur mit Feldern so richtig, bei 3d musst du dir die Umgebung dann irgendwie einteilen.

Edlothiol

Fr, Jan 30, 2004 14:37
Antworten mit Zitat

Also, A* funktioniert soviel ich weiß in etwa so:
Du fängst an einem Punkt (Startpunkt) an.
Für jedes Nachbarfeld (ob diagonal auch kannst du dir aussuchen), das begehbar ist, berechnest du:
1. Die Kosten vom Startfeld an, d.h. diese Kosten vom Feld dessen Nachbarn du grade berechnest + Kosten dieses Feldes (normal 1). Also z.B. wenn du grad beim Startfeld bist dessen Kosten vom Startfeld an sind natürlich 0, da es das Startfeld ist. Dazu addierst du dann z.B. 1 und speicherst es für das Feld.
2. Die Kosten von diesem Feld bis zum Ziel. Da du die natürlich noch nicht wissen kannst, musst du eine Schätz - Funktion schreiben. Das kann z.B. einfach die Anzahl der Felder zwischen diesem Feld und dem Zielfeld sein, das erzielt schon ganz gute Ergebnisse.
3. Für alle Felder addierst du diese beiden Werte, und schaust dann nach, welches (noch nicht getestete) Feld den kleinsten Wert besitzt. Nun machst du die gleiche Prozedur (Nachbarfelder checken) für dieses Feld, usw.
Ausserdem musst du für jedes Feld speichern, von wo du dieses Feld gecheckt hast. Wenn du ein Feld checkst, das schon von einer anderen Seite gecheckt wurde, schaust du nach, ob die Kosten vom Startfeld bis hierhin damit kleiner sind als da schon steht, wenn ja, überschreibst du den Wert woher du auf das Feld kamst.
Sobald du das Zielfeld erreicht hast, brichst du ab. Damit wirst du nicht unbedingt den kürzesten Weg gefunden haben, aber einen Weg. Das kommt ganz auf die Schätzfunktion an.
Wenn ich einen Fehler gemacht habe, berichtigt mich bitte. Ich weiß dass ich das nicht sonderlich gut erkärt habe Rolling Eyes

aber einen Versuch ists wert.

PS.: Das funktioniert natürlich nur mit Feldern so richtig, bei 3d musst du dir die Umgebung dann irgendwie einteilen.

	girgl	Fr, Jan 30, 2004 19:26 Antworten mit Zitat
schon mal danke für die antwort aber was meinst du mit "Kosten" ?

girgl

Fr, Jan 30, 2004 19:26
Antworten mit Zitat

schon mal danke für die antwort aber was meinst du mit "Kosten" ?

	Edlothiol	Fr, Jan 30, 2004 19:31 Antworten mit Zitat
Ähm, ich habs ein bisschen ungenau beschrieben, es gibt 1. Die Bewegungskosten für ein Feld. Die legst du schon im voraus fest, meistens werden sie 1 oder so sein. Damit kannst du kontrollieren, welche Felder eher begangen werden. 2. Die Kosten vom Startfeld bis zum jeweiligen Feld. Die sind einfach (Kosten vom Startfeld bis zum vorherigen Feld) + Bewegungskosten des Feldes. und 3. Die Kosten vom jeweiligen Feld bis zum Zielfeld. Da du sie natürlich nicht kennst, musst du sie schätzen.

Edlothiol

Fr, Jan 30, 2004 19:31
Antworten mit Zitat

Ähm, ich habs ein bisschen ungenau beschrieben, es gibt
1. Die Bewegungskosten für ein Feld. Die legst du schon im voraus fest, meistens werden sie 1 oder so sein. Damit kannst du kontrollieren, welche Felder eher begangen werden.
2. Die Kosten vom Startfeld bis zum jeweiligen Feld. Die sind einfach (Kosten vom Startfeld bis zum vorherigen Feld) + Bewegungskosten des Feldes.
und 3. Die Kosten vom jeweiligen Feld bis zum Zielfeld. Da du sie natürlich nicht kennst, musst du sie schätzen.

	TheShadow Moderator	Fr, Jan 30, 2004 19:37 Antworten mit Zitat
Zitat: ja,aber den code will ich mir net unbedingt durchschaun,weil ich ihn auch nich wirklich versteh. Kann vielleicht jemand sagen,wie die einzelnen schritte aussehen,also was ich zuerst berechnen muss usw. ? Du hast dir das Tutorial nicht durchgelesen - es hat gar KEINEN code - ist somit universell - ein BB-Beispiel am Ende ist nur Bonus - der Pathfinding-Kern hat nur 100 Zeilen Übrigens ist Tutorial eher sowas wie Schritt-für-schritt-anleitung - sogar mit Bildern...
AMD64 3500+ \| GeForce6600GT 128MB \| 1GB DDR \| WinXPsp2

TheShadow

Moderator

Fr, Jan 30, 2004 19:37
Antworten mit Zitat

Zitat:

Du hast dir das Tutorial nicht durchgelesen - es hat gar KEINEN code - ist somit universell - ein BB-Beispiel am Ende ist nur Bonus - der Pathfinding-Kern hat nur 100 Zeilen

Übrigens ist Tutorial eher sowas wie Schritt-für-schritt-anleitung - sogar mit Bildern...

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

	Omenaton_2	Fr, Jan 30, 2004 20:58 Antworten mit Zitat
hi! Ich stand vor ca. 1 Jahr vor diesem Problem. Ich habe mir damals auch einige Tutorials angeschaut. Es gibt darüber einige Tutorials, aber kein einziges davon ist wirklich ausreichend hilfreich für jemanden, der damit erst anfängt. Man muß schon 2-3 Tutorials sehr genau durchlesen und aus allen die Stellen verinnerlichen, die darin besonders gut erklärt werden. Ich habe nachdem ich es mit ziemlich viel Mühe gut verstanden habe wie das A* Pathfinding funktioniert selber einen guten A* Pathfinding Code geschrieben. Zeile für Zeile alleine. Das ist der einzig richtige Weg den du auch gehen solltest. Es ist nachhinein gar nicht so kompliziert, aber einfach ist es auch nicht. Die Grundlagen zu verstehen geht schnell, aber um das alles vernünftig zu programmieren kostet schon einige Tage oder gar eine Woche. Das schaffst du nur, wenn du bereit bist dafür die nötige Zeit und Mühe zu nehmen. Da ich das schon vor längerer Zeit gemacht habe erinnere ich mich jetzt nicht mehr gut daran. Ich müßte mich da wieder hinenfinden und die Zeit (und Lust) dazu habe ich nicht. Hier sind paar Links: http://www.ccg.leeds.ac.uk/james/aStar http://www.policyalmanac.org/g...torial.htm http://www-cs-students.stanfor...html#paths http://www.geocities.com/jheyesjones/astar.html http://ai-depot.com/GameAI/Design.html http://www.iicm.edu/greif/images/node1.html

Omenaton_2

Fr, Jan 30, 2004 20:58
Antworten mit Zitat

hi!

Ich stand vor ca. 1 Jahr vor diesem Problem. Ich habe mir damals auch einige Tutorials angeschaut. Es gibt darüber einige Tutorials, aber kein einziges davon ist wirklich ausreichend hilfreich für jemanden, der damit erst anfängt. Man muß schon 2-3 Tutorials sehr genau durchlesen und aus allen die Stellen verinnerlichen, die darin besonders gut erklärt werden.

Ich habe nachdem ich es mit ziemlich viel Mühe gut verstanden habe wie das A* Pathfinding funktioniert selber einen guten A* Pathfinding Code geschrieben. Zeile für Zeile alleine. Das ist der einzig richtige Weg den du auch gehen solltest. Es ist nachhinein gar nicht so kompliziert, aber einfach ist es auch nicht. Die Grundlagen zu verstehen geht schnell, aber um das alles vernünftig zu programmieren kostet schon einige Tage oder gar eine Woche.
Das schaffst du nur, wenn du bereit bist dafür die nötige Zeit und Mühe zu nehmen.

Da ich das schon vor längerer Zeit gemacht habe erinnere ich mich jetzt nicht mehr gut daran. Ich müßte mich da wieder hinenfinden und die Zeit (und Lust) dazu habe ich nicht.

Hier sind paar Links:

http://www.ccg.leeds.ac.uk/james/aStar

http://www.policyalmanac.org/g...torial.htm

http://www-cs-students.stanfor...html#paths

http://www.geocities.com/jheyesjones/astar.html

http://ai-depot.com/GameAI/Design.html

http://www.iicm.edu/greif/images/node1.html

	girgl	Fr, Jan 30, 2004 21:29 Antworten mit Zitat
@TheShadow Das Tutorial mit den Bildern hab ich bis dato noch garnet gesehen gehabt,nur das was es dazu zum download gab @omenaton heissen dank,werd mir das mal genauer anschaun

girgl

Fr, Jan 30, 2004 21:29
Antworten mit Zitat

@TheShadow
Das Tutorial mit den Bildern hab ich bis dato noch garnet gesehen gehabt,nur das was es dazu zum download gab

@omenaton
heissen dank,werd mir das mal genauer anschaun

	adba	So, Feb 01, 2004 18:31 Antworten mit Zitat
Hi Ich hab eine Pathfinding rutiene in BB geschrieben ist allerdings schon gut 2 jahre her. dementsprechen chaotisch habe ich damals auch programmiert du kannst dir das programm jedoch mal runterladen und anschauen aber es zu verstehen ist wohl nicht möglich.. (ich selbst verstehe nicht mehr alles ) Link: http://mypage.bluewin.ch/Baade...rldv01.zip

adba

So, Feb 01, 2004 18:31
Antworten mit Zitat

Hi

Ich hab eine Pathfinding rutiene in BB geschrieben ist allerdings schon gut 2 jahre her. dementsprechen chaotisch habe ich damals auch programmiert Smile

du kannst dir das programm jedoch mal runterladen und anschauen aber es zu verstehen ist wohl nicht möglich.. (ich selbst verstehe nicht mehr alles Smile

)

Link: http://mypage.bluewin.ch/Baade...rldv01.zip

Übersicht

BlitzBasic

Allgemein

Nach Oben

BlitzBasic Portal

Pathfinding

Betreff: Pathfinding