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

[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

[Ritchie]

Hallo,

so, ich habe das ganze nochmals überarbeitet. Jetzt hoffe ich doch, das jetzt auch die A* Funktionen besser durchkommt und keine reine Suchfunktion über alle Felder vorhanden ist.

Edit:
Nochmals viele Dank an Markus für die Hilfe.

Gruss R.