Proving a quest is completable before anyone plays it

There is a file in the Open Quest Format repo called unreachable-step.oqf that parses without complaint and is valid OQF, but one of its three steps can never happen. Here it is, stripped down to the cells that matter:

greet             start step
forgotten_errand  unlock: step.greet and step.greet == "failed"
leave             unlock: step.greet    outcome: finished

In a condition, a bare step.greet means that greet is done. So the errand only unlocks when greet is done and failed at the same time, which can never be the case. The problem with a step like this is that nobody will find it by playing. A playtester never sees the step, so there is nothing for them to report, and the quest still finishes normally through leave. The errand just stays in the file forever without anyone knowing it is dead.

The validator does catch it, and it reports both that the errand leads nowhere and that no path reaches it:

$ oqf validate unreachable-step.oqf
unreachable-step.oqf: warning dead-end: step "forgotten_errand" has no outcome, no rewards and nothing depends on it (quest unreachable_step, step forgotten_errand)
unreachable-step.oqf: warning unreachable-step: no path from a start step reaches "forgotten_errand" (quest unreachable_step, step forgotten_errand)
0 errors, 2 warnings

It can only do that because of a decision I made before writing any code. In OQF, conditions are data, and I deliberately kept the language they are written in very limited so that a program can reason about every condition in a quest.

The condition language: eleven operators and six namespaces

Under the hood, a condition is stored as a JSON Logic tree, but only a whitelisted subset of JSON Logic is accepted. The whole whitelist lives in model.ts and has eleven entries: and, or, !, ==, !=, <, <=, >, >=, in and var. If a condition uses anything else, the validator reports it as an error. That means there are no function calls, no arithmetic, no assignment and no loops, and in can only test whether a value is in a list literal. What I wanted was for every condition to be something the validator can evaluate completely on its own, and each of those missing features would have made that impossible.

A condition reads its variables from six namespaces: flag, count, step, outcome, quest and var. The first five are owned by the runtime, which keeps track of every flag, every step state and every step counter, so the validator knows in advance what values they can take. var.* is different because it belongs to the game: season, time of day, or whatever else the engine decides to resolve. The whole validator relies on that split, since it can reason about the five runtime namespaces completely but has to treat anything under var as unknown.

Authors never have to write the tree by hand. The compact format lets them write a condition as an infix string, like count.catch_rare >= 5 or step.steal == "done" or step.trade == "done", and a hand-written precedence climbing parser turns that string into the tree. The parser has no dependencies, and neither does the evaluator. JSON Logic libraries exist in most languages and the tree stays compatible with them, but I still wrote a strict evaluator for the TypeScript side. That way @oqf/core depends on nothing, and == means strict equality instead of the loose equality JSON Logic uses.

The reason for keeping the language this small is that a validator has no way to tell whether a Lua snippet will ever return true. As soon as a single condition in a quest is a script, the question “can this quest be finished” no longer has an answer, neither for the validator nor for a person reading the file. Restricting conditions to comparisons over known variables is what keeps that question answerable.

How the reachability search works

Reachability is computed in graph.ts as a fixpoint. Start steps, meaning steps flagged s or steps with no unlock at all, are reachable from the beginning. The validator then works in rounds, and in each round it looks at every other step and asks whether any assignment of the runtime-owned variables makes that step’s unlock true. If one does, the step is added to the reachable set, which gives the next round more states to work with, and the search stops when a round adds nothing new.

Trying “any assignment” sounds expensive, but because the language is so limited, the set of values worth trying turns out to be small enough to enumerate. A step.x read for a step that is already known to be reachable can take any of its six states: locked, available, active, done, failed or skipped. For a step that is not reachable yet, the state is pinned to locked and its counter to zero, since nothing could have moved it. Flags and outcomes are either true or false. Numbers are probed at 0, at every literal that appears in the condition, and at every literal plus one, which lands on both sides of any comparison the language can express. Every combination then goes through the real evaluator, the same function the runtime calls during play, so the analysis cannot drift away from what the game will actually do.

In the errand fixture, greet is reachable, so the validator tries all six states for step.greet. None of them is both done and failed, which means no assignment satisfies the unlock, and the validator can say the errand is unreachable because it has checked every case.

There is a cap on this search. Past 20,000 combinations, the validator gives up and treats the condition as satisfiable. I chose that direction on purpose, because I want the validator to call a step unreachable only when it has really checked every case. If it raised false alarms, authors would learn to ignore the warning, and I think that would cost more than occasionally missing a real problem.

Flags follow the same principle, because the game is allowed to set any flag it likes, so the validator never treats a step as unreachable because of a flag on its own. If you replace the impossible half of the errand’s unlock with flag.errand_posted, the unreachable-step warning goes away. The dead-end warning stays, though, because the errand still leads nowhere: it has no outcome, no rewards, and nothing depends on it.

The other checks that matter for completability

The validator knows 25 finding codes in total, and each one is a stable kebab-case string so that a tool can switch on the code directly. One of them, lore-node-effect, is reserved for dialogue, and the check that emits it is on the way. For deciding whether a quest can be completed, the codes that matter are cycle-without-repeat, outcome-with-dependents, dead-end, unreachable-step, no-ending-reachable and ending-needs-var. The other codes cover duplicate ids, references to steps, quests, rewards or outcomes that don’t exist, and malformed conditions.

Cycles are found with Tarjan’s algorithm over the step dependency graph. A loop is allowed as long as every step in it is marked repeat, because that is how an author says a step is meant to come around again. The ferry fixture has a loop between two steps that are not marked, so the validator reports both of them:

