Worlds within Worlds: The Hidden Mechanics
A deeper dive into the ASP patterns and implementation techniques that power interactive fiction systems.Photo Credit: Rob Grzywinski
This technical companion explores how Answer Set Programming (ASP) can elegantly model the core mechanics of interactive fiction. While the main document focuses on building a complete game, here we'll examine key ASP implementation patterns and interesting implications that arise when using declarative programming for interactive storytelling.
Interactive Fiction: A Brief Introduction
Interactive fiction (also known as "text adventures") are programs in which players use text commands to control characters and interact with the environment. Popular in the 1970's - 1990's, titles such as Zork, Adventureland, and The Pawn were the first engaging games that many of us played. A sample interaction might be:> GO NORTHFurther along the streetPeople are still pushing and shoving their way from the southern gate towards the town square, just a little further north. You recognise the owner of a fruit and vegetable stall.Helga pauses from sorting potatoes to give you a cheery wave. "Hello, Wilhelm, it's a fine day for trade! Is this young Walter? My, how he's grown. Here's an apple for him -- tell him to mind that scabby part, but the rest's good enough. How's Frau Tell? Give her my best wishes."> INVENTORYYou are carrying:- an apple
- a quiver (being worn)
- three arrows
- a bow
> TALK TO HELGAYou warmly thank Helga for the apple.> GIVE THE APPLE TO WALTER"Thank you, Papa."
Interactive Fiction in ASP
Leaving aside for a moment the translation of constrained natural language into atoms, one can readily imagine that the player may specify actions such as moveΩ/2, inventoryΩ/0, talkΩ/2 and giveΩ/3 that results in fluents such as at_locationΔ/3 being updated. The information (output/1) provided back to the player is defined by a relation between the environment, the current location of their character, and previous actions that the character performed. This is nothing more than a planning problem and is well-understood in ASP.To provide a little context, below are some high-level examples of what the sample interaction from the introduction might look like in ASPoutput(("Thank you, Papa.")) ←
giveΩ(apple, walter, I),
at_locationΔ(apple, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(walter, Location, I) .
Fully defining the action giveΩ/3 ensures that the player is informed of unwanted or impossible actions:output(("You don't have the ", Item, " to give to ", Person)) ←
giveΩ(Item, Person, I),
not at_locationΔ(Item, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(Person, Location, I) .
output((Person, " is not here!")) ←
giveΩ(Item, Person, I),
in_inventoryΔ(Item, I),
at_locationΔ(character, Location1, I),
at_locationΔ(Person, Location2, I),
Location1 != Location2 .
Almost Incremental Solving
The largest difference between what's needed to write Interactive Fiction in ASP and what has been covered so far is how time instants are advanced and how player-provided actions get incorporated into the program for future time instants. In vanilla incremental solving, the programmer defines all of the facts, rules and exit conditions, provides and upper and lower bound for time and lets the solver run. In a typical planning problem, the solver is looking for answer sets that allow the system to proceed from some initial state to some desired final state. If the result is unsatisfiable then that indicates that there is no such plan.Interactive Fiction is different in that at each instant, the player injects new facts into the program and then the solver (re)solves this new program up to the current instant. Based on how the program was written, there may always be a single answer set (e.g. by computing an optimal answer set) or the programmer may choose to allow a random answer set to be presented to the player. The programmer wants to ensure that there is never a result of unsatisfiable since that would leave the player with nothing to do; each action must result in some facts which inform the player of the effects of their action. Some actions are categorized as "informational" (e.g. "look around", "inventory") and neither affect the environment nor increment the time instant. Other actions (e.g. "go north", "talk to helga") change the environment in some way and become part of the knowledge base and cause time to move to the next instant.An Interactive Fiction-specific wrapper around the vanilla ASP solver is used. This wrapper takes input from the player and translates it into player actions. These actions are injected into the existing program at the current time instant and the program is solved. All output/2 is shown to the player. If the player's actions were valid then the time instant is incremented and the resulting non-player actions are appended to the program for use in the next instant. All outputs are discarded. This process is continued until an exit state is reached.Player Input
Players may provide invalid input and the program must provide useful feedback while not advancing to an invalid state. Player inputs are treated separately from actions in order to determine if it is valid. This keeps the logic for actions (and their associated fluents) simple and separates that from the logic that determines validity. It also simplifies testing as player input can be tested separately from actions. The prefix "ρ" for player is used for player actions ("ρΩ") and "Ω" denotes an action.Different Types of Errors
Unlike traditional ASP in which invalid cases are pruned using constraints, the player needs to be informed when they perform an invalid action. An explicit form of "cannot"s are used for player feedback.output((invalid, I), ("You don't have the ", Item, " to give to ", Person)) ←
giveρΩ(Item, Person, I),
not at_locationΔ(Item, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(Person, Location, I) .
Traditionally this rule would be a constraint:⊥ ← giveρΩ(Item, Person, I),
not at_locationΔ(Item, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(Person, Location, I) .
but if a traditional constraint was used then the result would simply be unsatisfied which is not useful to the player.The use of output/2 kills two birds with one stone:- It provides feedback to the player;
- It indicates (via its first argument) whether or not the action was valid ("
valid") or not ("invalid").
This allows other rules to only hold if the player is in a valid state or not. For example, (5) can be enhanced to only hold if no other error has occurred:output((invalid, I), ("You don't have the ", Item, " to give to ", Person)) ←
giveρΩ(Item, Person, I),
not at_locationΔ(Item, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(Person, Location, I),
not output((invalid, _), _) .
With the addition of this condition (not output((invalid, I), _)), other more specific rules could be written that override the default behavior:output((invalid, I), ("You wouldn't want to give the ", Item, " to ", Person, "!")) ←
giveρΩ(gold, Person, I),
not at_locationΔ(gold, inventory, I),
at_locationΔ(character, Location, I),
at_locationΔ(Person, Location, I) .
This rule provides a different (perhaps essential to the plot) message to the player. Without the extra condition in (6) the player would get both "You don't have the gold to give to Joe" and "You wouldn't want to give the gold to Joe!" messages.Traditional constraints are used within Interactive Fiction to ensure that the environment is consistent. Having an item disappear or appear in more than one place is an example of an inconsistency in the environment and should be prevented with a traditional constraint.
Quantum Storytelling: When Possibilities Collapse
Consider this delightful quirk of interactive storytelling — it's Schrödinger's cat all over again, but with trolls! Until observed, your world exists in multiple states simultaneously. Take a wandering troll, for instance. Using choice rules, we can let this troll exist in several possible locations at once. As long as the player hasn't encountered it, the troll inhabits a space of pure possibility. It could be in any of its allowed locations. But the moment the player glimpses it (whether through an explicit look/1 action or by stumbling into its presence), that cloud of possibility collapses into a single, concrete reality. The answer sets narrow to only those where the troll occupies that specific spot!This means that even seemingly "informational" actions can reshape the world. When a player's look/1 action causes the system to choose an answer set, we might need to cement that choice with a new at_locationΔ(troll, L, I) fact. This ensures future actions - even another look around! - maintain this now-established reality, even without advancing time.It's a beautiful demonstration of ASP's power — not just in managing vast search spaces, but in letting us model the very act of discovery itself. One program can spawn countless possible stories, each crystallizing into reality through the simple act of observation.
The Poetry of Directions: When North Meets South
There's something beautifully symmetric about directions, isn't there? Every north implies a south, every east a west. At first, we might explicitly write out these relationships:direction(foyer, south, bar) .
direction(bar, north, foyer) .
But there's a deeper wisdom here — not just about directions, but about symmetry itself. What if we could capture the very essence of "oppositeness"?
The Nature of Opposition
Let's start with the raw truth about directions:opposite_raw(north, south) .
opposite_raw(east, west) .
opposite_raw(up, down) .
Notice we're only stating each pair once. Because here's the core insight: if A is opposite to B, then B must be opposite to A. We can express this fundamental symmetry with a simple rule:opposite(A, B) ← opposite_raw(A, B) .
opposite(B, A) ← opposite_raw(A, B) .
This isn't just about directions anymore — it's about the nature of opposition itself. When two things are truly opposite, the relationship flows both ways, like ripples meeting in a pond.
When Spaces Connect
Now we can express how locations link together:direction(To, Dir2, From) ←
direction(From, Dir1, To),
opposite(Dir1, Dir2) .
With this understanding in place, we only need to state one direction:direction(foyer, south, bar) .
And ASP derives the other: {| direction/3 |
|---|
| bar | north | foyer |
| foyer | south | bar |
}
Beyond Directions: The Symphony of Symmetry
But why stop at directions? This pattern — of recognizing and expressing fundamental symmetries — can illuminate any domain where relationships mirror each other:symmetric(Rel, A, B) ← raw(Rel, A, B) .
symmetric(Rel, B, A) ← raw(Rel, A, B) .
We could even go meta, defining the very nature of different types of relationships:relationship_type(opposite, symmetric).
holds(Rel, B, A) ←
holds(Rel, A, B),
relationship_type(Rel, symmetric).
This is ASP at its most profound — not just solving problems, but revealing the hidden patterns that govern our systems. We've moved from describing paths to expressing the fundamental nature of symmetry itself. And in doing so, we've made our world both simpler and more elegant.Each time we recognize these deeper patterns, our code becomes not just more concise, but more truthful. We're no longer just writing rules — we're discovering the poetry in our programs.
Worlds of Possibility
The beauty of using ASP for interactive fiction isn't just in its elegant handling of game mechanics — it's in how it mirrors the creative process itself. Just as a writer starts with infinite possibilities and gradually shapes them through specific choices, ASP begins with a space of potential stories and lets them crystallize through player interaction.Think about that moment when a player types their first command. They're not just triggering a predetermined response — they're collapsing a wave of possibilities into a specific reality, much like a writer deciding which path their story will take. Each choice builds upon the last, creating a unique narrative thread from the vast tapestry of potential stories encoded in our rules and constraints.This isn't just programming — it's world-building at its most fundamental level. By separating the "what" (our rules and constraints) from the "how" (the solver's exploration of possibilities), we create spaces where stories can emerge organically from the interaction between player and system.The technical patterns we've explored here are really just the beginning. They're invitations to think differently about how stories can be told, how worlds can be built, and how players can participate in shaping their own narratives.So take these building blocks and experiment. Push the boundaries. Let your imagination dance with the logic, and see what new forms of storytelling emerge from the elegant interplay of rules and possibilities.After all, every great story starts with someone asking "What if?"
Appendix
References
- Interactive Fiction
- What is Interactive Fiction
