N. Zombings

The zombie brain is not famous for its complexity - this makes zombies easy to simulate. Simulating zombies helps you learn how they are best controlled.

We've prepared a simulation for you. You need to prove your ability by controlling your zombies so that more zombies will reach your goal.

The current state of the map and zombies are periodically sent out in UDP broadcast packets. Controlling your zombies is possible using a TCP connection.

http://todamax.kicks-ass.net/2010/zombie-lemminge/

All of the competing teams' zombies move around on the same map. Each team has a separate starting position, where their zombies spawn, but teleports also lead to these starting positions. Each team also has a goal, where they must get as many zombies as they can, to demonstrate your skill in controlling them. Although each player can only control their own zombies, they gain points for any zombies they get to their goal.

Scoring

A simulation game is run every hour with the following schedule: the server is listening to connections and broadcasting the map from 9:40, 10:40, 11:40,.. etc and the first spawn at 9:45, 10:45, 11:45,.. etc.

The hourly maximum contest score is 3500 divided by 24, multiplied by 0.5 for the first hour, 1.5 for the last hour, and linearly scaled in between. The team with the highest amount of points gets this amount, and the other teams get their score linearly based on their points.

Map

The zombies move around on a 2D map, represented by a width by height matrix. Each position in the map can contain one of the following:

Empty space.
Wall.
Indestructible wall
Teleport (indestructible)
Goal for one of the players (indestructible)

Also, there can be several zombies on a position, but they don't form part of the map. Building on a position means replacing space with wall, destroying a position means replacing wall with space. These actions can be applied to indestructible positions (it is not an error to do so), but they have no effect.

Zombie status

At any moment, a zombie's status consists of the following variables:

Position: x and y coordinates, where the top left corner of the map is (0, 0).
Direction: facing left or right.
State: what the zombie is doing at the moment. Can be walking, falling or one of the skills described below. They are referred to as the following enum values in the network protocol:

state	value
walking	0
falling	1
stopping	2
digging	3
shoveling	4
spiral stairs	5
bridging	6

State time: a wrapped around counter for how long the zombie has been in its current state. It's significance is described for each state separately.

Each turn of game time happens in 4 phases:

Build phase: this is when all zombies modify the map, create or destroy. Any pixel of the map that gets built in and destroyed in the same turn will be destroyed.
Movement phase: zombies move, using the already modified map from the first phase. This is also when zombies can die, teleport or reach a goal.
State time is increased by one, except if in walking state, then as specified below. If it reaches the wrap around for the state, it resets to 0.
Command phase: this is when the commands sent to the zombies take effect, all zombies that got a command change state, and their state time resets to 0. They will act according to their new state from the next turn.

Next is the specification of the zombies' behavious in each of these phases, depending on their current state.

Legend for ASCII drawings

S = Current position of zombie, facing right
+ = Next position for zombie
. = Empty space
# = Wall
! = Target for buiding or destruction
0..9 = Target after N turns

Build phase

