Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
Fragen zu Blatt 4
Hier mal ein paar random Fragen die auftauchten und Antworten dazu:
Aufgabe 1
Nein. Bei Heuristiken geht es ja immer nur um relative Werte, nie um absolute. Wenn ich zwei Heuristiken so skalieren kann dass sie gleich werden sind sie für alle praktischen Zwecke identisch.
Beispiele sind keine Beweise. Der Beweis muss so detailliert sein, dass jedem (ohne absichtlich pedantisch zu sein!) klar ist, dass er tatsächlich die Behauptung impliziert. Mir ist bewusst dass das schwammig ist, aber ich bin mir nicht sicher wie ich derartige Fragen genau beantworten sollte. Fragt euch einfach selbst, ob eure Argumentation wirklich stichfest ist und die potentiellen fehlenden Zwischenschritte „klar“ sind oder nur von Definitionen abhängen, und nicht unter Umständen eure Argumentation kaputt machen.
Aufgabe 2
Das ist genau die Aufgabenstellung. Ziel der Aufgabe ist eben genau, dass ihr die gegebene Problemstellung (also eine bestimmte Game mechanik) als Tree-search formuliert, z.B. um sie im Spiel zu implementieren; daher ist sie bewusst so offen gestellt.
Im Prinzip ist das auch die tatsächliche Antwort auf so ziemlich jede Frage zu dieser Aufgabe, außer sie bezieht sich auf das Spiel an sich (die bereits im Forum beantwortete Frage ob die Figur sich diagonal bewegen darf ist zum Beispiel völlig legitim).
…es äußert sich dadurch dass der Charakter sich langsamer bewegt? Euer spiel frisst zu viele Systemressourcen und muss optimiert werden vong Rechenaufwand her.
Offenbar ist dann zweiteres keine Implementation die ihr eurem Chef bei EA vorschlagen wollt (außer ihr wollt nen fix als DLC dazu vorschlagen).
Aber da bleibt bei mir immer noch die Frage, warum bei der Bewegung des Charakters zu viele Ressourcen in Benutzung sind, wenn der Weg (also das Ergebnis von A*) doch im voraus (also vor der kompletten Bewegung) berechnet wird?
Weil für mich scheint diese Vorausberechnung gerade die einzig sinnvolle Art, die Problemstellung als Tree-Search zu formulieren. Aber da kann es während dem Laufen des Charakters kein Ruckeln/Stottern/etc. geben. Und für ein Problem das nicht auftauchen kann, kann ich mir erst recht keine Lösungen ausdenken, aber gerad das fordert doch der zweite Unterpunkt von Problem 4.2 .
Und wenn du eben nicht den kompletten Weg im voraus berechnest und dann abläufst? Könnte auch Sinn machen, Stichwort Sichtradius. Gehe jetzt mal nicht weiter ins Detail… 
1 „Gefällt mir“
Ok… dann ist klar, wieso das ganze viele Ressourcen frisst, Stichwort Sackgassen…
Okay, jetzte ist dafür mir überhaupt nicht klar, warum Sackgassen systemressourcen fressen sollten…? aber bevor ich dich jetzt weiter verwirre ignorier mich lieber 
Hm also mein Gedanke war der: A* merkt sich ja eigentlich nur, wo er schon war und betritt Zustände nicht zweimal.
Wegen Sackgassen muss man aber das nun beheben.
Aber es reicht nicht einfach, zuzulassen dass man Zelle X zweimal betritt, man muss auch verhindern, dass der Charakter ein Schritt raus aus der Sackgasse macht und dann aufgrund der Heuristik direkt wieder hineinläuft.
Das scheint mir ein völlig orthogonales Problem zu sein. Ich versteh aber auch nicht direkt, was an “die suche frisst extrem viele systemressourcen” genau so problematisch ist oder einer erklärung bedarf - ich denke dass A*-suche für pathfinding nicht ideal ist, insbesondere gekoppelt mit nem sichtradius, sollte klar sein. Die Frage ist also hauptsächlich: “Wenn du feststellst, dass das mehr rechenaufwand ist als man in das problem stecken sollte, wie lassen sich algorithmus und/oder heuristik adaptieren um das ganze zu verbessern”? Klar kannst du in deiner Antwort gerne Sackgassen erwähnen (auch wenn du dann bitte besser erklären solltest was du damit meinst, ich versteh deine erklärung nämlich immer noch nicht ganz, sorry :-/ ), aber das scheint mir jetzt sehr detailfixiert zu sein…
Also nochmal anders: nachdem du vorher schon gemeint hast, dass A* ja “im vorraus” berechnet wird:
Wenn du nen beschränkten sichtradius hast kann das nicht funktionieren. Du kennst ja die knoten nicht im detail, und um die, die außerhalb des sichradius liegen, zu expandieren muss sich der charakter zwangsläufig bereits bewegen.