Project 2: Voronoi

This project is a four-player game where the goal is to control territory while maintaining supply lines back to your home base. The action takes place on a square arena of size 100km by 100km. Each player has a home base offset by (0.5,0.5) from one of the corners towards the center of the board. Players start with one unit positioned at their home base. Every $n\geq 1$ days after that (where n is a parameter), each player generates a new unit at their home base.

Every day, players can move each of their units up to 1km in any direction, as long as they stay within the arena. All moves by all players are processed in parallel. All players see the entire state of the game before and after each move. Units are numbered in order of appearance, so you (and your opponents) can track the movements of individual units. For convenience, the simulator will maintain a game history for all players to access. Multiple units from multiple players can occupy the same cell, and even the same point, if required.

At the end of each day, the simulator decides who controls each 1km by 1km cell according to the following rules:

• A unit at position (x,y), where x and y are floating point coordinates with $0\leq x,y < 100$, occupies the cell $(\lfloor x \rfloor, \lfloor y \rfloor)$.
• A cell containing units from just one player is controlled by that player.
• A cell containing units from more than one player is disputed.
• For cells C that do not contain any units, the nearest cell(s) containing units are identified. (``Nearest'' here means that the Euclidian distance between the center of the two cells is minimum.) Let S be the set of such cells. If S contains units from just one player, then C is controlled by that player. Otherwise, C is disputed.
• The total number of cells controlled by each player is calculated, and will be used for scoring.

Each player's score is incremented by the number of cells they control on the current day.

At this point, the simulator checks that each unit has a path to the home base that traverses only cells controlled by that unit's player. A path can be a combination of orthogonal and diagonal steps. A unit without such a path has been cut off from the home square, and is lost, i.e., removed from the game. All lost units are removed simultaneously.

The game ends after a number of days t that is known to all players in advance. Players are trying to maximize their scores. We'll be averaging the scores (not the ranks) from many games to get an overall score. So ``winning'' a particular game is not as important as getting a good score. For example, getting a score of 10,000 but ranking 2nd might be better than getting a score of 9,000 while ranking first.

Things to think about:

• Note that moves in the north/south or east/west directions are guaranteed to change cells, while diagonal moves may not change cells. Is the position of the unit within the cell strategically important?
• Disputed cells don't add to any players' scores. Does this mean there's an incentive for all players to avoid disputed cells?
• As a multiplayer game, you might choose to selectively cooperate with another player. How would you decide who to try to coorperate with, and how would you achieve an ``agreement'' given that you can only communicate by moving your units?

This game is similar in spirit to the Outpost project from PPS 2014, but boiled down to the dimension of territorial control.