Walking	Nothing
Digging	If state time is 0, the zombie tries to dig down. In this state, state time wraps around at 8, so this means every 8th turn, including the first turn in this state. If all of the target spots are space or wall, they get destroyed, if any of them are indestructible, none of them change. The target positions are the ones below the zombie, and the next four x coordinates in each direction.	........S........ ####!!!!!!!!!#### #################
Shoveling	If state time is 0, the zombie tries to dig horizontally. In this state, state time wraps around at 8, so this means every 8th turn, including the first turn in this state. If all of the target spots are space or wall, they get destroyed, if any of them are indestructible, none of them change. The target positions are the ones in front of the zombie (the next column in the direction it is facing), from his level to 10 above.	.........######## .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### ........S!####### ################# #################
Stopping	Stopping zombies only have a lifetime of 8 turns. During this time, they crystallize into a wall. When their state time is 0, 2, 4, 6 and 8, they build subsequent layers of a wall out, starting with the column they are in at time 0. In the current column they build into the rows from 3 below them to 10 above them. In the figure to the right, you can see which positions get built on in which round, compared to the position of the zombie (the S in the middle).	....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....8642S2468.... ####864202468#### ####864202468#### ####864202468#### ################# #################
Spiral stairs	When building spiral stairs, state time wraps around at 16, but the behaviour is different when state time < 13, and after. When state time < 13, and state time is even (so when it's 0, 2, 4, 6, 8, 10 or 12), the zombie builds into the spaces in front of it by 1 and to in its direction. (These are marked 1-7 in the figure, as it moves up as well.) Then, in round 14 it builds into the space above himself, into the space in front of that one, and builds up a wall of 15 spaces starting from the space 2 from the one above him in his direction.	................. ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... .........888..... ..........77..... .........66...... ........55....... .......44........ ......33......... .....22.......... ...S11........... ################# #################
Bridging	If state time is 0, the zombie builds one more piece of his bridge. In this state, state time wraps around at 8, so this means every 8th turn, including the first round in this state. It builds into the spaces in the column in front of it, from the one below, to a depth of 4.	........S........ #########!....... #########!....... #########!....... #########!....... #########........
Falling	Nothing

Movement phase

In this phase it is possible for the zombie to change state automatically, as described in detail below. If that happens, state time is reset to 0. If the state changes to falling, it the zombie will already fall this turn, so state time will be 1 by the end of the turn. If it changes to walking, it the zombie will only start moving next turn, state time will be 0 at the end of this one.

Walking	First, the zombie looks at the seven spots in front of him, from his level up to 6 above, and steps into the first empty one. If none of them is empty, it changes direction without moving. If it successfully stepped into the first spot (the one directly in front of him), it may descend at most 3 coordinates below, as long as the space under him is empty, without changing to falling. If it successfully stepped, the state time is set to zero. If it didn't (it changed direction), it keeps counting. If the state time is 4, they die (so they can't survive long when being stuck in a wall).	................. .........7....... .........6....... .........5....... .........4....... .........3....... .........2....... ........S1....... ################# #################
Digging	If state time is 0, and the zombie successfully dug, it moves down one. (That space is always empty, because destruction overrides building if it happens in the same round.) If state time is 0, but the zombie couldn't dig successfully, because of an indestructible block, it changes to walking, and will start moving in the next turn.	........S........ ####!!!!+!!!!#### #################
Shoveling	If state time is 0, and the zombie successfully shoveled, it moves in the direction it's working. (That space is always empty, because destruction overrides building if it happens in the same round.) If state time is 0, but the zombie couldn't shovel successfully, because of an indestructible block, it changes to walking, changes direction, and will start moving in the next turn. If all the target spots (the next column, from his level to 10 above) are empty it concludes that it's work is done, and changes to walking, and will start moving in the next turn.	.........######## .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### .........!####### ........S+####### ################# #################
Stopping	Stopping zombies never move, don't fall, and can't be changed to walking by a command either. If their state time is 8, they die.	....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....864202468.... ....8642S2468.... ####864202468#### ####864202468#### ####864202468#### ################# #################
Spiral stairs	If state time is 1, 3, 5, 7, 9, 11 or 15 (note: not on 13!), the zombie tries to move. If state time < 13, it's target is one up and one forward from him, if state time is 15, it is 2 up and one forward from him. If that space is not empty, it changes to walking, changes direction, and will start walking in the next turn. If it is empty, it moves there. If state time is 15 and the movement was successful, it changes direction as well.	................. ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ...........8..... ..........+8..... .........888..... .........+77..... ........+66...... .......+55....... ......+44........ .....+33......... ....+22.......... ...S11........... ################# #################
Bridging	If state time is 4, it tries to move one ahead. If that space is not empty, it changes to walking, changes direction, and will start walking in the next turn.	........S+....... #########!....... #########!....... #########!....... #########!....... #########........

After normal movement, if the space under the zombie is empty, it changes to falling mode, and already falls in this turn. (Even if it changed state in this turn to something else.)

Falling happens like this:

If the space under the zombie is not empty, it changes back to walking.
If state time is 11, it realizes the actual depth and dies of horror.
It moves down at most 3 spaces as long as those positions are empty.

After this, the following checks are done:

