Archiv für den Monat: Oktober 2018

Fortschrittsbericht: September 2018

Im September fokusierte ich mich auf die KI Pfadfindung für Schiffe.

Es gibt viele erpropte Pfadfindungsalgorithmen, diese haben aber in der Regel einen Nachteil: Sie können nur eine sehr begrenzte Anzahl von Faktoren (z.B. die „Bewegungskosten“, die ein gewisses Terrain hat) mit in die Berechnung einbeziehen und suchen den kürzesten Weg unter der Annahme, dass sich der Agent praktisch frei bewegen kann. Das bedeutet auch, dass  diese Algorithmen bei de Pfadberechnung keine möglichen Faktoren, wie, dass der Agent sich nur eingeschränkt schnell drehen kann, oder, dass der Agent sich nur drehen kann, während er sich auch vorwärts bewegt, berücksichtigen können.
Ein weiteres Beispiel ist die Unfähigkeit, die Windrichtung/Geschwindigkeit underen Einfluss auf die Schiffsgeschwindigkeit mit einzubeziehen, um den schnellsten Weg zu finden.

Ein Algorithmus, der dies alles könnte, wäre wahrscheinlich leider nicht nur viel zu ineffizient, sondern bezüglich Zeitaufwand und technischem Anspruch nicht realistisch umzusetzen.

Statt dessen habe ich mich für folgendes entschieden: Ich nutze einen standard Algorithmus, doch statt dem errechneten Pfad direkt zu folgen, versuche ich, mit den gegebenen Bewegungsrestriktionen des Schiffes, dem Pfad so gut zu folgen, wie es geht. Würde z.B. der ideale Pfad verlangen, sich 5° zu drehen, das Schiff sich aber unter den gegebenen Umständen in einem Frame nur 3° drehen kann, dreht sich das schiff nur 3° und wird den Rest der Rotation im nächsten Frame zu Ende bringen.

Folgend ein Video, in dem dieser Ansatz mit verschiedenen maximalen Drehgeschwindigkeiten getestet wird. Wichtiges Detail: Momentan bewegt sich das Schiff immer mit der unter den gegebenen Umständen (Wind, etc). maximal möglich Geschwindigkeit und kann nicht langsamer werden, was das Problem weiter verschärft. Das istnicht 100% realistisch, könnte aber u.U. aus Gameplaygründen beibehalten werden. Aber selbst wenn nicht, wird das Schiff sehr wahrscheinlich eine gewisse Trägheit haben und nicht von einem auf den anderen Moment komplett stoppen können.

Beobachtungen

  • Gibt es keine engen Kurven im Pfad, funktioniert der Ansatz problemlos.
  • Enge Kurzven stellen ein grosses Problem dar.
  • Kann sich das Schiff schneller drehen, werden die Probleme weniger, verschwinden aber nicht.
  • In einigen Situationen kann man gut das Problem beobachten, welches ich Eingangs beschrieb: Es würde für das Schiff mehr Sinn machen, um ein Hindernis herumzufahren und in einem grossen Bogen zu wenden, statt zu versuchen, sich direkt zu drehen. Aber da die Pfadfingung  den kürzesten idealen Pfad ohne Berücksichtigung der langsamen Drehbewegung des Schiffes berechnet, versucht das Schiff, praktisch auf der Stelle um 180° zu wenden.
    Dieses Bild verdeutlicht das Problem:

    Traditionelle Pfadsuche findet nicht immer einen Weg, der auch für Schiffe geeignet ist… (Gelbe Linie = errechneter Pfad, Ende der Linie: Ziel)

Warum das kein Problem sein muss

Momentan werde ich aus folgenden Gründen nicht versuchen, dieses Problem zu beheben:

  • Das Schiffssteuerungsverhalten ist noch übeberhaupt nicht kalibriert. Solange ich nicht zumindest grob weiss, wie sich die Schiffe am Ende steuern, hat es keinen Sinn, die KI dafür zu optimieren.
  • Glüklicherweise bestehen Schiffskämpfe vor allem aus Wasser und einem gelegentlichen „Arrrh!“. Es gibt schlicht kaum Hindernisse. Höchstens ein paar Schiffe, der Rest ist offenes Meer.
    Wenn es kaum Hindernisse gibt, könnte es schlicht keine Rolle spielen, wenn die KI nicht gut darin ist, Hindernissen auszuweichen. Aber um sicher zu sein, muss ich erst eine simple Kampf KI entwickeln.

Was, wenn es doch ein Problem ist?

Ich habe schon einige Ideen, wie ich diese Probleme beheben oder zumindest entschärfen könnte:

  • Schiffe könnten langsamer werden und versuchen, sich in einem kleinen Radius zu drehen, wenn sie sich mehr als eine bestimmte Anzahl Grad drehen möchten.
  • Schiffe könnten sich nicht drehen, wenn sie zu nah an einem Hindernis sind, damit sie nicht damit kollidieren.
  • Ich könnte versuchen, vor einem Punkt kurz vor dem Schiff einen Weg zum Ziel zu berechnen und diesen nutzen, wenn er aus weniger Pfadsegmenten als der aktuelle besteht.
  • etc.