R
Andreas XXL schrieb:
Hallo, ich habe mal ne Frage zu A*
Den Algorithmus verstehe ich so halbwegs aber wenn ich z.B nen Spiel ala CßC habe mit z.B 512 * 512 Feldern, dann müsste es ja 512 * 512 Knoten geben.
Und von Jedem Knoten die kanten zu seinen 8 Nachbarn.
Das is doch nen bisl viel oder?
in den C&C versionen die 2d sind, sind es im leveleditor, wenn ich mich recht erinnere, 128*128 maximal und sie haben 4nachbarn. zudem gibt es dort nicht nur einen wegfinde algorithmus. zum einen gibt es etwas wie A*, das wird aber nur begrenzt oft aufgerufen (würde sonst bei ein paar hundert einheiten das spiel stehen lassen), und es gibt kleine lokale suchalgos, z.b. immer aufs ziel zu, wenn du auf ein hinderniss triffst, rechts abbiegen. und es gibt natürlich optimierungen z.b. wenn du mehrere einheiten selektierst, dann wird nur für die erste gesucht, die anderen versuchen dann einfach einen sehr nahen path zum ziel zu wählen sofern die einheiten in sichtweite sind.
Ich habe mir überlegt, dass wenn ich z.B nur jeden 2. Knoten nehme, dann gibt es ja Felder, zu denen ich nicht gehen kann!
Wie verringert man also die Knoten- und Kantenzahl ohne "nichtbegehbahre" Stellen zu erhalten?
heutzutage wären die maps viel zu hochauflösend für den speicherverbrauch und die performance eines normalen suchalgorithms, deswegen gibt es mehrere hierarchien, zum einen gibt es wichtige knotenpunkte im level (manchmal als raster ausgelegt, manchmal wie z.b. bei unreal auch von den leveldesignern per hand). diese knotenpunkte decken ein gewisses gebiet ab. möchte man nun eine einheit zu einer bestimmten stelle schicken, wird für die position der einheit zuständige knoten gewählt und für den zielpunkt ebenfalls. nun wird A* nur auf die knoten angewendet, so bekommt die einheit einen groben weg zum ziel.
währenddessen führt jede einheit stumpfe wegfindung zwischen den knoten druch, manchmal anhand eines ziemlich hoch aufgelösten rasters, manchmal auch anhand von geometrischen (oft konvexen) formen. diese "lowlevel" suche ist dann zwar sehr stumpf (und schnell), sie läuft aber auch nur für so lokale gebiete ab, dass diese stumpfheit nicht scheitern kann, sobald es ein problem geben würde (z.b. ein U-formiges gebilde), würden die A*-Knoten das gebiet in kleinere stücke aufteilen.
rapso->greets();
