How Netwalk Generates Solvable Boards: From Tree to Puzzle
A fair connection puzzle should not ask the player to trust luck. The generator must know a solved arrangement before it scrambles the tiles. Netwalk follows that solution-first principle: construct a connected network, store the direction of every pipe, and only then rotate the visible pieces. The player is reversing a transformation of a known solution rather than searching an arbitrary collection of pipes.
This guide follows the actual concepts used by the browser game, including its grid graph, randomized Prim-style growth, directional bitmasks, mode-specific adjustments, and flood-fill completion check. It also separates three claims that are often confused: a solution exists, the solution is unique, and the puzzle is enjoyable. A generator can guarantee the first without automatically guaranteeing the other two.
1. Model the board as a graph
Begin with a rectangular grid. Each cell is a vertex, and each shared horizontal or vertical border is a possible graph edge. On a 5 by 5 board there are 25 vertices and 40 possible neighbor edges. A Netwalk pipe crossing a shared border means the corresponding graph edge was selected.
The representation must be reciprocal. If cell A connects east to cell B, cell B must connect west to A. The generator therefore writes both halves of an edge in the same operation. This simple invariant prevents dangling one-way pipes in the solved state and gives later validation a precise rule: every selected direction must have its opposite bit set in the adjacent cell.
2. Encode four directions in four bits
The game stores a tile as a four-bit mask. North is 1, east is 2, south is 4, and west is 8. Combining directions uses bitwise OR. A north-east elbow is 3, a vertical straight is 5, an east-south-west T is 14, and a four-way cross is 15. An empty cell is 0.
This encoding makes rotation compact. Moving every active bit one position clockwise turns north into east, east into south, south into west, and west back into north. It also makes neighbor checks cheap: test the current tile's east bit and the next tile's west bit. The visible pipe artwork is merely a rendering of the mask; the mask remains the authoritative puzzle state.
3. Grow a spanning tree from one visited tile
The base generator chooses a starting vertex, marks it visited, and collects frontier edges from it to unvisited neighbors. It repeatedly selects one frontier edge at random. If the destination is still unvisited, it adds a reciprocal pipe across that border, marks the destination visited, and adds the new cell's frontier edges. Edges that lead to already visited cells are discarded.
When the frontier is empty, every cell has been visited. Each newly visited cell entered through exactly one accepted edge, so a board with V cells received V minus 1 tree edges. The result is connected and contains no cycle. Those two properties define a spanning tree. Random selection changes its shape: one seed may create long corridors while another creates dense branching near the center.
Calling this "Prim-style" is more exact than claiming the game solves a weighted optimization problem. Classical Prim's algorithm chooses the cheapest frontier edge to build a minimum spanning tree. Here the grid edges do not represent costs; randomized frontier selection is used because varied connected topologies make varied puzzles.
4. Choose the server and respect the play mode
In bounded and torus modes, the browser game places the server at the grid center before growing the network. This gives the solved network a stable visual anchor. In classic mode the starting location may be selected by the generator. A torus changes neighbor calculation: stepping beyond one side wraps to the opposite side, so a western edge can be reciprocal with a tile on the far right.
Mode rules affect more than presentation. Bounded and Torus preserve endpoints, straights, corners, T-junctions and crosses from the generated tree. Classic can add extra reciprocal connections. Any validation routine must use the same neighbor rules as generation. Treating a torus as a bounded rectangle would falsely label legitimate wraparound pipes as off-board errors.
5. Add complexity without losing reciprocity
A pure spanning tree gives an existence guarantee, but its many endpoints may make some boards too transparent. Classic mode can inspect adjacent pairs and add an extra reciprocal edge with a probability based on board size. An added edge joins two vertices that were already reachable through the tree, creating a cycle. Connectivity is preserved because adding an edge cannot disconnect the graph.
The probability decreases as boards grow. Small boards have fewer cells from which complexity can emerge, while a large tree already contains many junctions and interactions. This is a tuning choice, not a mathematical law. A robust designer measures resulting tile distributions, solve paths, and player behavior rather than assuming a single percentage produces the same difficulty at every size.
6. Preserve the solved state before scrambling
After topology construction, the connection-mask matrix is the solution. The game keeps that matrix and stores a separate rotation offset for each tile. The current visible mask is computed by rotating the solution mask zero, one, two, or three quarter-turns. This separation is valuable: generation logic never has to reverse-engineer the scrambled board, undo can restore a prior offset, and rendering always derives from one consistent model.
Random scrambling needs two small safeguards. First, the system should avoid an accidentally solved starting board, especially on tiny grids. Second, rotationally symmetric pieces need careful interpretation. A four-way cross is unchanged by rotation, and a straight has only two visually distinct states even though the offset has four numeric values. Counting offsets alone can exaggerate the real number of choices.
7. Understand what solvable does not mean
Because the generator stores a connected solution before scrambling, returning every tile to its recorded orientation yields a connected board. That proves at least one solution exists. It does not prove uniqueness. Extra classic edges and symmetric shapes can allow multiple orientations that keep every tile reachable. The win checker requires full connectivity and matching openings in every mode, plus no cycles in Bounded and Torus. It accepts any arrangement meeting these conditions, not only the original orientation.
Solvability also does not guarantee a satisfying deduction path. A board may be technically solvable but require an early guess, contain too many immediately forced boundary tiles, or offer little visible progress until the final moves. Content quality for a puzzle generator comes from evaluating the player experience after the mathematical floor has been met.
8. Validate topology before presenting the puzzle
The regression tests check structure directly; this is test-time validation, not a separate runtime validator. For every cell and active direction, locate the appropriate neighbor using the current mode. Reject an off-board opening in bounded mode. Reject a connection whose neighbor lacks the opposite bit. Then run a traversal from the server across reciprocal edges and count reached cells. If the count differs from the number of intended network cells, the solution is disconnected.
For a strict tree mode, also count undirected edges and verify E equals V minus 1. For a mode that permits cycles, skip that equality and instead ensure E is at least V minus 1. Optional quality checks can count endpoints, straights, elbows, junctions, and crosses; reject pathological distributions; and enforce a minimum scramble distance measured in visible quarter-turns.
9. Use flood fill for live connectivity
During play, the game derives current masks from solution masks plus rotations, then starts a graph traversal at the server. It follows an edge only when both tiles expose reciprocal openings. Every reached tile can be rendered with the connected color. Reaching every cell is necessary but not sufficient: the checker also rejects unmatched openings, and Bounded and Torus reject cycles.
This traversal is linear in the size of the graph: each cell and neighbor relation is examined only a small number of times. Even a large browser board is modest by algorithmic standards. Running the check after every rotation gives immediate feedback without needing a server request, database, or delayed validation step.
10. Test the generator as a property, not one example
A screenshot proves only that one board looked plausible. Generator tests should run many sizes, modes, and seeds and assert invariants for every result. Essential properties include reciprocal edges, valid boundaries, server inclusion, full reachability, legal masks, and successful restoration of the stored solution. Seeded tests should also compare two independent generations and demand identical outputs.
Edge cases deserve dedicated cases: the minimum grid, a long narrow custom board if supported, wraparound neighbors, a server near unusual topology, and random sequences that generate many frontier duplicates. A regression test should preserve any seed that once exposed a failure. Deterministic seeds turn a rare random bug into a permanent, reproducible fixture.
11. A practical generation checklist
- Create a grid graph with mode-correct neighbors.
- Select the server and initialize a seeded or unseeded random source.
- Grow a reciprocal spanning tree until every cell is visited.
- Apply only mode-safe topology adjustments.
- Validate reciprocity, boundaries, and server reachability.
- Store the solved mask matrix separately from rotations.
- Scramble through the same random source when reproducibility matters.
- Reject accidental solved starts and poor tile distributions.
- Use flood fill after each move to render progress and detect completion.
This pipeline is small enough to understand end to end, which is one reason Netwalk works well as both a game and a programming example. The spanning tree supplies the guarantee, reciprocal masks make state testable, and scrambling converts a known network into a visual reasoning problem. Read how deterministic Daily seeds build on this pipeline, or compare the abstract model with the graph theory guide.