spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

Hi,
ich verwende in meinem Spiel ein Raster, um Objekte die sich in der game.world befinden einfacher darzustellen. Anhand dieses Rasters soll jetzt der schnellste Weg vom derzeitigen Aufenthaltspunkt eines Agenten zu einem vorher bestimmten Ziel ermittelt werden. Problem: Der Agent kann sich nur entweder geradeaus bewegen oder mit festen "Wenderadius" nach links oder rechts lenken.
Die Lösung hatte ich mir so vorgestellt: Die Strecke wird in mehre Abschnitte unterteilt, auf denen der Agent entweder lenken oder geradeaus fahren muss. Diese Abschnitte werden durch Waypoints begrenzt.
Ich suche jetzt also einen Algorithmus der die kürzeste Strecke zwischen Origin und Destination findet und diese anhand von Waypoints, gekoppelt mit "Lenkkomandos", speichert und so für der Agenten verwertbar macht. Allerdings werde ich wahrscheinlich nicht der Erste sein, der mit einem solchen Problem konfrontiert wurde.. Welche Lösungsmöglichkeiten würden sich hier anbieten?

Mfg Dooku

PS: Anbei ein Beispiel (schwar sind zuvermeidende Hindernisse; die türkis-gestrichelte Linie stellt ungefähr den gewünschten Verlauf des Agenten da..)

Zitat von »TGGC«

Zitat von »Schrompf«
Ganz laienhaft würde ich erstmal einen Flood Fill bauen, in kleinen Zeitschritten einen Baum von Bewegungsmöglichkeiten aufbaut, indem er von jeder Startposition aus die drei Basismöglichkeiten "geradeaus", "voll links" und "voll rechts" durchrechnet. Das wird ziemlich fix ein großer Baum, glaube ich, aber auf dem könnte man dann wieder ganz plump die A*-Heuristik anwenden.

Japp, genauso macht man das. Ist ja im Prinzip komplett analog zu dem Fall wo man sagt, ich geh ein Feld nach oben, unten, links oder rechts.

Das wage ich jetzt einfach mal zu bezweifeln. Folgendes Szenario:
Angenommen der Agent befände sich ganz am linken Rand des Spielfeldes. Das Ziel ist auf gleicher Höhe in das letzte Raster am rechten Rand gesteckt. Der Agent muss nur geradeaus nach Rechts "fahren", da keine Hindernisse auf der Strecke liegen.
Das Raster ist 100 Einheiten breit. Damit ein Agent jede Einheit im Raster erreichen kann, darf der Alg. das Raster also max. mit der Länge einer Einheit "abtasten" (Abtastung -> neue Ebene zum Baum hinzufügen). Bei 100 Einheiten die es zu überwinden gilt, läuft diese Abtastung also mindestens 100 mal. Pro Durchlauf (eine Abtastung) wird die Anzahl der Knoten mit 3 multipliziert -> Für die Anzahl der Knoten N_A in Abhängigkeit der Anzahl der Durchläufe n ergibt sich also grob N_A(n) = 3^n. Für das gewählte Beispiel ergeben sich somit zunächst ~5*10^47 Knoten.
Natürlich fallen da noch alle Knoten weg die außerhalb des Rasters liegen oder auf gleichartige fallen würden. Trotzdem ist allein diese Menge von Knoten (ohne Kanten) schlichtweg zu gigantisch....
Kommentare ?