Note: Bots are not permitted to edit this file. All content here is to remain human-authored.

voronoi-go-rs

A rust implementation of the rules of Voronoi Go, including associated python bindings and a language-agnostic engine binary. This package exists to provide people with a means of locally developing and validating game-adjacent software - primarily bots.

Be warned: code in this package was 100% AI ported from the original typescript client implementation. With that being said, I designed the API and reviewed all of the core files by hand and everything looks sane to me. Honestly a lot of it looks better than the original code, but maybe that's just a rust/typescript issue.

Any behavioral differences from the game client code are intentional and small (usually floating point edgecase related) and either target limitations present in typescript that rust doesn't need or differences in interface to make things more suited for bot development vs. human play. The rest of the behavior was verified against fixtures generated directly by the original implementation.

The other docs in this repo can be assumed to be machine-generated unless stated otherwise. I've read them too and they seem accurate if not overly verbose.

If you build a bot or other software using this package, I'd love to see it! I'm also available to answer any questions. Please feel free to drop into the Discord or open a Github issue.

Crates

There are three main crates included here:

• voronoi-go - the core rules implementation. Use this if you are developing in rust.
• voronoi-go-py - python bindings, published as the voronoi-go wheel. This is the best option if you are using python.
• voronoi-go-engine - a binary wrapper of the core rules that communicates in JSON over stdin/stdout. Should only be used if you're not writing in rust or python, as it has some serialization-related overhead that's not present in the other versions. See docs/protocol.md for info.

Installation

Installation depends on what you're developing.

You can also download directly from the releases page or run the (machine generated unverified) install script using curl -fsSL https://raw.githubusercontent.com/csun/voronoi-go-rs/main/install.sh \| sh

Usage Examples

In python:

import voronoi_go as vg

# Stones have radius 1.0 units so an 18x18 unit board is actually 9x9 stones
game = vg.Game(board_size=18)

snapped_move = game.nearest_living_move((4.2, 4.2))
delta = game.try_move(snapped_move)       # Can raise errors if move is invalid

game.undo_move()
game.pass_turn()

black_area, white_area = game.territory()

In rust:

use voronoi_go::{Game, Point};

// Stones have radius 1.0 units so an 18x18 unit board is actually 9x9 stones
let mut game = Game::new(18.0);
let snapped_move = game.nearest_living_move(Point::new(4.2, 4.2)).expect("Board has space");
let delta = game.try_move(snapped_move)?;

game.undo_move()?;

let black_area = game.territory().black();

In any other language, you can run voronoi-go-engine in a separate process and communicate via stdin/stdout:

→ {"id":1,"cmd":"createGame","boardSize":18}
← {"id":1,"ok":{"gameId":0}}
→ {"id":2,"cmd":"tryMove","gameId":0,"pos":[4.0,4.0]}
← {"id":2,"ok":{"newStone":{"id":0,"color":"black","pos":[4.0,4.0]},"capturedStoneIds":[]}}

How It Works

The voronoi stuff just uses voronator and then performs some logic to merge cells based on adjacency and color.

The deadzone stuff is more interesting because it was actually written specifically for this game. When playing the game you see the deadzone (where stones can't be placed), but in the code it's actually modeling the inverse - the alivezone.

The alivezone starts the game as a square inset by one stone radius from all sides of the board. The interior of this square represents all of the areas on the board where a new stone's center can be placed. Each time a new stone is placed on the board, it effectively blocks all future stones from being placed within 2 stone radii of itself - any closer and the stones would overlap. To model this, the alivezone "subtracts" a circle with radius 2 from the living area. When stones are captured, the alivezone "reclaims" their circles as living area.

When the alivezone is rendered, it is drawn with its edges expanded by one stone radius to represent the total swept area of valid circles that could be placed. Recall that it represents the valid placement area of stone centers, so if it were to be rendered without this expansion step you would only see tiny dots of living territory in tight spaces, rather than a more natural stone-sized hole.

The algorithm for performing this area subtraction and reclamation is bespoke. I couldn't find a library that could a) handle circles without discretizing them to polygons and b) handle edge cases with a bunch of things exactly overlapping.

In brief, it works by maintaining a list of circles that have been subtracted from the alivezone. Every time two circles intersect, they get further split into arc segments at the points of intersection. By tracing the segments on the hull of groups of intersecting circles (segments not overlapped by more than one circle), we can find all edges of the alivezone. From there, we can perform even/odd raycast tests to check if points are inside or outside of the alivezone, check shortest distances between lines and the alivezone boundary, etc. There is some substantial edge case logic around supporting multiple circles intersecting at the same point, as well as handling intersections with the outer (linear) edges of the board, but that's the general methodology. To learn more you can look at the alive_zone folder.

Documentation

To read the API docs from a checkout rather than the web, ./tools/docs-preview.sh

Performance

There's some claude-written benchmark info in docs/benchmarks.md.

No attempt has been made to optimize the code. I haven't profiled, but if you are interested in improving things I would look first at alivezone and use some sort of spatial hashing or similar to prevent iterating over all shapes and segments for each comparison. I would also look at voronoi and try to make it cache as much info as it can between territory rebuilds. Right now it rebuilds the whole diagram whenever anything changes even though it's usually just one stone being added. Alivezone is a bit better in this respect in the sense that it was built from the ground up to be able to add / remove single stones without rebuilding everything.