2D Bewegungs-KI für newtonsches Flugmodel

Einstiegsfragen, Mathematik, Physik, künstliche Intelligenz, Engine Design
Antworten
Despotist
Establishment
Beiträge: 394
Registriert: 19.02.2008, 16:33

2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Despotist »

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
Dateianhänge
Bewegungsvektoren.png
Bewegungsvektoren.png (7.76 KiB) 2899 mal betrachtet
Psycho
Establishment
Beiträge: 156
Registriert: 16.09.2002, 14:23

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Psycho »

Hallo,

nur mal zum Verständnis: Beschleunigen soll die KI nur am Anfang einmal, um dann möglichst genau das Ziel zu treffen?
Ich nehme an es ist so, dass das einfach die spritsparensde Methode es, es aber genauso möglich *wäre*, auch während des Fluges noch zu beschleunigen?!
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.
Das habe ich nicht verstanden. Wenn Du weißt, wie lange du beschleunigen möchtest (also bis zu welcher Endgeschwindigkeit) und du die Beschleunigung kennst, müsste sich das doch ausrechnen lassen. Und wenn das geht, würde ich die Lösung als "einfache" auch bevorzugen.
(Ich nehme an, die Station "treibt" durchs All und beschleunigt selbst nicht?!)

Kollisionen der Station lassen sich ja eventuell noch vorberechnen, aber zu prüfen, ob zwischendurch irgendein Asteroid deine gewünschte Flugbahn kreuzt klingt schon nach erheblichem Aufwand.
Da würd ich es einfach so machen, dass nach einer Kollision eine neue optimale Flugbahn gewählt wird. War dann halt Pech.

Bei Tiberian Sun im Multiplayer sind die Einheiten auch manchmal, wenn sich der Gegner bewegt hat, erstmal hart vorbeigelaufen. Ui.
Benutzeravatar
Lord Delvin
Establishment
Beiträge: 574
Registriert: 05.07.2003, 11:17

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Lord Delvin »

Da das Problem an sich schon theoretisch relativ hart zu berechnen ist, würde ich dir fast raten erst grob zu schätzen, wo das Ziel sein wird, wenn man ankommt(z.b. indem man schaut wie lange man mit der maximalen geschwindigkeit brauchen würde, wenn es keine hindernisse gäbe und die bewegung des ziels konstant wäre, das ist ja mathematisch einfach zu machen und vermutlich meistens eine gute näherung). Und dann sucht man sich einfach Graphbasiert den kürzesten weg und versucht da lang zu laufen, wenn man das oft genug iteriert, dann sollte da auch ein glaubhafter und meistens sehr guter weg rauskommen.
Als Erweiterung könnte man alle Objekte auf allen potentiellen Wegen etwas verschieben um die Zahl der Kollisionen zu verringern.

Ansonsten würd ich dir aber eher raten einfach eine greedy suche zu implementieren und zu hoffen, dass es nicht auffällt.
XML/JSON/EMF in schnell: OGSS
Keine Lust mehr auf C++? Versuche Tyr: Get & Get started
Despotist
Establishment
Beiträge: 394
Registriert: 19.02.2008, 16:33

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Despotist »

