PWB 2013 - Die Aufgabe

Wir wollen ein Wettrennen veranstalten. Die Aufgabe der Programme wird es sein, eine möglichst schnelle Route zu einer gegebenen Menge von Checkpunkten zu bestimmen.

Die Route wird durch eine Folge von Schrittpunkten definiert. Das zu bewegende Objekt setzt sich aus Positions- und Richtungsvektor zusammen. Jeder Schritt verändert den Richtungsvektor um einen festen Betrag, im Anschluss wird der Richtungsvektor auf den Positionsvektor des Objektes addiert.

Es dürfen innerhalb einer bestimmten Zeit beliebig viele Routen abgegeben werden. Gewertet wird am Ende die letzte Route, der noch innerhalb der gegebenen Zeit eingereicht wurde.

Allgemeine Spielregeln

• Jeder Schritt kostet Energie, welche bei Erreichen eines Checkpunkts (teilweise) wieder aufgefüllt wird.
• Ein Checkpunkt gilt als erreicht, wenn der Positionsvektor des Fahrzeugs auf einen Punkt innerhalb des Feldes zeigt.
• Die Runde gewinnt derjenige, der nach Erreichen aller Checkpunkte die meiste Restenergie hat.
• Sollte während des Rennens die Energie auf 0 fallen, so scheidet das Programm für die Runde aus dem Rennen aus.
• Entspricht die Ausgabe nicht der erwarteten Syntax, scheidet das Teilnehmerprogramm aus.
• Zusätzlich gibt es Boosterfelder, die den Energievorrat erhöhen. Boosterfelder müssen nicht erreicht werden. Der Bonus von Boostern und Checkpunkt wird nur einmal pro Feld gewertet.
• Die Koordinaten von Checkpunkten und Boosterfeldern werden in ganzen Zahlen angegeben.
• Die Energie wird als ganze Zahl repräsentiert.
• Die Anzahl der Checkpunkte und Boosterfelder, sowie die Seitenlänge einer Rennstrecke werden nicht größer als 65335 (2^16 -1) sein.
• Der Startpunkt ist der Mittelpunkt des ersten Checkpoints.

Routen

Sei v der aktuelle Richtungsvektor. vwird immer mit (0|0) initialisiert.

Eine Route besteht aus einer Folge von Zeichen verschiedenen Zeichen.

• ‘N’ => v = v + ( 0|-1)
• ‘S’ => v = v + ( 0| 1)
• ‘W’ => v = v + (-1| 0)
• ‘E’ => v = v + ( 1| 0)
• ‘D’ => v = v + ( 0| 0)

Eine Route EESDWW würde die folgenden Punkte erreichen:

Felder (Checkpunkte, Booster)

Ein Feld ist ein 5-Tupel: (x1,y1,x2,y2,energy).

• x1,y1 definiert die obere linke Ecke
• x2,y2 definiert die untere rechte Ecke

Daraus lässt sich ableiten, dass alle Felder rechteckig sind.

Da die Felder die Energie der Teilnehmer manipulieren, wird zusätzlich die Energieveränderung pro Feld angegeben energy.

Aufrufkonvention

Die Teilnehmerprogramme werden für jede Aufgabe neu gestartet und nach abgelaufener Zeit falls nötig gewaltsam beendet. Nach Programmstart werden die benötigten Daten über die Standardeingabe übergeben. Mit dieser Übertragung beginnt die Zugzeit und es können Vorschläge eingereicht werden.

Zwischen dem Start der Programme und der Übergabe der Nachrichten lassen wir aus Gründen der Chancengleichheit genug Zeit, um z.B. eine VM oder einen Interpreter vollständig zu starten.

Die Daten werden jeweils in einer Zeile und immer in der folgenden Reihenfolge und Syntax übergeben:

1. Eine Liste von Checkpunkten im Format [Feld, Feld, ...]
2. Eine Liste von Boosterfelder im Format [Feld, Feld, ...]

Es ist zu beachten, dass während der Durchführung des Wettbewerbs die Standardeingabe von uns nicht geschlossen wird. Es sollte beim Einlesen der Daten also nicht auf ein EOF gewartet werden

Ausgabe

Die gefundenen Routen sollen als Schrittfolgen auf die Standardausgabe geschrieben werden. Jede Route soll mit einem Zeilenumbruch terminiert werden.

