Zielauswahl

Sebastian Stock

In diesem Unterkapitel wird etwas genauer beschrieben, nach welchen Kriterien die nächste Zielposition ausgewählt wird. Dies geschieht in der Klasse Pathplanner. Als Basis dienen dabei natürlich die Tresore, Geschenke und die eigene Position. Aber auch die Positionen und evtl. bekannten Zielpositionen anderer Spieler werden berücksichtigt.

Um sich keinen künstlichen Vorteil gegenüber anderen Spielern zu verschaffen, verwendet auch der Agent nur diejenigen Tresore und Geschenke, die für ihn auch sichtbar sind. Diesen wird jeweils mit Hilfe einer Bewertungsfunktion ein Wert zugeteilt und der Tresor oder das Geschenk mit dem höchsten Wert wird als Ziel ausgewählt.

Chat der Agenten untereinander

Bevor auf die Bewertungsfunktion eingegangen werden kann, muss noch kurz ein weiteres Detail angesprochen werden. Ein Problem, das sich zunächst bei mehreren Agenten schnell gezeigt hat, war, dass sie nach einer gewissen Zeit alle das gleiche Ziel gewählt haben. Dieses kann verhindert werden, indem sie den Chat nutzen, um sich gegenseitig ihre Ziele mitzuteilen. Jedesmal wenn ein neues Ziel ausgewählt wurde, wird im Team-Chat "Next goal: ", gefolgt von der eindeutigen ID des Tresors oder Geschenkes, gesendet. Ebenso werden die anderen Spieler auch darüber informiert, wenn der Agent zu seinem bisherigen Ziel nicht mehr läuft, er einen Tresor geöffnet hat, das 8-Puzzle nicht lösen konnte oder ein Geschenk eingesammelt hat.

Bewertungsfunktion

Um den Tresoren und Geschenken einen Nutzen zuzuweisen wird zunächst deren Punkte-Wert durch die euklidische Distanz, der aktuellen Position des Agenten zu diesen, dividiert. Da man für das Öffnen der Tresore zwischen 10000 und 40000 Punkten erhält, die Geschenke jedoch keinen festen Wert haben, wird für diese ein Wert von 2000 Punkte verwendet. Man erhält auf diese Weise also jeweils die Anzahl der Punkte pro Meter. Dies ist zwar eine gute Basis kann durch einige andere Faktoren jedoch noch verbessert werden:

  • Wenn ein Mitspieler aus dem gleichen Team im Chat bereits angekündigt hat, zu diesem Ziel zu laufen, wird der Nutzenwert stark reduziert.
  • Die Positionen der anderen Spieler werden herangezogen, damit sich die Spieler besser verteilen: Wenn ein Mitspieler aus demselben Team näher am Ziel ist, wird dieses bestraft und der Nutzen mit Hilfe des Faktors 0.8 * teamDistanz / Distanz verringert, wobei teamDistanz die minimale Distanz eines Spielers aus demselben Team zum Ziel ist. Im Falle eines Geschenkes wird statt 0.8 der Faktor 0.2 verwendet, da es im Vergleich zu den Tresoren weniger sinnvoll ist, wenn sich zwei Spieler aus dem gleichen Team nur wegen eines Geschenkes in das gleiche Gebiet bewegen.

Die Positionen der Gegner gehen ausschließlich in die Bewertung der Geschenke ein und verringern auch hier den Nutzen, wenn sich ein Gegner näher an einem Geschenk befindet als der Agent. Dies hat mehrere Gründe. Wenn sich ein Gegner näher an einem Geschenk befindet und zu diesem läuft, wird er es wahrscheinlich auch früher einsammeln, wodurch der Weg umsonst wäre. Bei den Tresoren muss hingegen noch das 8-Puzzle gelöst werden. Auch wenn der Gegner den Tresor vor dem Agenten erreicht, besteht dennoch die Möglichkeit, dass er das 8-Puzzle schneller löst und den Gegnern so auch noch Punkte wegnimmt. Daher soll der Nutzen des Tresores in der Bewertungsfunktion auch nicht auf Grund eines Gegners verringert werden.

Beispiel

Das folgende Bild zeigt ein Beispiel für die Zielauswahl der Agenten und deren gewählte Route: Man sieht zwei Agenten aus demselben Team und deren berechneten Routen, an deren Ende jeweils ein Tresor liegt. Obwohl es Geschenke gibt, die näher an den Startpunkten liegen, haben sich beide Agenten auf Grund des höheren Wertes für Tresore entschieden.

Wie man an der Länge der eingezeichneten Routen sieht, hat der obere, blaue Agent bereits eine längere Strecke zurückgelegt. Daher muss er auch sein Ziel bereits vor seinem Mitspieler ausgewählt haben, da sich beide mit der gleichen Geschwindigkeit fortbewegen. Der blaue Agent hat sich also für den Tresor in der Mitte entschieden und ihn fast erreicht. Für den roten Agenten ist dieser Tresor auch deutlich näher als der Tresor links oben. Dennoch wird letzterer Tresor als Ziel gewählt, weil der blaue Agent im TeamChat bereits mitgeteilt hat, dass er zu dem Tresor in der Mitte läuft und dessen Nutzen für den roten Agenten dadurch deutlich sinkt.

Abb. 1: Zielauswahl zweier Agenten


Page last modified on March 21, 2011, at 05:53 PM