Voronoi Grid — Prototype

A Hamiltonian path puzzle built in Unity as an architecture- and algorithm-focused showcase project. A board is cut into irregular polygonal segments; you start at the centre and open one neighbour at a time, trying to open them all — without stranding yourself.

Everything is procedural: there are no sprites, no prefabs, and no GameObject per segment. The whole board is one mesh drawn by one shader, and every level is generated at runtime.

Tech Stack: Unity · VContainer (DI) · UniTask (async) · Unity Input System · NUnit (Edit Mode Tests).

Game loop: generate grid → open a neighbouring segment → keep going → open every segment (win) or run out of neighbours (dead end) → restart (R / Touch & Hold).

What this project is about

Two things got the attention, and they are the interesting part:

1. Generation speed — specifically, predictable runtime. The generator performs no search or retries: every step is guaranteed to succeed, producing the same generation cost on every level start and restart.

2. Architecture — every system sits behind an interface and is composed by dependency injection. The rules, the undo history, and the puzzle generation carry no rendering and no engine logic, which is why they are unit-testable without opening a scene.

What was built

Gameplay

• Procedurally generated levels with a guaranteed solution — solvability is constructed, never searched for.
• Undo system and win / dead-end detection.
• Deterministic generation: a fixed config seed always reproduces the same board.

Input

• LMB / Tap: Open a neighbouring segment, or click the head to undo the last move.
• Hover: Highlights which segments can be opened.
• R / Touch & Hold : Restart the level instantly without reloading the scene.

Presentation

• The entire board is rendered as a single procedural mesh with one material.
• Segment contours, gaps, and inward glow are computed as a signed distance field in the shader from a per-cell edge table packed into a data texture.
• An animated energy line traces the opened path.
• The board preserves the grid's aspect ratio, and the camera frames it automatically.

Tuning

• The grid size (N × M) and fill ratio are the only generation parameters; segment count, board shape, and cell size follow automatically.
• All visual dimensions are defined as fractions of a lattice cell, keeping the appearance consistent at any grid size.

Running it

1. Open the project under VoronoiGrid-Unity/ in Unity.
2. Press Play from any scene.

How level generation works

The board is a Voronoi diagram, and the puzzle graph is read straight out of it.

1. The spine — a guaranteed solution, built by backbite. A Hamiltonian path visits every cell exactly once. Deciding whether one exists in an arbitrary graph is NP-complete, so the generator never asks: it constructs the path first and builds the board around it.

The path starts as a boustrophedon — a snake walking the lattice row by row, back and forth. Its first N cells are a valid self-avoiding path by construction. Then it is randomised by a fixed budget of backbite moves, each of which turns a valid path into another valid path of the same length:

• Reversal — the path's end bonds to a neighbour already on the path, forming a loop; breaking the loop's far bond reopens it as a path. The occupied cells stay the same; the traversal order changes.
• Reptation — the end steps onto a free cell and the opposite end gives up its own. The length holds while the path's footprint moves across the grid.

Because no move can fail, there is nothing to search and nothing to backtrack: the spine is a fixed number of guaranteed-successful moves, so generation costs the same every single time.

2. The seeds. Each spine cell becomes a seed point, jittered inside its cell to make the shapes organic. The start seed is never jittered, so the board's centre always lands inside the starting segment.

3. The Voronoi cut. A cell is the set of points closer to its seed than to any other. It is built by clipping the board rectangle with the perpendicular bisector against each nearby seed (Sutherland–Hodgman). Seeds are bucketed into a spatial grid and visited in expanding rings, and the walk stops as soon as the next ring is provably too far to touch the shrinking cell — which keeps this linear in the number of segments instead of quadratic.

4. The graph is read off the geometry. Two segments are neighbours iff their polygons share a visible border. This is the project's central invariant: the graph is never built separately from the picture, so the game can never disagree with what you see. Because every shared border becomes an edge — not just the spine — you are free to leave the guaranteed path and strand yourself. That is the game.

5. Validation. A validator recomputes the invariants from scratch (connectivity via BFS, the embedded Hamiltonian path, articulation points and bridges via Tarjan) and logs a report. It reports; it never repairs — correctness is guaranteed by construction, so a failed check means a real regression rather than a level to throw away.

How visualization works

Once the polygons exist, they are turned into exactly three things:

• One mesh. Every cell is fan-triangulated (valid because Voronoi cells are convex) into a single mesh, with the cell's id written into its UVs.
• An edge texture. For each cell, every polygon edge is stored as an inward-facing half-plane (normal + offset) in a row of a float texture. The fragment shader reads that row and takes the minimum distance to all of them, which gives it a signed distance field for the cell — that is what draws the gap between segments, the contours, and the glow, with analytic anti-aliasing and no extra geometry.
• A state texture. One row per cell holding its tint and emission. Opening a segment rewrites a few pixels rather than touching any object.

The result is a board of any size at one draw call, where the game state is uploaded as pixels.

Tests

The core logic is covered by EditMode unit tests, all running without Unity objects: generation invariants (segment count follows the grid, connectivity, the embedded Hamiltonian path, every edge being a genuinely visible border, per-seed determinism, rectangular boards, even coverage) and the pure game rules (move classification, win, dead end, undo).

Architecture

Two composition roots assemble the app: BootstrapScope registers infrastructure and loads the Core scene; CoreScope registers the gameplay systems and its CoreFlow entry point runs the ordered async startup. Restarting a level does not reload the scene — GameService simply generates a new one.

System	Responsibility	Unity
LevelFactory	Orchestrates generation: grid → spine → seeds → Voronoi → graph	No — engine-free logic
SpineBuilder	Backbite: the guaranteed Hamiltonian path	No — engine-free logic
SeedPlacer	Places Voronoi seeds from graph nodes, applying deterministic jitter while keeping the start seed fixed	No — engine-free logic
VoronoiBuilder	Half-plane clipping and reading adjacency off the geometry	No — engine-free logic
SeedGrid	Spatial buckets powering the ring-walk neighbour queries	No — engine-free logic
BoardMapper	Lattice → world mapping: cell size and the board rectangle	No — engine-free logic
GraphValidator	Invariant checks and metrics (BFS, Tarjan)	No — engine-free logic
RulesService	Move classification and outcome — the single definition of a legal move	No — pure C#
UndoService	The opened path, head, and open-set	No — pure C#
RandomProvider	The one deterministic random source	No — pure C#
GameService	Game loop: start, hover, click, outcome	Yes
LevelVisualizer / LevelView	Mesh, data textures, materials, hit-testing	Yes
LevelHighlighter	Maps game state onto per-segment visual states	Yes
InputService	Input System wrapper — pointer, click, restart	Yes
CameraProvider	Orthographic fit to the generated board	Yes
GameAssetsProvider	Async config loading	Yes

The generator hands out its result as a read-only graph, so the systems that consume a level — rules, undo, presentation — cannot mutate it: only the factory that builds a graph can change one.

Future improvements

• Drop the Unity dependency from the domain: implement a custom Vector2Int/Vector2 so the generator, rules, and undo compile as plain C#. They are already logic-only — the only thing tying them to the engine is the math types, and removing them would let the whole puzzle layer be tested and reused outside Unity.
• HUD: the outcome currently only reaches the log. Add a result screen (win / dead end) with a restart button, instead of relying on the keyboard shortcut.
• Better input: support hold-to-select, so a path can be traced by dragging across segments rather than clicking each one. This needs a gesture layer in InputService that does not leak into the game loop.
• Larger boards: the grid is capped at 10x10 today. Lifting it needs bucketed hit-testing (currently a linear scan per pointer query) and an O(1) path reversal in the backbite mixing.