#

#
Gravitational Voronoi Game

#
Dennis Shasha

#
Omniheurist Course

#
Computer Science

##
*
Description
*

Game is played on a 1000 by 1000 grid.
Given a set of point-sized
stones (which we will call ``stones'' for simplicity) of various colors,
a gravitational Voronoi diagram is a tesselation of a plane into colored regions
such that every point x has the color of the stones that give it the
greatest pull.
The pull for a color c at point x is calculated as follows.
Take all the stones for color c and compute the Euclidean distances to x,
say d1, d2, ... dk.
Then pull(c,x) = (1/(d1*d1)) + (1/(d2*d2)) + ... + (1/(dk*dk)).
It's as if we're computing the color of a point based on the color that
gives the greatest pull.

The Graviational Voronoi game is a two person game that works as follows:
you and I each start with N stones (should be a command line
parameter throughout
-- no magic numbers in your programs please).
Yours are red and mine are blue.
The first player places one stone, then the second player places one stone
and play alternates with each player placing one stone until
the second player places the last stone.
All stones are placed at integer locations on the 1000 by 1000 grid
and every stone must be a Euclidean distance of at least 66 away from any
other stone.

As the game proceeds,
the Gravitational Voronoi diagram is computed.
The display should make the stones darker than the other points in the region.

It may help you to see this by looking at
a French implementation of the non-gravitational version of the game

Your job is to find a strategy to play this game competitively
on a one against one basis and as a * melee * in which
several players compete.

For the two player game, we will take the sum of your scores
as first player and second player.

Here is
Simon Lynch's version from 2010

Here are some results from
five stone games from 2011.

### Architect

The architect will accept move from one or more players,
display them on the screen, and color appropriately.
The architect will also send board positions and keep track of time.
In the "melee" version of Voronoi, many players compete and the one
with the most territory wins.

Here is the
github
for 2016.

Here is the architecture from 2015
by Dewei Chen and Mayank Singh.