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

- Antworten:
  - Re: [ct-bot] Erweiterung Pfadplanung
    - From: Timo Sandmann

- Referenzen:
  - AW: [ct-bot] Erweiterung Pfadplanung
    - From: Frank Menzel

- Voriger (Datum): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Nächster (Datum): Re: [ct-bot] Erweiterung Pfadplanung, Timo Sandmann
- Voriger (Thread): AW: [ct-bot] Erweiterung Pfadplanung, Frank Menzel
- Nächster (Thread): Re: [ct-bot] Erweiterung Pfadplanung, Timo Sandmann
- Indizes:
  - Datum
  - Thread