If the space below the zombie is a teleport, it moves the zombie to a different location. (Note that this doesn't change state, if the zombie was falling, its state time remains!)
If the space below the zombie is a goal space, the zombie disappears ("dies"), and the player that the space belongs to gets a point.

Commands

The commands to zombies consist of the number of the zombie it should be applied to, and the state they should change into. But there are restrictions on what changes are accepted. The restrictions are the following:

You can never give falling as a command.
You can never give a stopping zombie a command.
Falling zombies can only be given stopping as a command.
Zombies that are at most 50 Manhattan distance from a starting point can't be given commands.

It is however allowed to give walking as a command (except to a falling or stopping zombie), to stop whatever the zombie is doing at the moment.

Whenever a command is successfully given, state time resets to 0.

Summary

The following table summarizes the possible transitions between the different states. "auto" means the transition can happen automatically, "cmd" means it can happen by commanding.

FROM\TO	walking	falling	stopping	digging	shoveling	spiral stairs	bridging
walking	-	auto	cmd	cmd	cmd	cmd	cmd
falling	auto	-	cmd	-	-	-	-
stopping	-	-	-	-	-	-	-
digging	auto (indestructible) / cmd	auto	cmd	cmd	cmd	cmd	cmd
shoveling	auto (indestructible or empty) / cmd	auto	cmd	cmd	cmd	cmd	cmd
spiral stairs	auto / cmd	auto	cmd	cmd	cmd	cmd	cmd
bridging	auto / cmd	auto	cmd	cmd	cmd	cmd	cmd

UDP broadcast protocol

The server broadcasts binary udp messages continously. Each datagram message consist of one or more message chunks. Message chunks are identified by their first byte according to the table below. The first message chunk is always a tick (starts with a T). All numbers are unsigned integers in network byteorder (MSB first). {n:name} means an n-byte long unsigned integer referenced with the given name in the description. Other characters in the message chunk specification are bytes verbatim in the input with ASCII coding.

message chunk	description
T{4:tick}	following chunks correspond to the state after the `{tick}`th tick
M{2:x}{2:y}{2:length}{data}	This chunk contains map data {data} has {length} bytes after {tick}th tick, the {x}..{x}+{length}-1 of {y}th row of the map is {data} {data} consists of bytes: '.': empty '#': wall '%': indestructible wall 'a'-'z': goal of 0-25th teams '0'-'4': goal of 26-30th teams 'A'-'Z': teleport to 0-25th teams' starting point '5'-'9': teleport to 26-30th teams' starting point
Z{2:zombienum}{2:x}{2:y}{1:statewithtime} S{2:zombienum}{2:x}{2:y}{1:statewithtime}	These chunks carry information about the zombies zombie {zombienum} is at {x},{y} coordinates after {tick}th tick facing left if Z, right if S {statewithtime} has two 4-bit parts: high 4 bits is state time low 4 bits is state, can be 0-6 as described in the beginning
C{2:zombienum}{1:state}	These chunks broadcast all the commands that were given to the zombies, at the time of their execution, if they were successful. {zombienum}th zombie was commanded to do {state} after {tick}th tick

TCP response (server → client)

Control commands are sent using a text based TCP protocol. When a client connects to the server, it sends back various information in text format, each message on separate line:

message	description
allplayernum {playernum}	number of players
yourplayernum {playernum}	you are player {playernum}
mapwidth {width}	width of map
mapheight {height}	height of map
tickfreq {tickfreq}	number of ticks in a second
ticknum {ticks}	number of ticks in the full game
zombienum {zombienum}	number of zombies for each player
firstspawn {firstspawn}	first zombies spawn at tick {firstspawn}
spawntime {spawntime}	time between spawning of zombies
spawnpoint {playernum} {startx} {starty}	{playernum}th player's zombies spawn at {startx},{starty}
skillnum {state} {num}	each player can use {state} at most {num} times

Unsuccessful commands also get error messages through the tcp connection, successful commands get notification through the udp broadcast.

TCP control (client → server)

The client can send the following command to the server. Each command must be on a separate line.

message	description
{zombienum} {state} {tick}	Command your {zombienum}th zombie to change to state {state} (from the table above) after the {tick}th tick. {tick} must be in the future for the server, and the command must conform to the restrictions described in the "Commands" section, otherwise it will fail.