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 ?