spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Also zu seinem ersten; ich Dächer Wer sollte immer möglichst schnell sein, aber halt relativ zu seinem Verwendungszweck.
Das heißt, wenn du ihn in einem Spiel in jeden Frame aufrufen willst, sollte er nicht 2 mim dauern, aber wenn er irgendwas planen soll zb die Route von einer Stadt zur anderen ist es nicht schlimm, wenn er auch mal 20 Sek dauert.
Kommt halt immer drauf an...
Und zu deinem zweiten, wäre es vll mal gut, wenn du aus Paint ein Bild malst und das dann hochlädst. Dann kann man dir besser Folgen

Problem bitte illustieren. Ich bin ein ziemlich fantasieloser Mensch und kann es mir so nicht vorstellen. Frage 1 verstehe ich nicht ganz. Vorallem hängt das sehr stark von der Implementierung ab. Frage 2 kann ich in sofern beantworten, dass a-star definitiv den kürzesten Weg findet, wenn es einen gibt. Wenn es anders zu sein scheint, oder ist, dann liegt das nicht am a-star sondern an dessen Implementierung durch dich, womit wir wieder beim Anfang wären; ich bräuchte ehrlich gesagt ein Bildchen. Sind die Kantenlängen alle auf 1 normiert (sprich keine unterschiedlichen Wegkosten)?

Aaaaber wenn ich deine Beschreibung richtig verstehe, würde ich mal gegenfragen, warum du denn meinst, dass dein Weg günstiger sein sollte. Dein Problem lässt sich sogar auf 2x2 Knoten reduzieren. Wenn alle Kantenkosten gleich sind, dann ist es egal ob man erst nach rechts und dann nach unten oder erst nach unten und dann nach rechts geht.

Und warum sollte es das sein? Siehe mein beispiel. Du hast ja nur 4 Richtungen, also keine Diagonalen. Sprich warum sollte er diagonal gehen? Vorallem gibt ja die Heuristik an dass "nach rechts" viel günstiger als "nach unten" ist, da du wahrscheinlich die euklidische Norm wähltest und sich das Ziel ja Rechts vom Start befindet und nciht unter oder oberhalb.

Ahh dann habe ich mich verlesen. Dachte du schriebst dass du 4 statt 8 Richtungen hast und nicht umgekehrt. Tja, dann ist wohl deine Kostenberechnung fürn A*. Oder du sortierst den Kontainer nicht korrekt (boost priorityqueue soll ganz gut sein für diesen Zweck).

Ahja...und wie ist Block bzw. F definiert? Wie berechnest du F? geschätzte + bisherige Kosten?

Ich denke, du verwendest die Manhattenlänge.

Du musst in die Länge schon die Diagonalen miteinbeziehen
Wenn X und Y Koordianten des Vektors zum Ziel sind:
Max = max(abs(X), abs(Y))
Min = min(abs(X), abs(Y))
Distanz = Min * 141 + (Max - Min) * 100