- heise online
- c't Magazin
- iX Magazin
- Technology Review
- Telepolis

- heise mobil
- heise Security
- heise Netze
- Open Source
- heise Developer

- heise Resale
- heise Foto
- heise Autos
- c't-TV

- Software/Download
- Stellenangebote
- Preisvergleich
- IT-Markt

- heisetreff
- heise Veranstaltungen
- heise Whitepapers
- Abo&Heft
- Archiv

####

####

c't Projekte - c't-Bot und c't-Sim - Mailinglisten

## c't-Bot und c't-Sim

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

### Re: [ct-bot] Erweiterung Pfadplanung

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

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

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

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

- Aktuelles Heft
- Aktuelles Editorial
- Websites aktuell

#### Support

- Hotline & FAQ
- Treiber & BIOS
- Firmenkontakte

#### Download

- Software zu c't
- Software-Verzeichnis
- c't-Projekte
- Testbilder & Vorlagen

#### Magazin

- Heftarchiv
- c't specials
- Leserforum
- c't-Bildmotive
- Schlagseite

#### Info

- Abo & Heft
- Veranstaltungen
- Mediadaten
- Kontakt
- Impressum

Kleinanzeigen und
Veranstaltungen

- Datenschutzhinweis
- Impressum
- Kritik, Anregungen bitte an c't-WWW
- Mediadaten
- Copyright © 2009 Heise Zeitschriften Verlag
- International: The H, The H Security, The H Open Source, heise online Polska, heise Security Polska, heise Open Source Polska, heise Networks Polska