Psycho hat geschrieben: nur mal zum Verständnis: Beschleunigen soll die KI nur am Anfang einmal, um dann möglichst genau das Ziel zu treffen?
Nein. Ein mal Triebwerke zünden dauert 1 Sekunde und beschleunigt um 3-6 Pixel. Das wäre also viel zu langsam. Die Ki muss also mehrfach beschleunigen. Ich hatte aber schon vor eine "Höchstgeschwindigkeit" einzubauen damit die KI Zeit zum reagieren hat. Wenn man zu schnell unterwegs ist knallt man wo rein (und wird in andere Richtung gelenkt) oder fliegt am Ziel vorbei. Aber an sich kann jeder immer weiter beschleunigen, dem ist keine Grenze gesetzt.
Psycho hat geschrieben: Ich nehme an es ist so, dass das einfach die spritsparensde Methode es, es aber genauso möglich *wäre*, auch während des Fluges noch zu beschleunigen?!
Sprit sparen ist aber nicht der Hauptgrund da es fast nichts kostet. In der Zeit wo man langsam zum Ziel fliegt verdient man ja auch kein Geld durch Handel.
Psycho hat geschrieben: Ich nehme an, die Station "treibt" durchs All und beschleunigt selbst nicht?!
Ja. Sie verhält sich wie ein Asteroid und ändert bei Kollisionen nur die Richtung aber der Betrag der Geschwindigkeit bleibt gleich.
Psycho hat geschrieben: aber zu prüfen, ob zwischendurch irgendein Asteroid deine gewünschte Flugbahn kreuzt klingt schon nach erheblichem Aufwand.
Ist es auch. Die vielen Möglichkeiten machen es halt für KI schwer zu entscheiden wie sie am besten hinkommt. Ich weiß auch nicht welche Daten "fair" gegenüber den menschlichen Spielern wären da diese ja etwas eingeschränkt sind durch das Sichtfeld.
Psycho hat geschrieben: Da würd ich es einfach so machen, dass nach einer Kollision eine neue optimale Flugbahn gewählt wird. War dann halt Pech.
Mir wird wohl nichts anderes übrig bleiben aber dann kann eben der Fall auftreten das die KI sich schon in ungünstige Lage und Flugbahn begeben hat und am Ziel vorbeifliegt und erst mühsam umkehren oder eine neue Station als Ziel auswählen muss die sie besser erreicht.
Lord Delvin hat geschrieben: Da das Problem an sich schon theoretisch relativ hart zu berechnen ist,
Der Computer würde das sicher machen aber wie sage ich es ihm wie ? ;). Es sind einfach zu viele Variablen. Das hatte ich am Anfang nicht bedacht beim überlegen der Mechanik. Aber ich hoffe das diese "Unvorhersehbarkeit" und die vielen Einflussfaktoren das Spiel dafür für Menschen interessanter machen.
Lord Delvin hat geschrieben: würde ich dir fast raten erst grob zu schätzen, wo das Ziel sein wird, wenn man ankommt(z.b. indem man schaut wie lange man mit der maximalen geschwindigkeit brauchen würde, wenn es keine hindernisse gäbe und die bewegung des ziels konstant wäre, das ist ja mathematisch einfach zu machen und vermutlich meistens eine gute näherung).
Darin sind jetzt auch meine Überlegungen gegipfelt. Es wird ja ständig neu geprüft und die Flugbahn angepasst. Muss ich halt mal testen wie es aussieht. Zur Not muss die KI eben doch ein bisschen tricksen.
Lord Delvin hat geschrieben: Ansonsten würd ich dir aber eher raten einfach eine greedy suche zu implementieren und zu hoffen, dass es nicht auffällt.
Schönen Dank auch. Da du es erwähnt hast ist es nun vorbei mit "nicht auffallen" ;). So etwas hatte ich mir gedacht mit dem "Score" für verschiedene Varianten. Sind aber wie gesagt sehr viele Variablen die da einfließen und die manuell zu wichten wird schwer. Daher hatte ich eben auch an ein KNN gedacht was dies automatisch tut aber wiederum anderen Implikationen mit sich brächte.

Ich werd man versuchen bis Sonntag Mittag was einfaches zu basteln was funktioniert. Falls dann noch Zeit (Verlängerung) und Motivation da ist kann ich es ja noch verfeinern.
Erstmal Danke und wenn noch Ideen und Vorschläge sind nur her damit.
Henry
dronus
Establishment
Beiträge: 114
Registriert: 11.01.2010, 01:53

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von dronus »

Du kannst dir das Spielfeld als 3d-Raum vorstellen, mit deinem 2D Raum und einer Zeitdimension. Außerdem kannst du die aktuellen Geschwindigkeitsverktor des Raumschiffs von allen Objekten abziehen. Dann bekommst du für jeden Meteoriten und deinen Zielort einen schrägen Zylinder im 3d-Raum mit dem Durchmesser=Raumschiffdurchmesser+Objektdurchmesser.

