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

[Ritchie]

Hi,

dann habe ich ja was zu suchen. Deine Aussage, das A* immer den optimalen Weg bei korrekter Parametierung findet, kann ich nur unterstreichen.

Von hier habe ich meinen Ursprung:
http://www.generation5.org/content/2000/cpathfinder.asp

Und mein PC Programm zu testen und lernen des A* stimmt mit diesem Code sehr gut noch überein. Aber auch hier ist dieses seltsame Verhalten.

@damfino: Meine Karte hat 90000 Felder.

Gruss R.

[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.