cycle-without-repeat.oqf: error cycle-without-repeat: step "ferry_out" can reach itself through "ferry_out", "ferry_back" and is not marked repeat (quest cycle_without_repeat, step ferry_out)
cycle-without-repeat.oqf: error cycle-without-repeat: step "ferry_back" can reach itself through "ferry_out", "ferry_back" and is not marked repeat (quest cycle_without_repeat, step ferry_back)
2 errors, 0 warnings

A single mistake often produces several findings at once, and I find that cascade more useful than it first looks. In duplicate-step-id.oqf, the second greet unlocks on step.greet and also carries the ending. That one copy-paste slip produces three errors: the duplicate id, a step that depends on itself, and an ending that something depends on. Each of those errors describes a real problem in the file, so reading them together tells you exactly what the slip broke.

The broken fixtures also record where the tooling does not behave the way their comments expect. There are ten files in packages/examples/quests/broken/, and each one opens with a comment naming the error it should produce. Six of them never reach the validator, because the compact parser throws first and the CLI reports a parse-error. For three of those six, the comment names a validator check instead, and rather than quietly editing those fixtures to match, the CLI test suite records each mismatch so that it stays visible. My favourite is unknown-objective-kind.oqf. Its step says gather fish.rare 5, and since gather is not an objective kind, the parser reads the cell as a condition and reports unknown variable namespace "gather". That error is correct, but it is a little confusing if you don’t know how the parser reads a cell.

What the validator cannot prove: game variables

The guarantee gets weaker as soon as a quest reads var.*, and the validator tells you when that happens. Here is a quest I wrote for this post to show it. It is not in the repo:

dig_bait    start step              complete: collect bait 3
wait_dark   unlock: step.dig_bait   complete: var.time.isNight
land_eel    unlock: step.wait_dark  complete: collect eel    outcome: landed

night-eel.oqf: warning ending-needs-var: every path to an outcome of "night_eel" passes through a var.* read, so completability cannot be proven (quest night_eel)
0 errors, 1 warnings

To produce that warning, the validator runs reachability a second time. In this pass it pins every var.* to null, which is what a game that promises nothing would supply, and it requires each step along the way to be completable as well as unlockable. If no ending survives that second pass, you get the warning. In the night eel quest the only way to land_eel goes through wait_dark, which completes on var.time.isNight, so the ending depends entirely on the game. If you add a second route, a lantern step that also unlocks from dig_bait, and make land_eel unlock on step.wait_dark or step.lantern, the warning goes away and the validator prints 0 errors, 0 warnings. The reference quest in the repo validates clean for the same reason, because its trade route reaches an ending without touching a game variable.

Two checks are being extended while I work on this part. Today condition-constant fires only on a literal true or false, and a version that catches any condition that is always true or always false given the owned namespaces is incoming. The second pass is also getting a more precise message. As a test, I gave a step complete: count.mend_rod >= 3 and count.mend_rod < 2, which can never hold and does not read any game variable at all. The validator already flags that quest, but it does so as ending-needs-var, which points at the wrong cause, so a fix is incoming that points the message at the impossible condition itself.

Logic the condition language cannot express

Leaving out arithmetic means you cannot write something like gold >= level * 10. Timers and time-of-day conditions are incoming in v2, but until then conditions have no notion of a clock. There are also no random rolls, no inventory lookups and no way to say “three eels during a storm since Tuesday”, and plenty of quest logic in real games looks exactly like that.

The way OQF handles this is to leave that logic in the engine, where it already lives, and have the quest count what the engine reports. Objectives are events with some syntax sugar on top: collect eel 3 counts item.collected events for that item, and event <name> [n] counts any event by name. So if the game knows when a storm catch happens, it can emit storm.eel_landed, and the step says event storm.eel_landed 3. For logic that doesn’t fit a counter, there is custom. The engine-hooks template has a step whose complete cell is custom cozycoast.ritual moon candles. The runtime never completes a step like that on its own. Instead, the engine reports it by emitting quest.<questId>.step.<stepId>.custom with { done: true }.

The validator treats an objective as something the world can report, and it does not try to prove that the storm will ever come. In practice, the logic you would have written as a script still exists, but it lives in engine code the validator cannot see, while the quest graph around it stays checkable. The cost of that is easy to state: if the game never emits storm.eel_landed, that step waits forever and the validator has nothing to say about it.

Diffing two versions of a quest

Diffing two versions of a quest is on the way, and what 0.1.0 ships today is the groundwork for it. Every condition has one canonical spelling (lowercase keywords, single spaces, and the fewest parentheses that reproduce the tree), and every serializer reproduces the fixture files byte for byte. Together, those two properties mean that changing an unlock shows up in git as one changed cell on one line. On top of that, oqf graph prints the step graph as a mermaid flowchart that you can paste into a pull request. A dedicated oqf diff is incoming, and it will join a command list that today is validate, convert, import, graph, schema, extract and inject. Because both versions of a quest are plain data, a diff that tells you “this change made forgotten_errand unreachable” can start by running the validator on each version and comparing the findings.

Incoming. Several pieces mentioned in this post are on the way: a dedicated oqf diff, the wider condition-constant check and the more precise ending-needs-var message. Timers are planned for v2, and Cozy Coast is lined up as the first shipping game built on OQF.

All the broken fixtures are in the repo if you want to run the validator on them and watch them fail.