2D Bewegungs-KI für newtonsches Flugmodel
Verfasst: 27.05.2010, 22:11
Oje, da hab ich mir was aufgehalst. Das mit der KI ist doch viel schwieriger als ich gedacht hatte. Je mehr ich darüber nachdenke umso mehr Probleme fallen mir auf. Daher würde ich euch mal um Hilfe, Ideen und Einschätzungen bitten.
Randbedingungen:
Also das Spiel ist ja im Weltraum und der KI-Spieler hat Ziele die er anfliegen muss (Frachter, Stationen) und Dinge denen er ausweichen muss (Asteroiden, andere Spieler) um Kollision und Schaden zu vermeiden. Die Physik ist newtonsch also die Objekte bewegen sich in eine Richtung mit konstanter Geschwindigkeit bis sie kollidieren oder beschleunigen (Schiffe). Die Kollision ist unelastisch und die absolute Geschwindigkeit der beteiligten Objekte bleibt gleich nur der Winkel wird geändert (vom Kollisionspunkt weg). Also etwa wie Billard. Wenn ein Objekt das kreisförmige Spielfeld verlässt bekommt es einen zufälligen Geschwindigkeitsvektor der nach innen zeigt.
Die Parameter die die KI beeinflussen kann ist die Drehrichtung des Schiffes und wann Schub (impulsweise) gegeben wird. Zur Verfügung hat sie alle Objekt-Positionen und Geschwindigkeitsvektoren. Ein paar Kollisionen steckt das Schiff weg es ist also nicht tragisch nur fliegt man dann halt in eine ganz andere Richtung als man ursprünglich wollte. Und das Ziel kann auch mitten im Manöver wechseln z.B. durch Marktaktivität anderer Spieler oder Veränderung der Positionen (aus allen Werten wird ein Score für jedes Ziel berechnet und das Ziel mit maximalem Score gewählt). Die KI wird regelmäßig upgedatet (zur Zeit 1 mal pro Sekunde aber das kann ich anpassen).
Mein Problem jetzt ist, wie ich einem KI-Raumschiff am besten sage wie es zu seinem Ziel kommt nur durch Rotations- und Schubanweisungen. Gehe ich nun naiv ran und drehe mich direkt zum Ziel und beschleunige dann habe ich nach langer Flugstrecke eine hohe Geschwindigkeit und wenn sich das Ziel seitlich von mir weg bewegt kann ich nicht mehr genug in seine Richtung beschleunigen und fliege vorbei. Also muss ich auf die zukünftige Position des Zieles zuhalten (Vorhaltepunkt).
Mein bisheriger Denkansatz ist daher, die Zeit mit aktuellen Geschwindigkeitsvektoren weiter zu simulieren um auf mögliche Kollisionen mit dem KI-Spieler und die Flugrichtung zum Ziel zu prüfen. Dabei werden keine möglichen Kollisionen zwischen Asteroiden berücksichtigt (die deren Flugbahn ändern) und es wird simuliert als würde sich alles so wie bisher weiterbewegen aber das spielt erstmal keine Rolle. Es soll nur zeigen dass sich die Bedingungen ändern und ich dann dynamisch darauf reagieren muss bzw eine neue "Lösung" finden muss wenn der Vektor der Station sich plötzlich ändert (was ich aber eben nicht vorhersehe).
Ein besonderes Problem bereitet mir die Beschleunigung. Wenn ich zb aus dem Stand heraus beschleunige kann ich keinen Vorhaltepunkt bestimmen da sich meine Bewegung dahin aus konstantem Flug und beschleunigtem Flug zusammensetzt. Ich kann also nicht einfach mit Vektoren arbeiten wie ich das gern würde (Bild im Anhang). Weiterhin wenn ich mich schon in eine ungünstige Richtung bewege (z.B. weil neues Ziel gewählt wurde oder Station durch Kollision neuen Kurs hat) und ich in eine andere Richtung beschleunige ist der ursprüngliche Bewegungsvektor (im Bild grün) auch nicht mehr derselbe. Das heißt mein aktueller Bewegungsvektor (im Bild blau) bleibt auch nicht gleich. (Erklärung: Ein Pfeil im Bild repräsentiert die Bewgung in einem simulierten Zeitschritt).
Ich schwanke jetzt zwischen folgenden "Möglichkeiten":
- eine Kaskade von ifs und elses also quasi manuelles umsetzen meiner Entscheidungen: Con: Hölle zu programmieren, zu verändern (balancing) und zu debuggen
- Optimierung von Varianten/Befehlsketten (zb durch zufälliges Einfügen von Steuerungsoperationen und Bewertung anhand eines Scores) Con: Rechenpower/Laufzeit
- KNN (Fragen: Struktur/Typ? haben Gewichte bei anderem "Universum"/Spielfeld dieselben Werte oder muss es für jedes Spielfeld trainiert werden? Wie die Daten aufbereiten (Entfernung, Relevanz, Positionen, Vektoren, Spielerzustand)? Pro: Implement + forget Con: nicht-trivial
Ich will auch keine zu perfekte Lösung zum einen weil ich bezweifle dass die Rechner genug Power haben um tausende Fälle durchzusimulieren (und zu optimieren) und zum anderen um nicht den Eindruck zu erwecken die KI cheatet. Aber eine halbwegs clevere KI die nicht verliert (Geld für Reparaturen + Treibstoff alle) wäre schon wünschenswert. Super wäre es natürlich wenn die KI gezielt das Spielfeld nutzt zb sich durch gezielte Kollision treibstoffsparend in die richtige Richtung zu lenken. Aber das ist denke ich in dem Rahmen Illusion.
Unter den Bedingungen würde ich eine Woche mehr Zeit auch begrüßen ;). Ansonsten wirds halt qed (quick, einfach + dirty ;)).
Also wäre schön ein bisschen Input und Schubs zu bekommen.
Besten Dank
Henry
Randbedingungen:
Also das Spiel ist ja im Weltraum und der KI-Spieler hat Ziele die er anfliegen muss (Frachter, Stationen) und Dinge denen er ausweichen muss (Asteroiden, andere Spieler) um Kollision und Schaden zu vermeiden. Die Physik ist newtonsch also die Objekte bewegen sich in eine Richtung mit konstanter Geschwindigkeit bis sie kollidieren oder beschleunigen (Schiffe). Die Kollision ist unelastisch und die absolute Geschwindigkeit der beteiligten Objekte bleibt gleich nur der Winkel wird geändert (vom Kollisionspunkt weg). Also etwa wie Billard. Wenn ein Objekt das kreisförmige Spielfeld verlässt bekommt es einen zufälligen Geschwindigkeitsvektor der nach innen zeigt.
Die Parameter die die KI beeinflussen kann ist die Drehrichtung des Schiffes und wann Schub (impulsweise) gegeben wird. Zur Verfügung hat sie alle Objekt-Positionen und Geschwindigkeitsvektoren. Ein paar Kollisionen steckt das Schiff weg es ist also nicht tragisch nur fliegt man dann halt in eine ganz andere Richtung als man ursprünglich wollte. Und das Ziel kann auch mitten im Manöver wechseln z.B. durch Marktaktivität anderer Spieler oder Veränderung der Positionen (aus allen Werten wird ein Score für jedes Ziel berechnet und das Ziel mit maximalem Score gewählt). Die KI wird regelmäßig upgedatet (zur Zeit 1 mal pro Sekunde aber das kann ich anpassen).
Mein Problem jetzt ist, wie ich einem KI-Raumschiff am besten sage wie es zu seinem Ziel kommt nur durch Rotations- und Schubanweisungen. Gehe ich nun naiv ran und drehe mich direkt zum Ziel und beschleunige dann habe ich nach langer Flugstrecke eine hohe Geschwindigkeit und wenn sich das Ziel seitlich von mir weg bewegt kann ich nicht mehr genug in seine Richtung beschleunigen und fliege vorbei. Also muss ich auf die zukünftige Position des Zieles zuhalten (Vorhaltepunkt).
Mein bisheriger Denkansatz ist daher, die Zeit mit aktuellen Geschwindigkeitsvektoren weiter zu simulieren um auf mögliche Kollisionen mit dem KI-Spieler und die Flugrichtung zum Ziel zu prüfen. Dabei werden keine möglichen Kollisionen zwischen Asteroiden berücksichtigt (die deren Flugbahn ändern) und es wird simuliert als würde sich alles so wie bisher weiterbewegen aber das spielt erstmal keine Rolle. Es soll nur zeigen dass sich die Bedingungen ändern und ich dann dynamisch darauf reagieren muss bzw eine neue "Lösung" finden muss wenn der Vektor der Station sich plötzlich ändert (was ich aber eben nicht vorhersehe).
Ein besonderes Problem bereitet mir die Beschleunigung. Wenn ich zb aus dem Stand heraus beschleunige kann ich keinen Vorhaltepunkt bestimmen da sich meine Bewegung dahin aus konstantem Flug und beschleunigtem Flug zusammensetzt. Ich kann also nicht einfach mit Vektoren arbeiten wie ich das gern würde (Bild im Anhang). Weiterhin wenn ich mich schon in eine ungünstige Richtung bewege (z.B. weil neues Ziel gewählt wurde oder Station durch Kollision neuen Kurs hat) und ich in eine andere Richtung beschleunige ist der ursprüngliche Bewegungsvektor (im Bild grün) auch nicht mehr derselbe. Das heißt mein aktueller Bewegungsvektor (im Bild blau) bleibt auch nicht gleich. (Erklärung: Ein Pfeil im Bild repräsentiert die Bewgung in einem simulierten Zeitschritt).
Ich schwanke jetzt zwischen folgenden "Möglichkeiten":
- eine Kaskade von ifs und elses also quasi manuelles umsetzen meiner Entscheidungen: Con: Hölle zu programmieren, zu verändern (balancing) und zu debuggen
- Optimierung von Varianten/Befehlsketten (zb durch zufälliges Einfügen von Steuerungsoperationen und Bewertung anhand eines Scores) Con: Rechenpower/Laufzeit
- KNN (Fragen: Struktur/Typ? haben Gewichte bei anderem "Universum"/Spielfeld dieselben Werte oder muss es für jedes Spielfeld trainiert werden? Wie die Daten aufbereiten (Entfernung, Relevanz, Positionen, Vektoren, Spielerzustand)? Pro: Implement + forget Con: nicht-trivial
Ich will auch keine zu perfekte Lösung zum einen weil ich bezweifle dass die Rechner genug Power haben um tausende Fälle durchzusimulieren (und zu optimieren) und zum anderen um nicht den Eindruck zu erwecken die KI cheatet. Aber eine halbwegs clevere KI die nicht verliert (Geld für Reparaturen + Treibstoff alle) wäre schon wünschenswert. Super wäre es natürlich wenn die KI gezielt das Spielfeld nutzt zb sich durch gezielte Kollision treibstoffsparend in die richtige Richtung zu lenken. Aber das ist denke ich in dem Rahmen Illusion.
Unter den Bedingungen würde ich eine Woche mehr Zeit auch begrüßen ;). Ansonsten wirds halt qed (quick, einfach + dirty ;)).
Also wäre schön ein bisschen Input und Schubs zu bekommen.
Besten Dank
Henry