Die zuletzt geschriebene (vollständige) Route wird gewertet.

Wichtig: Wenn mit gepufferter Ausgabe gearbeitet wird, sollte immer der Ausgabepuffer explizit nach der Ausgabe einer Lösung geleert werden, damit die Lösung nicht versehentlich im Ausgabepuffer stehen bleibt.

Beispiel

Eingabe: Strecke

[(10,10,20,20,40), (50,10,60,20,40)]
[(30,30,40,40,100)]

• 2 Checkpunkte, Energie pro Checkpunkt: 40
• 1 Boosterfeld, Energie des Boosterfeldes: 100

Ausgabe: Route

EDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDDW

• Beschleunigung um 1 nach Osten E
• Drift bis zum Ziel DDDD...
• Bremsen durch Gegenschub nach Westen W

Der Wettbewerb

Wir werden mehrere Rennen veranstalten, pro Rennen wird eine Strecke vorgegeben, welche es abzufahren gilt. Dann werden die Lösungsprogramme mit den gleichen Vorgaben aufgerufen, um ihre beste Lösung zu ermitteln. Dabei wird die Rechenzeit beschränkt, es wird also darauf ankommen, möglichst zielgerichtet eine lukrative Lösung zu finden.

Bei den einfachen Rennen (kleine Strecken, wenige Checkpunkte) wird weniger Zeit zur Verfügung stehen als bei späteren Rennen.

Streckeneditor

Es gibt einen Streckeneditor, mit die Programm getestet und neue Strecken entwickelt werden können. Zu Ausführung wird Python 2.7 benötigt.

Versionshistorie

• Version 1.0: Erstes Release
• Version 1.1: Es werden beliebig viele Checkpunkte pro Schritt validiert
• Version 1.2: Bugfix für einen Fehler, der das Programm unter Linux zum Absturz bringt. Mausradunterstützung zum Zoomen unter Windows ergänzt.
• Version 1.3: Solverprogramm-Terminierung optimiert. Sofern die Python Image Library installiert ist, können Screenshots gemacht werden. Zeichnroutine für das Grid optimiert.
• Version 1.4: Neuimplementierung des Streamreaders für die Ausführung der Lösungsprogramme. Die Validierung zeigt jetzt die maximale und die Durchschnittsgeschwindigkeit an.

Der Grand-Prix

Zusätzlich zum eigentlichen Wettbewerb ist ein Grand-Prix geplant. Dieser ist unabhängig vom Wettbewerb und soll dem Training dienen, es wird keine Preise für die Sieger des Grand-Prix geben.

Hierfür lassen wir die Programme wöchentlich (bezeihungsweise auch nur zweiwöchentlich, je nach verfügbarer Zeit) auf einer Strecke gegeneinander antreten. Das Rennen erfolgt offline, es wird keine öffentliche Austragung der Grand-Prix Rennen geben. Im Anschluss an das Rennen werden Strecke und Platzierungen veröffentlicht. Für die Rennen werden Punkte wie in der Formel 1 vergeben. Der Erstplatzierte erhält 12 Punkte, der Zweite 10 Punkte, der Dritte 8 Punkte, die Plätze 4 bis 11 erhalten entsprechend 7 bis 1 Punkte.

Logo, Teamname und -farbe

Jeder Teilnehmer hat die Möglichkeit sein Programm abseits des Namens zusätzlich zu personalisieren.

Da wir ein Rennen veranstalten, kann jeder Teilnehmer / jede Teilnehmergruppe einen Teamnamen, ein -logo und eine -farbe angeben. Während des Wettbewerbs werden die Fahrzeuge dann in diesen Spezifikationen erscheinen.

Bitte schickt die Informationen über euer Team per Mail mit Betreff [PWB13] an Hanno Sternberg. Achtet darauf, dass das Logo nicht zu detailiert ist, da wir es gegebenenfalls stark verkleinern müssen für die Darstellung. Wir behalten uns das Recht vor, Logos nicht zu akzeptieren. Als Formate sind alle gängigen Raster- (JPG, PNG, …) und Vektorgrafikformate (SVG, EPS, …) möglich.

Die Farbe bitte als HTML-Farbcode angeben. Seid kreativ bei der Wahl der Farbe, wenn alle Fahrzeuge schwarz sind, ist es langweilig.