Absender: Timo Sandmann
Datum: Di, 31.03.2009 16:02:53
In-reply-to:
<1D7762B9-A3FC-4669-ADFF-A2C026DC8008@xxxxxxxxxxxxxxx>
References:
<000001c9b04b$64a0b7e0$0200a8c0@mexpnew> <1D7762B9-A3FC-4669-ADFF-A2C026DC8008@xxxxxxxxxxxxxxx>
-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 Hallo, hier liegt aber definitiv ein Fehler in der Pfadplanung vor, oder? http://www.heise.de/ct/projekte/machmit/ctbot/ticket/185 Grüße, Timo Am 29.03.2009 um 17:04 schrieb Timo Sandmann:
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 muessteein 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 untersuchenmit 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 nichtklar, wieso die schräge Linie. Ist aber wohl der Startpunkt der nächsten anzufahrenden Bahn, die dann senkrecht nach oben verläuft. Die Planungzu diesem Punkt erfolgte ja von ganz unten, da war wohl die Ecke desHindernisses als solches noch nicht in der Map eingetragen und der Wegzu 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 bekanntesHindernis zum Hindernis wird! Und so geht’s eben durch die Wand. Um dieszu verhindern, könnte man ja auch im Stackverhalten map_way_free zumnächsten Punkt einbauen und falls nicht frei abbrechen. Dann müsste dasAufrufverhalten 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 nacheinem kleinen Hängenbleiben irgendwo. Erst mal so weit. Gruß, Frank
-----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.9 (Darwin) iEYEARECAAYFAknSIowACgkQDH/BX4067fJOqwCg4K7TnVJweO0SaVGGHYucstmi Gs8AoLaqIcauDf2/51F80hvthPB/bIzA =/WTM -----END PGP SIGNATURE-----