Einfaches Pathfinding?

Übersicht

Sonstiges

Smalltalk

	#Reaper Newsposter Betreff: Einfaches Pathfinding?	So, Okt 07, 2007 1:07 Antworten mit Zitat
Ich konnte bislang einfach noch nichts finden. Ich suche eine sehr einfache Pathfinding-Methode. Da die aber nicht für Blitz ist, schreibe ich mal in dem Forum hier. Ich konnte bislang nur sehr aufwendige Pathfinding-Methoden finden, wie z.B. den A*-Algorithmus. Nur versteh ich leider nicht, wie ich den auf C umsetzen könnte. Zumal das Sample von BlitzBase ja mit Types arbeitet, und ich aber eigentlich auch nur (möglichst) 1 Array verwenden möchte. Meine eigenen Versuche sind bislang kläglich gescheitert^^ Es muss deshalb C und so einfach sein, da das ganze für mein neuen RP6 gedacht ist Also, falls wer noch irgendwelche passenden Methoden kennt, sagt bitte bescheid Danke! MfG #Reaper
AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!) Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7

#Reaper

Newsposter

Betreff: Einfaches Pathfinding?

So, Okt 07, 2007 1:07
Antworten mit Zitat

Ich konnte bislang einfach noch nichts finden. Ich suche eine sehr einfache Pathfinding-Methode. Da die aber nicht für Blitz ist, schreibe ich mal in dem Forum hier. Wink

Ich konnte bislang nur sehr aufwendige Pathfinding-Methoden finden, wie z.B. den A*-Algorithmus. Nur versteh ich leider nicht, wie ich den auf C umsetzen könnte. Zumal das Sample von BlitzBase ja mit Types arbeitet, und ich aber eigentlich auch nur (möglichst) 1 Array verwenden möchte. Meine eigenen Versuche sind bislang kläglich gescheitert^^
Es muss deshalb C und so einfach sein, da das ganze für mein neuen RP6 gedacht ist Wink

Also, falls wer noch irgendwelche passenden Methoden kennt, sagt bitte bescheid Wink

Danke!

MfG
#Reaper

AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!)
Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7

	ChristianK	So, Okt 07, 2007 1:26 Antworten mit Zitat
Vielleicht hilft dir das weiter: http://wiki.delphigl.com/index...athfinding Ist zwar in Pascal, aber bestimmt leicht zu konvertieren.
AdvanceLcd Intel Core 2 Duo 3.2 GHz, 4 GB RAM, GeForce 8800 GTX \| MacBook Pro 15,4″ Intel Core 2 Duo 2.4 GHz, 2 GB RAM, GeForce 8600M GT

ChristianK

So, Okt 07, 2007 1:26
Antworten mit Zitat

Vielleicht hilft dir das weiter: http://wiki.delphigl.com/index...athfinding
Ist zwar in Pascal, aber bestimmt leicht zu konvertieren.

AdvanceLcd
Intel Core 2 Duo 3.2 GHz, 4 GB RAM, GeForce 8800 GTX | MacBook Pro 15,4″ Intel Core 2 Duo 2.4 GHz, 2 GB RAM, GeForce 8600M GT

	BladeRunner Moderator	So, Okt 07, 2007 11:40 Antworten mit Zitat
Pathfinding eines Roboters ist deutlich von dem in einem Spiel abzugrenzen. Der Roboter soll ja möglichst autonom sein und hat Sensoren um die Welt zu erfahren, wohingegen bei Spielen dem Programm idR die komplette Map bekannt ist. Deswegen kann ein A* bei einem Roboter auch nicht funktionieren, es sei denn er hat vorher das komplette begehbare Areal abgefahren und memoriert. Was Du also brauchst dürfte nicht Pathfinding im Sinne A* sein sondern Algorithmen welche ein sinnvolles Erforschen möglich machen. Hier sei die Rechte-Hand-Regel als Beispiel angeführt (in einem 2-Dimensionalen Labyrinth mit exakt einem Ein- und Ausgang gelangt man garantiert zum Ausgang wenn man am Eingang die Hand an die rechte Wand legt und nicht wieder loslässt und so immer der Wand folgt.). Zudem wirst Du einen rekursiven Mechanismus entwickeln müssen der die von den Sensoren gelieferten Daten auswertet und zu einer Karte zusammensetzt und (das wird der rekursive Teil) Sackgassen erkennt und aus der Karte wirft. Somit wird dein Roboter beim ersten Durchlauf auf einem Parcours noch viele Fehler machen, ab dem zweiten sollte er ihn fehlerfrei beherrschen.
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