Das Raumschiff bewegt sich ohne Antrieb nur auf der Zeitachse, sobald es seinen Motor feuert bewegt es sich auf einer Parabel. Wenn das Raumschiff sich sehr schnell drehen kann, also den Antrieb schnell in verschiedene Richtungen feuern kann, folgt es einer glatten Aneinanderreihung von Parabeln, das ist so eine Art quadratische Splinekurve.

Die KI könnte das Raumschiff in Zielrichtung drehen und dann den Antrieb feuern. Dann bekommt man eine Parabel die irgendwann den Zielortzylinder trifft. Du kannst einfach testen, ob diese auf dem Weg andere Zylinder trifft. Wenn das passiert, kannst dort einen Punkt an der Zylinderkante bzw. knapp draussen einfügen und erzeugst zwei glatt zusammengefügte Parabeln. Dazu sind ein paar Gleichungen zu lösen, die man sich allerdings erstmal hinfriemeln muss. Mit einer zusäztlichen Randbedingung kannst du sicherstellen dass das Raumschiff am Zielort zum Stillstand kommt. Das Ganze machst du solange, bis kein Zylinder mehr geschnitten wird. Wie man den Punkt außerhalb des Zylinders wählt ist etwas magic, da bei mehreren Hindernissen gleich sehr viele Möglichkeiten zustandekommen.. Da ist also etwas herumexperimentieren angesagt.
Benutzeravatar
Brainsmith
Establishment
Beiträge: 109
Registriert: 04.09.2009, 13:52
Echter Name: Fabbo

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Brainsmith »

Probiers doch mal mit Goal oriented action panning.
http://web.media.mit.edu/~jorkin/goap.html
http://web.media.mit.edu/~jorkin/GOAP_d ... 2_2003.pdf

Du verteilst einfach Prioritäten für die verschiedenen Verhalten (Angriff, Ausweichen etc)
Die KI sucht sich dann selber den passensten Weg raus. So könntest du auch auf Sachen reagieren, die bei Beginn der Szene noch nicht generiert sind ( wie zufällige Asteroiden)

Lass den Rechner denken ^^
Jaw
Beiträge: 54
Registriert: 14.07.2004, 01:00
Wohnort: Raum Düsseldorf

Re: 2D Bewegungs-KI für newtonsches Flugmodel

Beitrag von Jaw »

Ich denke so was wird gerne mal zerlegt. Egal ob ich etwas verfolgen, fangen, abschießen, parallel fliegen oder andocken soll, es gibt eigentlich zwei Probleme, erstens hin kommen, zweitens komplexe Interaktion. Wenn ich was verfolge was eh laufend die Richtung ändert bringt mir ein weiter Vorhaltepunkt nur Fehler. Je ungleichmäßiger die Flugbahn des Ziels, desto weniger sinnvoll ist ein Abfangpunkt schon im weiten voraus berechnet. Da liegt man ganz gut, erst mal zum Ziel zu fliegen, bis man nah genug ran ist. Und auch wenn ein Ziel linear fliegt wird nicht unbedingt der perfekte Kurs genommen, sondern es wird immer ein kurzer Vorhaltepunkt berechnet und der angeflogen. Den muss man eben laufend nach ziehen. Das ist also quasi ein ewiges Verbessern. Mit so etwas kommst du aber ausreichend und viel leichter ans Ziel. Und bei Dingen die der Spieler nicht sehen kann muss man nicht ordentlich sein. Was man wirklich merkt ist also eher die Navigation im Nahbereich.

Kurz ich denke dass immer eine begrenzte, kurzfriste Lösung reicht. Einfach ersma grob in die richtige Richtung. Allgemein würde ich sagen so dynamische Interaktionen zwischen beweglichen Dingen würde ich im Programm immer kontinuierlich lösen, also alle paar Frames neu nachrechnen und anpassen.

-JAW
Antworten