Probleme mit A Star, wenn Objekt größer ist als eine Nodepunkt

[markusj]

Interessant wäre fürs Debugging eine Darstellung der untersuchten Felder (ähnlich der Animation im A*-Artikel in der deutschen Wikipedia)

mfG
Markus

[Ritchie]

Hi,
das werde ich dann wohl heute abend mal eo erweitern.

Interessant ist aber, das diese besagte Ecke eigentlich der kürzstes Weg ist,
wenn ich den Weg nur in einer Breite von einem Kästchen sehen.

Also ohne mein zusätzliches Quadrat um den Robotermittelpunkt,
was ich als nicht begehbar ansehe um den Roboter
nicht gegen Wände fahren zu lassen.

Gruss R.

[markusj]

Ohne es auszurechnen: Das kann nicht sein (oder anders formuliert: Ich kann es nicht glauben ...).
Nach meinem Verständnis geht der kürzeste Weg diagonal zum ersten Tor. Ich hätte übrigens auch eine diagonale Verbindung vom Wegpunkt nach dem ersten Tor zum Wegpunkt vor dem zweiten Tor erwartet.

mfG
Markus

[Ritchie]

Bedenke, das ich ein Quadrat von der Kantenlänge 16 um den Mittelpunkt gezogen habe. Hierdurch will er
immer 8 Kästchen vom Rand (links & rechts) entfernt entlang fahren.

Ich erweitere die Grafik mit weiteren Information und werde einfach mal das gespannte Quadrat weglassen und
das Ergebnis hiervon auch mal zeigen.

Gruss R.

[markusj]

Bedenke, das ich ein Quadrat von der Kantenlänge 16 um den Mittelpunkt gezogen habe. Hierdurch will er
immer 8 Kästchen vom Rand (links & rechts) entfernt entlang fahren.

Schon klar, aber der erste Wegpunkt (der "Haken") ist komplett überflüssig. Nach der Karte könnte der Roboter auch direkt zum zweiten Punkt fahren. Genauso könnte der vierte Wegpunkt (der vor der Schräge zum zweiten Durchgang) übersprungen werden, um direkt vom Ende des ersten Durchganges zum Eingang des zweiten Durchganges zu fahren.

mfG
Markus

[Ritchie]

Du hast recht.

Ich habe jetzt nur die Standard "frei" routine aktiviert und hier sieht das ganze genauso "seltsam" aus.
Ich habe hier die Felder gelb markiert, welche die Routine auf Frei geprüft hat.

Meine Kostenroutine gibt immer 1 zurück, für eine Bewegung auf ein anderes Feld.
Edit 2: Ich vermute hier den Fehler.

Edit:
Und das zweite Bild zeigt, wie es eigentlich aussehen sollte.
Jetzt habe ich was zu tun

Gruss R.

[Ritchie]

Hallo Zusammen,

nachdem ich dynamische Kosten eingefügt habe, zeigt sich das Suchergebenis schon deutlich besser.

Aber 100% optimal ist der immer noch nicht ...

Gruss R.

[markusj]

In der Tat. Wie bereits erwähnt, könntest du dir die Arbeit einfacher machen, wenn du den Radius des Roboters als 1 festlegst und stattdessen die Hindernisse vergrößerst. Da dein Roboter ja annähernd quadratisch zu sein scheint, dürfte der entstehende Verschnitt sich in einem akzeptablen Rahmen bewegen.

mfG
Markus

Edit: Nachtrag zu deinem zweiten Post: Sieht besser aus, ja. Aber der Weg vom ersten zum zweiten Durchgang geht besser ... Und auch der Anfang ist komisch. Was meinst du eigentlich mit dynamischen Kosten?

[Ritchie]

Hallo,

ich gebe Dir recht, das die ganze Sache noch nicht wirklich sauber ist.
Die Wegberechnung ist jetzt besser, aber gefallen tut sie mir noch nicht.
Deine Einwände sind korrekt. Hier scheint noch was faul zu sein.

Auch will der Sucher -Algo. plötzlich wieder in die Ecke fahren, wenn ich das Ziel oberhalb der linke Ecke setze.

Ich habe derzeit nur eine einfach Kostenrechnung, da ich mich gestern nicht mehr darum kümmern konnte.
Schliesslich hat man doch hierbei eine Menge zu lesen, bevor ich an den Code gehen kann. Ich bin nämlich erst
in den Anfängen von A*.

        inline int    CostValue(int xo, int yo, int x, int y)
            {
                if (xo - x != 0 && yo - y != 0)
                    return        2;
                else    
                    return        1;
            }

Wobei Xo,Yo die alte Position und X,Y die neue Position ist. Hier wird nur geprüft, ob er diagonal fahren will.

Gruss R.

[markusj]

Die Kostenfunktion erklärt zumindest einige Irrwege (und macht, davon abgesehen, den A* obsolet weil ohne die Richtungsinformation eine vollständige Suche durchgeführt wird). Da die Kosten für eine diagonale Bewegung gleich den Kosten einer Bewegung entlang beider Koordinatenachsen gesetzt werden, kann der Algorithmus die Richtung frei wählen! Davon abgesehen erfüllt diese Kostenfunktion die A*-Bedingungen nicht mehr, da sie die Distanz überschätzt: sqrt(1² + 1²) < 1 + 1

mfG
Markus