Jump to content
  • Advertisement
Sign in to follow this  

Voronoi two-sphere war game (similar to Go)

This topic is 2353 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Voronoi two-sphere war game (similar to Go)

The idea of Delaunay/Voronoi tesselations is used here, so see http://www.comp.lanc.../voronoi/dt.gif if you aren't already familiar with the idea -- the dark lines in this image are the edges of the Delaunay triangles, and the dashed lines are the edges of the Voronoi cells (ie. hexagons, etc). The Voronoi vertices (where the dashed lines meet) are not explicitly shown in this image, but I'm sure you get the idea.

The game is similar to the traditional game Go, except that it's played on a spherical board rather than a flat board, and some of the rules are slightly different. I won't be able to polish the game up to distribution quality any time soon, and I don't think I'd charge for it even if I did complete it... so this is all up for grabs by anyone who might be interested in it. If you like it, and make your fortune from it, then consider doing the right thing and donating some of the money to the SPCA, or whatever. I mean, consider the fact that traditional Go is one of the oldest and most popular board games -- EVAR. However, for all I know, this idea of "Voronoi Go" may not be entirely new, as unlikely as that may seem (most people wouldn't ever care to know about Delaunay and Voronoi diagrams). Can you think of any optional rules that might make it more fun/challenging?

Game details:

- Two players, white and black

- Game board, Voronoi vertex mode:
- Board Initialization Step A: Each board is initially generated from a set of X roughly uniformly distributed seed vertices on a two-sphere. X can be anything reasonable (ie. 20, 200, 2000, not 2 or 2000000000000).
- Step B: A set of 2X - 4 = Y Delaunay triangles is generated from the seed vertices (keep in mind the Euler characteristic of a tesselated two-sphere is vertices - edges + faces = 2).
- Step C: A set of Y Voronoi vertices are generated from the barycentres of the Delaunay triangles (could use circumcentres, but that looks ugly).
- Step D: A set of Voronoi cells (ie. many-sided polygons, mostly hexagons, like a honeycomb) is generated from the Voronoi vertices. The end result is a set of Y Voronoi vertices that are connected to each of their three nearest neighbours by edges. Each Voronoi vertex represents a distinct position on the game board, and each of the position's three nearest neighbours represent adjacent positions on the board. Take a look at a standard honeycomb to get the idea.

- Alteratively: Rather than using the Voronoi vertices that define the cells as the positions (which, again, gives a constant nearest neighbour count of exactly 3), one could instead use the centres of the Voronoi cells as the positions on the board (which would give a non-constant nearest neighbour count of roughly 6). One could also use the centres of the Delaunay triangles as the positions (constant nearest neighbour count of 3), or even the Delaunay vertices as the positions (non-constant nearest neighbour count of roughly 6). All said, there are four different ways to use the Delaunay/Voronoi tesselation as a playing board made up of distinct positions.

- Pieces per player:
- Where P is the total number of positions on the board, and P is even, then both players start with P/2 pieces. Where P is odd, then white gets (P - 1)/2 + 1 pieces, and black gets (P - 1)/2 pieces. ie. 361 positions, white gets 181 pieces, black gets 180 pieces.

- Turns:
- All positions on the board are empty at the beginning of the game. Each player takes turns consecutively. One round consists of a turn from both players. Each player can place one piece onto the board per turn/round. Pieces can only be placed onto positions that do not already hold a piece.

- Territory:
- When an empty contiguous region is entirely surrounded by white pieces, the empty region is considered to be territory belonging to white. Likewise for empty regions that are entirely surrounded by black pieces. Territories are still entirely fair game for both players to place pieces into. Essentially, territories only really make a big difference in the grand scheme of things when the game ends and the final scores are calculated.

- Annihilation/Prisoner taking:
- When a contiguous region filled with white pieces is entirely surrounded by black pieces, or vice versa, the surrounded region's pieces are evacuated from the board and put into the opposing player's prison. Obviously, the newly evacuated region becomes a territory, and once again becomes entirely fair game for both players to place pieces into.

- Forbidden move:
- A player cannot place a piece onto the board if that placement would result in the immediate annihilation of that piece (or region of pieces). In other words, no blatantly suicidal moves.

- Game ends:
- When one player runs out of pieces to place onto the board.
- When both players agree to a truce.
- When one player surrenders.

- Counting score at the end of the game, per player:
- One point per unplayed piece.
- One point per piece on board.
- One point for opposing piece in prison.
- One point per position per territory region (ie. if a territory is 10 positions large, then player gets 10 points for that territory).
- Player with most points wins.

- Optional rules:
- Nuclear mode: Annihilation turns newly evacuated regions into totally unplayable "wasteland". No one can place pieces in the "wasteland", either permanently or at least for a set number of turns/rounds.
- Delegate mode: White also has a small number of "blue" delegate pieces, black has "red" delegate pieces. Delegate pieces cannot be annihilated, but they do help cause annihilation. Useful for halting annihilation altogether (ie. a black region with one red delegate on its border means that white/blue cannot fully envelop the black region, and so it cannot be annihilated).
- Prisoner treason mode: White pieces taken prisoner by black can switch to the black side after a set number of turns/rounds, and these newly minted black pieces can then be placed onto the board by the black player, and vice versa.
- Delegate treason mode: Sometimes (partially randomly?) delegates can switch to the opposite colour (ie. blue to red, vice versa, or even blue to black in very rare instances, and vice versa).
- Player treason mode: Sometimes a white piece on the board switches to black or blue, vice versa. Similar to delegate treason mode and prisoner treason mode.
- More than 2 players.

- Graphics:
- OpenGL ES 2. Single light phong / toon shader hybrid. Vertex buffers. Simple.
- Spheres for pieces, spherical triangles for playing board (includes Voronoi cells, which can be modeled as a set of triangles) to make up one large sphere, and curved cylinders stretching between nearest neighbour positions. Simple. Alternatively, one could instead use flat triangles and flat cylinders to increase performance, though it would look rather crude.
- Text just uses pre-generated textures and a pass-through colour shader. Simple.

- Controls:
- Spherical coordinates camera (not quaternion camera) to keep players well-oriented. Gimbal lock / camera up inversion obviously accounted for / avoided by keeping latitudinal angle within bounds at all times.
- Mouse/swipe "free" rotation. If too much swiping is considered to be a problem...
- Button/tap rotation (ie. rotate by 45 degree increment left/right/up/down).
- Single click on the board to select a position, click again on roughly same spot to place a piece on selected position.

- Notes:
- Obviously board edge cannot be exploited like in traditional Go, since there is no board edge on the two-sphere. Sorry traditional Go players.
- The basis of any computer AI will likely require that all open positions be given a white/black score based on proximity to white/black pieces. This mapping of position -> score would act as a guide as to where the AI should be forming annihilating boundaries around opposing regions, and where it should be forming regions of its own. A simple score could be made up of the distance to just the closest white / distance to closest black, or a not-so-simple score made up of distance to all pieces. Edited by taby

Share this post

Link to post
Share on other sites
You seem to be missing the ko rules, which I suspect still apply to the modified board space.

Share this post

Link to post
Share on other sites
Yes, you're right that ko (direct revenge) and superko moves aren't listed here, although wastelands kind of generate superko... sort of. Thanks for adding to the list. Perhaps a full explanation of these rules would help, for the benefit of everyone, if you are up to spending the time to write it down.

And yes, I do believe that all of the traditional Go rules can still be applied, except for those related to the board edge (... and some of the scoring/handicap rules that rely on an odd number of positions, which would not apply when using a board with an even number of positions). Edited by taby

Share this post

Link to post
Share on other sites
I'm a long-time go player, and looking at this, the rules seem to be the same, except for the board shape and the connectivity structure between the nodes.

Playing Go on board shapes different from the 9x9/13x13/19x19/some other square grids is not a particularly new thing. In real life, some of the more exotic board variants I have stumbled onto are Go on 3D cylinder boards (one-sided, flattened onto a 2D plane), three-player Go on a triangular board and Go on a multi-level board, e.g. a bit like 3D chess. For a change from the standard Go game, it's a lot of fun! I wish some of the online sites like gokgs.com would adopt these game variants, that would make them a lot easier to play.

Share this post

Link to post
Share on other sites
Right on... there we have it... a whole list of alternative boards to use. Awesome. smile.png

The whole curved / getting away from the 4 orthogonal/parallel connections per position would totally mess with tactics, I'm sure. I mean, I can't think of how ladders would work all that well on the two-sphere. As I'm sure you can tell, the main idea behind using the Delaunay/Voronoi on two-sphere was meant primarily to be closest to "war" on the surface of a planet. That said, a triangulation/dual with roughly uniformly distributed vertices can be made on almost any kind of reasonable surface (ie. Stanford bunny), which could lead to some very interesting (annoying?) levels.

Thanks for this, and thanks for the link to gokgs.com. Apparently one can spectate? That's awesome. Edited by taby

Share this post

Link to post
Share on other sites
Sign in to follow this  

  • Advertisement

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!