Voronoi diagram area game

Red area: Blue area:

Take turns placing points in the plane to maximize the area of your cells in the resulting Voronoi diagram. The player with a greater area after a set number of turns wins.
Base code taken from http://www.raymondhill.net/voronoi/rhill-voronoi.html

Game mode

turns per player.

Sandbox mode

random sites.
In sandbox mode, moving the mouse (or touching and dragging along the screen) previews the Voronoi diagram that would result from placing a site there.

Options

Hide sites. Limit sites to a grid with a spacing of pixels between points
Limit sites to one dimension Rectangular canvas Play against computer*
Quarantine mode (minimum distance between points)

*Playing against the computer only works in sandbox mode currently and can be started on either player's turn (red or blue). The computer player uses a simple greedy algorithm to pick its next point, looping through a grid of possible locations (with a spacing of 10 pixels between points to keep it reasonably fast) and choosing the one that maximizes its area after that turn.

For more in-depth analysis of strategy in the 2D Voronoi game, see Bouzy, Metivier, & Pellier, MCTS Experiments on the Voronoi Game, Advances in Computer Games, 7168 (2011), which suggests a balanced cell approach. The Voronoi game in 1D was solved by H. Ahn et al., Competitive facility location: the Voronoi game, Theoretical Computer Science, 310.1 (2004) and can be played here by checking the "Limit sites to one dimension" box. Slides from a talk I gave at FrankFest on the Voronoi game can be found here.

Other versions of Voronoi diagram generator:
Various visualization modes for Voronoi diagrams (including overlays with photographs of melons)
General Voronoi diagram generator (overlay user-specified images from web)

Back to programs