TL;DR: A generated map needs a route that the actual player can complete with the abilities, keys, resources, and world changes available along the way. Ordinary geometric connectivity proves only a small part of that claim. Validate progression as a state-transition problem, retain a witness route, and replay important witnesses through the real movement system. Treat visual variety and playable variety as separate acceptance questions.
Consider a fictional exploration game, Lantern Vault, whose generator produces a handsome underground station. Every room connects to another room. A pathfinder finds a line from the entrance to the exit. The developer presses play, reaches a locked gate, and discovers that the required key lies beyond it. The level is connected as a drawing and impossible as a game.
This is a useful failure because it exposes the question a generator must answer. Can a point travel across the map? Can a character of a particular size travel? Can a character with a particular inventory finish the objective? Can a human discover the necessary actions without knowing the generator's internal plan? Each question adds information that the previous model may omit.
The examples below are original design exercises, not measurements from a commercial game. They use small graphs so the assumptions remain visible. The article concerns progression and traversal; it does not attempt to evaluate random loot distributions or prescribe a particular visual style. Its intended reader is a developer deciding what evidence a generated level must carry before players receive it.
The first map has six rooms and one dishonest edge
Lantern Vault begins with six named rooms: Entry, Pump, Gallery, Workshop, Bridge, and Exit. Ordinary corridors connect Entry to Pump, Pump to Gallery, Gallery to Workshop, Workshop to Bridge, and Bridge to Exit. A second corridor connects Pump directly to Bridge. On an undirected room graph, the destination is plainly reachable.
Now label the Pump-to-Bridge corridor with a locked gate. Put the gate's brass key in Workshop. The longer path through Gallery and Workshop remains available, so this arrangement is solvable. The gate serves as a shortcut after the player obtains the key. It changes the shape of return travel without blocking the first journey.
Move the key into Exit and remove the Workshop-to-Bridge corridor. The same broad drawing still has an apparent route through the gate, but every feasible route to the key requires passing the gate first. A connectivity test that treats the locked corridor as an ordinary edge will approve the level. The test has answered the wrong question correctly.
The repair is not simply to forbid locks. A lock is a valuable design device when its dependency is intentional. The generator must represent that dependency and check that the prerequisite can be obtained before the restricted transition is needed. This turns a decorative room network into a progression model with consequences.
Godot's navigation overview distinguishes graph-based and navigation-mesh approaches. Those tools can support movement queries, but a developer still supplies the meaning of connections and restrictions. A navigation link says that a connection exists for pathfinding; it does not automatically implement the character action or prove that the game's inventory permits it.
Add inventory to the location
Represent a search state as a room plus the relevant inventory. Entry without the brass key is a different state from Entry with the brass key. When the player enters Workshop and collects the key, the state changes even though the room has not. When the player reaches the locked corridor, the transition checks the inventory rather than assuming that all drawn passages are traversable.
For the six-room example with one permanent binary key, there are at most twelve room-and-key combinations before accounting for other conditions. This is a deliberately small bound: six possible rooms multiplied by two key states. Some combinations are unreachable, but listing the possibilities makes the extra information concrete.
A search from Entry without the key can then produce a witness: enter Pump, enter Gallery, enter Workshop, acquire the key, return through Gallery to Pump, unlock the shortcut, cross Bridge, and reach Exit. The witness is useful beyond a yes-or-no result. A designer can inspect whether the required backtracking is interesting, whether the shortcut appears at the right moment, and whether the action sequence matches the intended fiction.
The witness should identify actions as well as locations. “Workshop to Pump” hides two corridor traversals. “Gate opened” hides whether the key was consumed. A clear sequence makes it possible to replay the reasoning and diagnose a failure when the generated scene behaves differently from the abstract graph.
The state model does not need every inventory item. A decorative collectible that never changes reachability can remain outside this particular search. The choice is based on causal relevance: include information that can alter the legality or outcome of a transition. Adding irrelevant detail increases cost without strengthening the specific guarantee.
A consumable key breaks the easy solution
Change the brass key into a single-use charge. The station now contains two gates that accept the same charge. One gate protects an optional treasure room, and the other protects the exit. A search that records only whether the player has ever found a key can incorrectly assume both gates are available. A correct model must track remaining charges and persistent gate state.
There are two distinct design promises available. The first says that at least one winning action sequence exists. The second says that ordinary permitted choices cannot leave the player permanently unable to finish. The first is existential reachability; the second is a stronger protection against softlocks. Lantern Vault must decide which promise its genre and audience expect.
If spending the only charge on optional treasure is allowed, the level may be intentionally risky. But the consequence should be communicated and recoverable according to the game's design, rather than appearing as an accidental dead end after an hour of exploration. A resettable puzzle and a long campaign with irreversible inventory changes have different tolerances.
A generator can enforce the stronger promise by reserving an exit resource, providing an alternate route, making the optional gate refundable, or checking that every reachable relevant state retains a path to completion. These are design choices with different effects on tension. A validator should report which promise it checked instead of collapsing them into a single “solvable” flag.
The example also shows why a witness alone is insufficient for universal safety. One successful route does not establish that every allowed choice is safe. Testing must match the quantifier in the promise. This distinction prevents a team from presenting a narrow search result as proof of a much broader player experience.
One-way passages change the meaning of a return trip
A drop into the Pump room may be easy to enter and impossible to climb back out of. Drawing the passage as an undirected edge silently grants the player an ability the movement system does not provide. Directed edges describe this asymmetry directly: Entry can lead to Pump without Pump leading to Entry.
Lantern Vault adds a ladder switch in Gallery that restores the return route. The search state now includes whether the ladder is deployed. Before activation, the passage is one-way. After activation, a reverse transition becomes legal. The feature creates satisfying world change if the player can understand it; it creates a softlock if the generator strands the necessary switch on the inaccessible side.
Godot's documented navigation links can be one-way or bidirectional, illustrating that direction is an explicit property rather than a visual inference. The game still needs to implement the climb, drop, or teleport that the link represents. A pathfinder can recommend a transition that the character controller cannot execute if the two systems disagree about its meaning.
The design review therefore asks for a movement contract for every unusual edge. A jump needs a launch region, a landing region, and the abilities assumed. A ladder needs a usable interaction point. A door needs an opening state and clearance. A portal needs a destination that remains valid after the relevant world change.
Return travel receives its own test when the objective requires it. Reaching the artifact is not sufficient if the player must bring it back to the entrance. The goal condition should include possession of the artifact at the return location. Reusing an outbound-only route test would ignore half the mission.
Geometry can invalidate a correct room graph
Suppose the abstract search succeeds, but a decorative pipe narrows the Workshop doorway. A point-sized path crosses the opening, while the player's collision shape cannot. The room graph remains logically correct because it has no representation of clearance. The generated scene has violated the assumptions under which that graph was validated.
The team can handle this by constraining placement around reserved traversal volumes and by checking the realized geometry after decoration. Reserved space is a generation rule; a post-generation traversal check is evidence that the rule actually held. Both are useful because a later art change can alter collision geometry without changing the room graph.
Different actors may require different checks. A crouching player, a carried object, and a large companion can have different clearance requirements. If the mission requires escorting the companion through the exit, validating only the player route misses the actual objective. The relevant actor configuration belongs in the level's validation record.
A navigation mesh also reflects a model of traversable space. It may omit dynamic obstacles or depend on a particular agent radius. It does not by itself establish that a scripted jump, moving platform, or interaction prompt works. The strongest practical evidence combines abstract progression checks with targeted execution through the real controller.
Lantern Vault replays the witness in a test mode that records failures by transition: approach point unreachable, interaction unavailable, jump unsuccessful, landing obstructed, or goal condition unmet. These categories help the generator team repair the appropriate layer instead of treating every failure as a generic pathfinding problem.
A route can exist and still be unfair to discover
The validator finds a route through a nearly invisible switch behind an unmarked pillar. A test agent with direct access to the graph succeeds immediately. A human player searches for twenty minutes and gives up. Logical solvability has not established readable design.
Lantern Vault therefore keeps a separate discovery review. It asks what the player can observe before each required action: a sightline, a sound, a recurring symbol, a map annotation, or an explicit objective. These cues can be subtle, but their existence should be intentional. The review does not require every puzzle to explain itself; it requires the designers to understand the information being offered.
A useful artifact is an information trace beside the action witness. At the gate, the player sees a brass socket. In Gallery, a mural connects that symbol to Workshop. In Workshop, the key's shape matches the socket. The route's logic and the route's clues now form two inspectable sequences. A missing clue can be discussed without confusing it with a missing corridor.
The same distinction applies to difficulty. A jump may be physically possible only with a near-perfect input sequence. Whether that is acceptable depends on the level's intended challenge and the player's expected abilities. A binary reachability test should not be relabeled as a difficulty measurement. The team needs separate evidence about timing tolerance, visibility, and recovery cost.
Human playtesting remains necessary for these questions. Automation can make the test population more useful by filtering impossible levels first, but it cannot replace every judgment about comprehension or pleasure. A generator that reliably produces valid geometry has completed an engineering task; it still owes the game a worthwhile experience.
Preserve the failure as a reproducible object
A player reports an impossible level and supplies a seed. The team reruns that seed after an update and receives a different station. The report is not necessarily mistaken. A seed determines a sequence within a particular random generator and sequence of calls; changing the generation algorithm or inserting additional draws can change the result.
Godot's random-number documentation describes seed and state control, including separate generator instances. Lantern Vault uses that distinction to isolate layout randomness from cosmetic randomness. Adding a new wall decoration should not accidentally consume values from the progression generator and rearrange every gate.
The bug report retains the generator version, content version, seed, configuration, relevant random-stream states, and a compact description of the realized level. For severe failures, saving the actual generated artifact can be more reliable than expecting future code to reproduce old behavior. The storage choice depends on the game's scale and privacy constraints, but “seed only” is not automatically sufficient.
The team also saves the failed assertion and the partial search frontier. If no exit state was reachable, which locked transitions blocked progress? If geometry replay failed, which action and collision configuration caused it? These details turn a mysterious world into a bounded debugging case.
A repaired generator should be checked against the saved failure and a broader sample. Passing the old seed demonstrates that one defect was addressed under the new configuration. It does not establish that the repair preserved variety or avoided creating another family of impossible layouts. Regression evidence and distribution evidence answer different questions.
Reject, repair, or generate by construction
Lantern Vault has three options when a candidate fails validation. It can discard the candidate and try another seed, repair the candidate, or redesign generation so the required structure is built in from the start. None is universally best, and their costs are different.
Rejection is simple when failures are rare and generation is cheap. If only one candidate in five passes, however, the accepted distribution may differ sharply from the proposed one. Certain room types or key placements may disappear because they are disproportionately rejected. A visually diverse proposal generator can therefore yield repetitive playable output.
Repair preserves more of a candidate but can damage its design. Adding a corridor around every locked gate may make all puzzles trivial. Moving a key to the entrance may remove the intended exploration. Repairs need their own objectives and limits; otherwise “make solvable” becomes an algorithm for erasing the interesting constraint.
Construction starts with a valid progression spine and adds optional structure around it. This can make the core guarantee easier to maintain, but it risks recognizable layouts if the spine is too rigid. The design challenge is to vary the meaningful dependencies while retaining a proof that the prerequisites remain available.
The team compares these approaches using more than pass rate. It records generation time, rejection reasons, route length, required backtracking, optional branch count, and the frequency of major progression patterns. These are descriptive measurements, not a universal fun score. They help identify whether a technical solution is quietly narrowing the game's design vocabulary.
Bound the search without disguising uncertainty
As the number of relevant world flags grows, the state space can expand rapidly. Ten independent binary flags allow up to one thousand twenty-four combinations before location and consumable counts are considered. Many combinations may be unreachable, but the worst-case growth explains why a naive exhaustive search can become expensive.
A search that reaches its time or memory limit has not proved that the level is impossible. It has failed to establish the desired result within its budget. Lantern Vault records this outcome separately from a completed search that found no valid goal. Conflating the two would make performance problems look like design defects and could hide incomplete validation.
State reduction can help when justified. If two inventory configurations permit exactly the same future transitions for this objective, they may be equivalent for the search. If possessing more of a nonharmful resource can never reduce available actions, dominance reasoning may discard weaker states. Those arguments depend on game rules; cursed items or weight limits can invalidate an apparently obvious simplification.
The validator's output therefore names its model version and assumptions. A change to carrying capacity, door behavior, or resource consumption can require a new validation run even if the visual level is unchanged. The proof belongs to the combination of level and rules, not to a screenshot.
This discipline is especially helpful during content updates. Designers can see which new mechanic enlarges the state model and which merely changes presentation. The cost of a mechanic becomes visible before it reaches a large procedural content library.
The shortest route can be the wrong witness
A pathfinder that minimizes distance may choose a hazardous shortcut that is technically possible but inappropriate for the level's intended route. Lantern Vault distinguishes a feasibility witness from a recommended design route. The former demonstrates that the goal can be reached; the latter expresses the experience the designers expect most players to follow.
Suppose the short route crosses four damaging steam vents while the long route passes through a safe maintenance corridor. If the starting health permits only three vent crossings, the short geometric route is infeasible unless the model includes a way to avoid damage or obtain healing. Assigning a larger numerical cost to the vents does not, by itself, enforce a hard health constraint. Resource feasibility and route preference are different concepts.
The team writes health consumption into the state model only for levels where it is part of the progression guarantee. It avoids pretending that a simplified fixed damage estimate captures every combat outcome. If enemy encounters introduce substantial player-dependent uncertainty, the validator can establish the structural route while a separate encounter review assesses whether the available resources are reasonable.
The same separation helps with optional objectives. A level can offer a quick exit and a longer route that collects every artifact. If the game advertises complete collection as possible in one run, the goal state must include those artifacts. If collecting one excludes another by design, the interface should communicate that choice instead of letting a completion counter imply an unattainable outcome.
For each witness, Lantern Vault records what was optimized, what was constrained, and what was ignored. That small explanation prevents a shortest-path result from becoming an accidental claim about safety, difficulty, or completion. It also helps a designer compare two valid layouts without reducing their differences to a single distance value.
The artifact that reaches the player
A release candidate for Lantern Vault carries a generated scene, an identified rule set, a successful progression witness, geometry checks for the required actor, and a record of any intentionally risky choices. The game does not expose this bundle as technical clutter to players. It uses the evidence to decide whether the level is eligible to appear.
A representative sample then receives human review for clarity, pacing, challenge, and variety. The sample is stratified by meaningful generator features so rare combinations receive attention. Reviewing only the easiest or most common layouts would give a flattering but incomplete picture of the system's behavior.
The final design promise is precise: the required objective has a feasible route under the stated starting conditions, and the implementation has checked the transitions that make that route possible. Stronger promises about avoiding softlocks or supporting every optional choice are added only when the validation actually covers them.
The station can now remain surprising without asking the player to discover the generator's mistakes. Its secret passages, locked shortcuts, and one-way drops become deliberate parts of play because the developer has separated the existence of a route, the execution of that route, and the player's opportunity to understand it.