So, Okt 07, 2007 11:40
Antworten mit Zitat

Pathfinding eines Roboters ist deutlich von dem in einem Spiel abzugrenzen. Der Roboter soll ja möglichst autonom sein und hat Sensoren um die Welt zu erfahren, wohingegen bei Spielen dem Programm idR die komplette Map bekannt ist. Deswegen kann ein A* bei einem Roboter auch nicht funktionieren, es sei denn er hat vorher das komplette begehbare Areal abgefahren und memoriert.
Was Du also brauchst dürfte nicht Pathfinding im Sinne A* sein sondern Algorithmen welche ein sinnvolles Erforschen möglich machen. Hier sei die Rechte-Hand-Regel als Beispiel angeführt (in einem 2-Dimensionalen Labyrinth mit exakt einem Ein- und Ausgang gelangt man garantiert zum Ausgang wenn man am Eingang die Hand an die rechte Wand legt und nicht wieder loslässt und so immer der Wand folgt.). Zudem wirst Du einen rekursiven Mechanismus entwickeln müssen der die von den Sensoren gelieferten Daten auswertet und zu einer Karte zusammensetzt und (das wird der rekursive Teil) Sackgassen erkennt und aus der Karte wirft. Somit wird dein Roboter beim ersten Durchlauf auf einem Parcours noch viele Fehler machen, ab dem zweiten sollte er ihn fehlerfrei beherrschen.

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

	Xeres Moderator	So, Okt 07, 2007 12:28 Antworten mit Zitat
Hier wird Backtracking mittels eines rekursiven Algorithmus' ziemlich gut erklärt, vll. hilfts ja beim Verständnis: http://www.matheprisma.uni-wup.../index.htm
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)

Xeres

Moderator

So, Okt 07, 2007 12:28
Antworten mit Zitat

Hier wird Backtracking mittels eines rekursiven Algorithmus' ziemlich gut erklärt, vll. hilfts ja beim Verständnis:

http://www.matheprisma.uni-wup.../index.htm

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)

	#Reaper Newsposter	So, Okt 07, 2007 13:27 Antworten mit Zitat
Schonmal danke für die Posts und für die Links. Naja, der A*-Algorithmus wäre schon nicht schlecht. Also ich habe vor, dem Roboter eine Karte schon mitzugeben, welche er dann auch durch seine Sensoren erweitern kann. Insofern weis er dann schon (mehr oder weniger), wie seine Umgebung "aussieht". Der Roboter soll dann auch automatisch einen Weg zu einer Position finden, welche ich ihm sage, und mit der "Rechten-Hand-Regel" ginge das dann wohl eher doch schlecht, da die Umgebung ja auch ziemlich leer sein kann. Aber ich schaue mir die Links nun noch genauer an
AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!) Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7

#Reaper

Newsposter

So, Okt 07, 2007 13:27
Antworten mit Zitat

Schonmal danke für die Posts und für die Links.
Naja, der A*-Algorithmus wäre schon nicht schlecht. Also ich habe vor, dem Roboter eine Karte schon mitzugeben, welche er dann auch durch seine Sensoren erweitern kann. Insofern weis er dann schon (mehr oder weniger), wie seine Umgebung "aussieht". Der Roboter soll dann auch automatisch einen Weg zu einer Position finden, welche ich ihm sage, und mit der "Rechten-Hand-Regel" ginge das dann wohl eher doch schlecht, da die Umgebung ja auch ziemlich leer sein kann.
Aber ich schaue mir die Links nun noch genauer an Smile

AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!)
Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7

	#Reaper Newsposter	So, Okt 07, 2007 18:22 Antworten mit Zitat
Sry wegen Doppelpost Ich bekomm das mit dem Pathfinding einfach nicht hin Den Code ProGamer.Coder's konnte ich noch nicht erfolgreich umsetzten, so das er läuft. :-/ Edit: Danke! Hab es nun soweit hinbekommen (Der Dlephi-Code war eine Qual^^)
AMD Athlon 64 3500+, ATI AX800 Pro/TD, 2048 MB DRR 400 von Infineon, ♥RIP♥ (2005 - Juli 2015 -> sic!) Blitz3D, BlitzMax, MaxGUI, Monkey X; Win7