c't

c't-Projekte - Mailinglisten


[Voriger (Datum)] [Nächster (Datum)] [Voriger (Thread)] [Nächster (Thread)]
[Nach Datum][Nach Thread]

Re: [ct-bot] Erweiterung Pfadplanung

Absender: Timo Sandmann
Datum: So, 29.03.2009 17:04:11
In-reply-to: <000001c9b04b$64a0b7e0$0200a8c0@mexpnew>
References: <000001c9b04b$64a0b7e0$0200a8c0@mexpnew>


-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Hi Frank,

also das Problem liegt an den Diagonalen: In den Zellen steht jeweils die Entfernung zum Ziel in Kantenlängen der Zellen gezählt. Dein Patch erstellt die Zellen jetzt aber so, dass er auch Diagonalen zulässt und diese genauso verarbeitet, wie die vier "Kantennachbarn". Die Entfernung vom Mittelpunkt einer Zelle zum Mittelpunkt einer anderen, die diagonal erreicht wird, beträgt aber nicht eine Kantenlänge, sondern das 1,4 Fache! Wenn die Karte konsistent bleiben soll, müssten die Werte der Zellen, die diagonal aktualisiert werden, also auch um 1,4 anstatt um 1 erhöht werden. Das Planungsverhalten hat alles richtig gemacht, es ist jetzt nur davon ausgegangen, dass der Weg diagonal zur nächsten Zelle genauso lang ist wie der Weg parallel zu einer der Kanten. Darum werden Diagonalen so stark bevorzugt und es kommt zu diesen Umwegen.

Da es recht ungünstig ist, mit einfachen und 1,4 fachen Kantenlängen zu arbeiten, bin ich auf folgenden Trick gekommen: In die Zellen wird wie früher die Entfernung zum Ziel eingetragen, die sich ergibt, wenn man die Diagonalen ausschließt, für die Erstellung hat jede Zelle also nur vier Nachbarn. Dadurch passt die Karte wieder zum Algorithmus, der jeweils die Zielentfernung in Kantenlängen erwartet. Wenn wir jetzt aber den kürzesten Pfad suchen, lassen wir auch den Diagonalweg zu, falls eine der diagonal angrenzenden Zellen den kleinsten Entfernungswert hat. Nach der oben beschriebenen Kartenerstellung bedeutet das ja, dass die Zielentfernung von dieser Zelle aus am Kleinsten ist, wenn man nur orthogonal fährt. Die Idee ist also, eigentlich nur rechtwinklige Wege zuzulassen, sobald sich durch eine Diagonale aber eine Abkürzung ergibt, wird diese auch benutzt. Dadurch ist zwar nicht garantiert, dass (unter Berücksichtigung der Diagonalen) der kürzeste Weg gefunden wird, der gefundene Weg ist aber kürzer als jeder anderen ohne Diagonalen (mit einer Ausnahme: Wenn eine an die Kante grenzende und eine diagonal angrenzende Zelle denselben Wert haben, dürfte nicht die Diagonale gewählt werden, das ist im Moment aber noch nicht implementiert!). Im Test hat das Ganze auch sehr gut funktioniert, darum habe ich die Änderungen schon mal ins SVN gestellt. Ich denke, das könnte so ein ganz guter Kompromiss zwischen Aufwand (1,4 fache Kantenlänge wirklich immer genau berücksichtigen) und häufigem Zick-Zack-Kurs (keine Diagonalen möglich) sein. Muss allerdings noch mal ausführlicher getestet werden, vor allem in unterschiedlichen Umgebungen.

Außerdem habe ich die Ausgabe von show_labmap() so gedreht, dass sie mit der Map-Anzeige im Sim übereinstimmt (x-Richtung nach oben und y- Richtung nach links).

Grüße,
Timo


Am 29.03.2009 um 10:50 schrieb Frank Menzel:
Hallo Timo,
eigentlich ist die Methode so wie im Link beschrieben implementiert. OK, wir sind uns einig, dass es mehrere Wege geben kann und gut, es muesste
ein kürzester sein.
Dass er aber erst so weit nach unten runter geht, ist mir so auch nicht
verständlich. Werde die Sache mal bei Gelegenheit und Zeit untersuchen
mit diesem Parcour.

Die rote Linie geht ja oben durch die Mauer. Was ist oberhalb?

Hiermit meine ich eigentlich: Er will ja wohl die schräge Linie
anfahren, die schräg oberhalb der Mauer endet. Ich dachte, es sollte
oberhalb ein Weg zur rechten roten Linie geben, sind ja aber wohl
verschiedene Planungen und Wege gewesen. Ja jedenfalls war mir nicht
klar, wieso die schräge Linie. Ist aber wohl der Startpunkt der nächsten
anzufahrenden Bahn, die dann senkrecht nach oben verläuft. Die Planung
zu diesem Punkt erfolgte ja von ganz unten, da war wohl die Ecke des
Hindernisses als solches noch nicht in der Map eingetragen und der Weg
zu dem Punkt so frei. Beim Fahren dorthin wird weiterhin die Map
aktualisiert und ist jetzt als Hindernis zu sehen, wo die Linie
durchläuft. Wenn aber nach der Planung die Pfadpunkte erst dem
Stackverhalten übergeben wird, ist da keine weitere Sicherheit
eingebaut, wenn auf der Fahrt dorthin ein vorher nicht bekanntes
Hindernis zum Hindernis wird! Und so geht’s eben durch die Wand. Um dies
zu verhindern, könnte man ja auch im Stackverhalten map_way_free zum
nächsten Punkt einbauen und falls nicht frei abbrechen. Dann müsste das
Aufrufverhalten entsprechend reagieren und evtl. neuplanen.
Ich werde da mal weiter, gerade mit dem o.a. Parcour testen. Fehler sind natürlich nicht ausgeschlossen. Aber Schwachstellen sind hier gerade in langen abzufahrenden Linien zu finden sowie im Verrutschen der Map nach
einem kleinen Hängenbleiben irgendwo.

Erst mal so weit.
Gruß, Frank

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.9 (Darwin)

iEYEARECAAYFAknPjeoACgkQDH/BX4067fKcCQCglhdINo/ph8pVK/+aBnH8y3wM
7aIAoLAdQG1XPrGEYORAJr2/4+Pkf78K
=1qwT
-----END PGP SIGNATURE-----