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.