KL. Paper Boy

Your team has an honorable daytime job: you deliver the local newspaper, which contains absolutely essential information about the ongoing zombie apocalypse. Despite of the sudden drop in interest, you and your team decide to implement the best effort service described in your contract and deliver all the papers even if there are no readers anymore. Less traffic on the streets will speed up the process anyway.

https://upload.wikimedia.org/wikipedia/commons/6/68/Cpc464.computer.750pix.jpg

In this task, you have to implement real time dynamic control of 3 simulated bicycles. You have to deliver newspapers, perform stunts, and run obstacle courses in a world full of hazards.

Score for this task is the sum of two halves (both for maximum 2500 points each): "delivery" and "agility".

Delivery

In "delivery", each of your bicycles can gather game points by delivering paper and completing obstacle courses. For each hour of the contest, the game points gathered by the teams are scaled against each other in a linear manner to get the contest score (best team gets maximum hourly score, worse teams get the maximum hourly score multiplied by the ratio of their points to the points received by the best team). Game points are reset after each hour.

In each hour, every mailbox, checkpoint and course are worth points only once per bicycle. To get the theoretical maximum score for a game hour, each bicycle would have to visit every mailbox and checkpoint, and complete every course once, inside the hour.

Each mailbox and checkpoint has a "level": 1 to 4 (easiest to hardest). Courses are chains of checkpoints, and their score is determined by the level of their last checkpoint.

To receive points for a mailbox, a bicycle has to throw a bundled up newspaper and hit the mailbox. Each bicycle can only carry 30 newspapers at once. Newspapers are replenished by touching a reset point, or forcing a manual reset.

To receive points for a checkpoint, a bicycle just has to touch the checkpoint.

To receive points for a course, a bicycle has to touch all checkpoints in the checkpoint chain in order, reaching each subsequent checkpoint within 30 seconds after the previous one, without touching any other checkpoints or any resetpoints.

Awarded game points:

• Mailbox level 1 - 1 point
• Mailbox level 2 - 5 points
• Mailbox level 3 - 10 points
• Mailbox level 4 - 20 points
• Checkpoint level 1 - 2 points
• Checkpoint level 2 - 8 points
• Checkpoint level 3 - 16 points
• Checkpoint level 4 - 32 points
• Course level 1 - 20 points
• Course level 2 - 80 points
• Course level 3 - 160 points
• Course level 4 - 320 points
• Manual reset on a bicycle that's alive - -1 point

The hourly maximum contest score is 2500 divided by 24, multiplied by 0.5 for the first hour, 1.5 for the last hour, and linearly scaled in between.

Agility

