## 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: So, 29.03.2009 10:50:21
In-reply-to: <3382C149-1047-488D-9761-E606002C609E@xxxxxxxxxxxxxxx>

    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

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

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

    Hi Frank,

    Am 28.03.2009 um 14:12 schrieb Frank Menzel:
    > Hallo Timo,
    > zu 1.)
    > Die Planung findet ja nicht den kürzesten Weg sondern eben nur einen
    > Weg.

    das war mir bisher nicht bewusst, steht das irgendwo?
    Der unter
    http://www.heise.de/ct/projekte/machmit/ctbot/wiki/NeueVerhalten#Pfadpla
    nung
    beschriebene Algorithmus findet immer einen (es kann allerdings
    mehrere gleich lange geben) kürzesten Weg zum Ziel, sofern es denn
    einen gibt. Ich dachte diese Methode wäre auch im Verhalten
    implementiert?

    > Die Logausgabe ist da eigentlich nicht viel aussagekräftiger, um
    > diesem auf die Spur zu kommen. Eine Welle geht ja von einer Zelle aus,
    > wobei alle Nachbarzellen den gleichen erhöhten Wellenwert bekommen. So
    > geht?s weiter bis zum Ziel. Wenn dann die Pfadrückverfolgung losgeht,
    > dann wird immer in gleicher Richtung rund um die Zelle der jeweils
    > kleinere Wellenwert genommen und dieser weiter rückverfolgt, wobei
    > immer
    > der zuerst gefundene genommen wird-also auch wenn alle anderen
    > identisch
    > sind. So muss diese Zelle nicht unbedingt die in Richtung Ziel naheste
    > sein.

    Das ist klar, aber das verlängert den Weg zum Ziel nicht, wenn man den
    o.g. Algorithmus benutzt. Von jeder Zelle mit gleichem Wert ist das
    Ziel gleich weit entfernt. Die Werte in den Zellen (mit Ausnahme denen
    für  Hindernisse) geben jeweils die Entfernung (eines befahrbaren
    Weges) zum Ziel an, das ist ja die Idee hinter dem ganzen Verfahren.

    > Prinzipiell muesste man auch die Distanzfunktion einbringen
    > koennen, um eben genau diese Zelle zu nehmen. Jedenfalls denke ich,
    > dass
    > eben dadurch die Richtung, die nicht unbedingt die zum Ziel kürzeste
    > ist, verfolgt wird, bis ein kleinerer Wellenwert wieder die Richtung
    > zum
    > Ziel weist.

    s.o.

    > Die Verteilung der Wellenwerte auf die niedrigauflösende Planungsmap
    > (Taste 6) sollte da aussagekräftiger sein.

    Ah ok, das werde ich noch mal ausprobieren.

    > Zu 2.)
    > Die rote Linie geht ja oben durch die Mauer. Was ist oberhalb?

    Na das sieht man doch in der Sim-Welt, oder was meinst du?

    > Soll der
    > Weg rechts der 2. Teil des Weges sein? Wo ist das Planungsziel?
    > Mit welcher Taste hast Du geplant, also nur auf befahrenem Gebiet
    > (Taste
    > 4) oder 5? Bei 4 sollte eigentlich alles nicht befahrene auf Hindernis
    > stehen und die Planung da nicht langgehen, bei Taste 5 würde man die
    > Welelnwerte direkt sehen...

    Ich habe einfach bot_drive_area() aufgerufen. Ich denke drive_area()
    setzt diesen Zielpunkt, weil der Bot dort noch nicht war (ist aber
    mitten in der Wand, was das Verhalten ja nicht wissen kann). Nur
    müsste die Pfadplanung doch feststellen, dass es keinen Weg dorthin
    gibt, oder? Der vom Planungsverhalten ermittelte Weg (sofern die rote
    Linie stimmt) kann auf jeden Fall nicht sein, weil er durch ein
    Hindernis führt. Darum crasht der Bot dort ja auch.

    Gruß,
    Timo

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

    iEYEARECAAYFAknOOpgACgkQDH/BX4067fK5xACg4tdSjB/RF7rSjEFt+j4Vc/O/
    FOIAnjw8X9++dF4DS5IoXUbml3RDvAil
    =raYS
    -----END PGP SIGNATURE-----

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

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

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

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