c't

c't-Projekte - Mailinglisten


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

AW: [ct-bot] Erweiterung Pfadplanung

Absender: Frank Menzel
Datum: Di, 31.03.2009 19:37:48
In-reply-to: <A230EC8C-95A0-414A-905F-8692142734D2@xxxxxxxxxxxxxxx>


Hi Timo,
da fehlt dann wieder leider die Debugausgabe um abzulesen, nach wie viel
Versuchen und mit welchem Radius er letztendlich den Weg gefunden hat.
Er versucht zuerst mit Radius 30, um bei nicht gefundenem Pfad diesen zu
verringern, um dann einen möglichen Weg zu finden.
Geplant hat er richtig, nur die Hindernisse eben nicht richtig mit 1
belegt und daher einen Weg durch die Wand gefunden. Möglicherweise
müsste man auch das Setzen eines Hindernissumkreises etwas ausweiten im
Onlinescan, so dass die Hindernisse breiter werden. Andererseits könnte
man auch beim Planen map_way_free einsetzen von Pfadpunkt zu Pfadpunkt,
um so einen zu geringen Abstand zu einer Wand auszuschliessen und einen
anderen möglichen Pfadpunkt zu nehmen. Doch dann würde der Mapzugriff
stark frequentiert sein, wobei dies im Sim andererseits fast egal sein
sollte zumal dies auf dem echten ja wohl doch nicht so funktioniert
oder?
Wie konnte man eigentlich diesen .map-Parcour reinladen?

Gruß, Frank

-----Ursprüngliche Nachricht-----
Von: ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx
[mailto:ct-bot-entwickler-bounces@xxxxxxxxxxxxxxxxx] Im Auftrag von Timo
Sandmann
Gesendet: Dienstag, 31. März 2009 16:03
An: Entwicklung rund um den c't-bot
Betreff: Re: [ct-bot] Erweiterung Pfadplanung

-----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  
>> 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)

iEYEARECAAYFAknSIowACgkQDH/BX4067fJOqwCg4K7TnVJweO0SaVGGHYucstmi
Gs8AoLaqIcauDf2/51F80hvthPB/bIzA
=/WTM
-----END PGP SIGNATURE-----

_______________________________________________
ct-bot-entwickler Mailingliste
ct-bot-entwickler@xxxxxxxxxxxxxxxxx
http://www.heise.de/bin/newsletter/listinfo/ct-bot-entwickler