The game tracks the completion time for obstacle courses (although the time doesn't matter for the "delivery" score). In each 6 hour period, leaderboards are built for each course completed by at least one team, using the completion time: the quickest team gets first place. For each course that the team completed at least once (with any bicycle), a value is calculated:

level * 0.8^place-1

Where place is the place in the leaderboard for the course (starting with 1), and level is the difficulty of the last checkpoint in the source (1 to 4). These values are then summed for the team, and the results are scaled against each other in a linear manner, with maximum score for each 6 hour period being 2500 / 4 = 625.

Bonus Task

Until the end of the 22nd hour (7:00), you can submit your own bicycle map (a file in the described map format), to the "Paper Boy - Your Own Map" task in the submission system. We don't plan to award any score for this. However, if we find a team-submitted map that we like that happens to work in our engine, we'll swap the game map to the team's map for the last hour of the contest (from 08:00).

The Paper Boy world is a 3D world with an euclidean coordinate system.

Orientation:

• increasing X goes "east"
• increasing Y goes "north"
• increasing Z goes "up"
• 1 unit = 1 meter

The world consists of tiles. Each tile is an axis-aligned box 5 meters in the X direction, 5 meters in the Y direction, and infinitely tall in the Z direction. In other words, if TX and TY are non-negative integers, then each tile contains the following section of the world:

 X = TX*5.0 ... (TX+1) * 5.0
 Y = TY*5.0 ... (TY+1) * 5.0
 Z = -infinity ... infinity

Each tile contains a type of floor, and may contain some objects. Objects are horizontally centered in the tile, and vertically begin on one of 8 special heights (called layers) - meaning objects stand on layers. One tile can have only one object standing on one layer, so one tile can have at most 8 objects.

The layers and their heights are:

height	layer
-2.5	"moat"
0.0	"road"
0.08	"sidewalk"
2.58	"elevation 1"
5.0	"roof"
5.08	"elevation 2"
7.58	"elevation 3"
10.08	"elevation 4"

There are four types of floors. A floor fills its tile horizontally, at a certain height. Floor types and their heights are:

height	floor type	description
0.0	"road"	normal road surface
0.08	"grass"	can be slippery
0.08	"sidewalk"	physically the same as the road, but slightly higher
-2.5	"lava"	a trench, with lava at the bottom. Don't fall in it

Map File Format

The map file is a text file with LF line endings. The first line of the map file contains a single integer: the map size, in tiles. The map is square, and contains map_size*map_size tiles.

The following map_size lines contain the rows of the map. The first line has tiles at TY=0, the next line has TY=1, etc.

Each line has map_size words. The first row specifies the tile at TX=0, the next one at TX=1, etc.

Each word is 10 characters long.

position	description
1	space (for separation)
2	floor type
3..10	objects in the 8 layers, in order of layer height.

The floor type is one of:

char	description
'r'	for road
'g'	for grass
's'	for sidewalk
'l'	for lava

The object type is marked by one of the following characters: ".1234hdulrftc_|ko".

char	meaning	description
'.'	empty	There's no object on the given layer.
'1', '2', '3', '4'	mailbox	Mailboxes have four different scores, '1' lowest, '4' highest. Physically, a mailbox is a standing cylinder, with 0.5m diameter and 1.8m height.
'h'	house	A house is a cube that horizontally fills the tile, and is vertically 5.0m high (so the roof of the house is at layer height + 5 meters).
'c'	reset point	When bicycles are reset, they're spawned standing on the nearest reset point. Reset points don't constitute a physical obstacle, but bicycles can touch reset points. A touch is detected when a bicycle wheel intersects a cylinder standing on the reset point with 4.0m diameter and 1.0m height.
'k'	check point	Checkpoints don't constitute a physical obstacle, but bicycles can touch checkpoints. The sensitive area is the same as with reset points (a cylinder with 4.0m diameter and 1.0m height). Checkpoints have more data at the end of the map file (see below).
'f'	flat surface	Fills the tile horizontally at the layer height, has the same physical properties as a road.
't'	elevated surface	Fills the tile horizontally at 2.5m above layer height, has the same physical properties as a road.
'u', 'd', 'l', 'r'	ramps	Ramps ascending to one of four directions. Ramps have the same physical properties as roads. They're rectangles that are at layer height on one edge of the tile, and at 2.5m above layer height on the opposing edge of the tile.
'u'	ascending to the north	It's a rectangle that is at layer height at the south edge of TY, and at layer height + 2.5m at the north edge of TY+1.
'd'	ascending to the south	It's a rectangle that is at layer height at the north edge of TY+1, and at layer height + 2.5m at the south edge of TY.
'l'	ascending to the west	It's a rectangle that is at layer height at the east edge of TX+1, and at layer height + 2.5m at the west edge of TX.
'r'	ascending to the east	It's a rectangle that is at layer height at the west edge of TX, and at layer height + 2.5m at the east edge of TX+1.
'_', '|'	planks	Planks have the same physical properties as roads. They're rectangles that lay flat on the layer height. They connect an edge of a tile with the opposing edge, but they're only 1.7m wide, leaving a (5.0-1.7)/2 = 1.65m wide gap on each side.
'_'	west-east plank	A plank connecting the west and east edges of a tile (centered at TY=0.5).
'|'	north-south plank	A plank connecting the north and south edges of a tile (centered at TX=0.5).
'o'	column	A physical obstacle. Columns are cylinders with 2.5m diameter and 2.5m height.

Mailboxes, checkpoints and resetpoints all have indexes. They're all indexed, separately, beginning with 0, in the order of map file appearance (from TX=0 and up, then TY=0 and up).

After the last encoded map row, the map file ends with metadata on checkpoints - one line per checkpoint, in index order (so order of appearance in map).

Checkpoint lines consist of words, separated by spaces:

    TX TY layer index next score name

• TX, TY are the tile position (redundant data).
• 'layer' is the layer index, 0..7 (redundant data).
• 'index' is the checkpoint index (redundant data).
• 'next' is the index of the checkpoint next in the course, or -1 if this checkpoint is at the end of a course (or is not part of a course at all).
• 'score' is 1, 2, 3, or 4.
• 'name' is the name of the checkpoint. May contain spaces, and may be "None" to indicate that the checkpoint has no name.

Geometry file

To aid with visualization and other algorithms, we provide a file (in the public file sharing area at http://server.ch24.org/public/) that contains a dump of the map geometry - someone may find this useful.

The file is a list of records, each record a line. Each line begins with a prefix character. Possible record types are these:

• q x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 - wall quad between the four vertices
• s x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 - slippery (grass) quad between the four vertices
• d x1 y1 z1 x2 y2 z2 x3 y3 z3 x4 y4 z4 - death (lava) quad between the four vertices
• k x y z score prevCP nextCP name - checkpoint
• r x y z - resetpoint
• m x y z score - mailbox
• o x y z radius height - column (a cylinder of wall standing on the given point, radius always 1.25, height 2.5)

Protocol

Coordinate system

Units are meters. All angles are radians.

Control (player → server)

UDP packets, text based, rows separated by LF.

First row is a single 32 bit unsigned integer sequence number. Packet is ignored if the previously received packet had a >= sequence number. If no packets are received for 10 seconds, the internal counter is reset to 0 (the first packet sent by the player should have a sequence number of 1).

Following rows are commands, one command per row. Commands are composed of words, separated by spaces.

Bicycle control command summary:

command format	description
<bicycle_id> <thrust> <steer> <weight>	Set control input
<bicycle_id> reset	Move the bicycle to a nearby resetpoint in a standing position. (Uncontrolled, unbalanced bicycles will tip over.)
<bicycle_id> paper <vx> <vy> <vz>	Throw newspaper with a certain speed. Only one newspaper may be in the air at a time for a single bicycle (if there's an active newspaper, the throwing command is ignored).
<bicycle_id> cam	Focus the camera on the selected bicycle.

parameter	type	value range	description
bicycle_id	integer	1 .. 3
thrust	float	-1 .. 1	controls the brakes (-1..0) and pedalling force (0..1). Any amount less than -1 for thrust will apply a small, constant reverse thrust.
steer	float	-1 .. 1	controls the front wheel. (left .. right)
weight	float	-1 .. 1	controls the center of mass. (left .. right)
vx,vy,vz	float	*	velocity in m/s. If the given velocity vector is greater than 10m/s, it will be scaled down to 10m/s (keeping its direction).

Control values are saved and used until the following command.

'steer' and 'weight' are inputs to a controller, they aren't immediately actualized.

Update (server → player)

UDP packets, text based, rows separated by LF. Words are separated by single spaces.

• First row is:

  <sequence_num> <recv_sequence_num> <errors>

  'sequence_num' is a 32 bit unsigned integer sequence number incremented with each packet.

  'recv_sequence_num' is the sequence number of the last received packet from the player.

  'errors' is the number of protocol errors (increases when control packet couldn't be processed, or was discarded).

• Subsequent rows are:

  B bicycle_id bx by bz fx fy fz roll steer weight dead

  bicycle_id: integer, 1 .. 3

  bx, by, bz: position of back wheel hub
  fx, fy, fz: position of front wheel hub

  'roll' is the angle of the bicycle seat above the back wheel from vertical (-PI/2: laying on the left side; PI/2 laying on the right side).

  'steer' is the angle of the front wheel to the rest of the bicycle (-PI/2: facing left; PI/2: facing right).

  'weight' is the current position of the center of mass (-1: left; 1: right).

  'dead' is 0 when the bicycle is alive, 1 when the bicycle is dead.

• For each active newspaper:

  N bicycle_id x y z

• Gamestate

  G bicycle_id newspapers checkpoint

  This is a game state update, sent every once in a while, and when the gamestate changes.

  'newspapers' is the remaining number of newspapers.
  'checkpoint' is the index of the last visited checkpoint, if a checkpoint path is being tracked, or -1 when not.

• Killed event

  K bicycle_id reason

  This message is sent once when a bicycle is killed. Reason is one of:

  • HEAD - person mass touched something.
  • BUTT - person mass touched by other person mass (headbutt)
  • SQUISH - person mass touched by a bicycle wheel
  • WHACK - person mass touched by newspaper thrown by other bicycle
  • LAVA - bicycle touched lava

• Newspaper got into mailbox event

  M bicycle_id index

  This message is sent once when a newspaper gets into a mailbox.
  'index' is the mailbox index.
  Gamestate will also be sent in the same packet.
  The event is sent even when the mailbox has already been filled in this hour (so no points are awarded).

• Resetpoint event

  R bicycle_id index

  This message is sent once when a resetpoint is touched.
  Gamestate will also be sent in the same packet.
  'index' is the resetpoint index.

• Checkpoint event

  C bicycle_id index name

  This message is sent once when a checkpoint is touched.
  Gamestate will also be sent in the same packet.
  'index' is the checkpoint index.
  'name' is the checkpoint name (may be empty, may contain spaces).

• Course completed event

  O bicycle_id index time

  This message is sent once when a course is completed.
  Gamestate will also be sent in the same packet.
  'index' is the checkpoint index (of the last checkpoint).
  'time' is the course completion time (seconds, floating point).

• Checkpoint timeout event

  T bicycle_id

  This message is sent once when 30 seconds elapse since the last checkpoint was touched (so the checkpoint chain is interrupted).
  Gamestate will also be sent in the same packet.