Player agency in an open world, versus combinatorial explosion

Egamebook DevLog #2

15 min readFeb 19, 2018

An open world game needs to allow players to change the world. Destroy a bridge. Kill the king. Forge an alliance. World-changing actions can come in many varieties, but it’s helpful to talk about quests. Quests tie these actions into meaningful packages — with motivations, characters and stories. Without those elements, the open world can feel like a literal sandbox, where nothing really matters.

This article is about the design decisions I’m making in order for the quests in my next game not to suffer from combinatorial explosion. What do I mean by combinatorial explosion in relation to quests? Here’s the problem in a nutshell:

Player actions (made during quests or separately) need to have consequences to the world. Otherwise, the actions feel pointless.
Some of these consequences can be incremental, like “the village’s wealth increases by 20 coins” or “the wizard’s reputation decreases by 6 points”. But there must also be major consequences like “the forest bridge no longer exists”, “the dwarves are now allies”, or “the player knows about the secret passage”. In spades.
This is especially important for a non-visual medium like Egamebook. Text generally needs broader strokes — the player’s new sword can’t be slightly nicer than the current broadsword, it must be Orcthorn, the bane of the ancient Orc king. The village can’t have a few more people on the streets — it must be suddenly bustling with life. A new combat move can’t just make +3 more points of damage. It must be chopping enemies’ arms.
These consequences combine. Outcomes of previous quests influence the next quest (among other things). Combining incremental consequences can be easy (20 coins + 10 coins => 30 coins), combining major consequences is most definitely not.
This is a major source of pain in development. And a major source of bugs.
As the number of quests increases linearly (e.g. 1 quest a week), the number of combinations of their consequences increases exponentially (e.g. 3 consequence combinations first week, 9 next, 27 after that). That is called a combinatorial explosion.
This can grind a project to a halt when the number of combinations explodes. Suddenly, no one wants to touch anything in fear that they’ll miss some important implication.

An example

To give you a concrete example, let’s say the player has done all these things in the past quests:

Negotiated an alliance with the dwarves.
Burned a bridge in their territory, which stopped an undead army from attacking the elves, but made that army turn around and lay siege to the dwarven fortress for months.
Killed a famous dwarven hero in a duel.
Maneuvered a large and dangerous beast away from a city and to the vicinity of a ford near the dwarves.

Now imagine that the player’s kingdom needs help from the dwarves to defeat yet another terrible danger.

The quest is simple: go to the dwarves and ask for reinforcements. If you were to program such a quest, then you have to deal with things like:

Which is more important for the dwarves? The alliance or the memory of their fallen hero?
How do they feel about the player at this point? Is the alliance with player’s kingdom more important to them than the fact that they had to endure months of siege? How much do they blame the player for that?
If they say yes, how do they march? Will they try to swim in the river? Go a long way around? Try the ford, knowing that there is a monster there? Do they know? Should the player automatically tell them? Should they have a choice to tell them?
If they don’t say yes, which of the reasons not to go should they mention, if any? Can they be persuaded to reconsider (e.g. by killing the monster at the ford, or by giving a legendary weapon to adorn the grave of their fallen hero, or by simply giving them gold)?

Remember: this is just a consequence of four previous quests. An average RPG will have tens, often hundreds of quests.

Note: I’m using the term “quest” for any long-term assignment with a goal. In a tabletop game, that would be one adventure, often (but not always) played in one play session. Save the hostages. Deliver the message. Deal with the rat infestation. Kill the mountain king and so on. So it’s not just side quests. It’s also all the things the player needs to do to achieve the main goal of the game.

So how do you mitigate this problem? Here’s my current thinking, summarized in rules. Some of the rules were already implemented in Insignificant Little Vermin. The rest I’m implementing now. I’m going to talk about each rule in detail below.

Rules

Put logic in the consequence, not the predicate.
Limit effects spacially and temporally.
If there are more effects of the same kind, pick the strongest one and ignore the rest.
One type of effect per scene.
Quests should be explicitly about one effect.
Build a framework for the most usual effects.
Hold quests until they’re fun.

1) Put logic in the consequence, not the predicate

This is an implementation detail, but widely applicable, so I’m putting it first. You can safely skip this if you’re not in the business of programming games, and you’re here for the game design solution.

Let’s say we want the following sequence of events:

Player visits an evil aristocrat’s soirée.
Player conspires with the butler.
Later that week, player sneaks into the aristocrat’s house through a window that the butler intentionally left open, and murders the aristocrat.

It’s natural for us humans to put logic in the predicate. When the player conspires with the butler, we naturally put some kind of flag on the butler that will later make him open the window. That is what I call putting logic in the predicate.

The problem here is that many things can happen between the soirée and the fatal night. Something can make the butler change his mind. The aristocrat can learn of the plan and set up a trap. The tree branch providing access to the window can fall. The town can get infested by deadly flying creatures that love flying into houses and feed on people.

So now you’d better make sure that all these different circumstances know about the opens_window flag on the butler, and change it accordingly. Bugs abound.

Instead, what you want to do is to move the logic to the point in time when it matters — to the consequence. Instead of setting a state to be used later, you’re “remembering” when the time comes. Here’s how it works:

When the player successfully conspires with the butler, all you do is make a record of this. This record could be as simple as an identifier of the event (butler_conspires) and the in-world timestamp. It goes into a repository we'll call history.
When the fatal night comes and we need to see whether the butler has opened the window, just query the history.

In the easiest case, you’re just asking whether there exists a butler_conspires record in the past. If so, then the window is open.

As things get more complicated, you just add more logic based on history. If there is an aristocrat_learns_about_conspiracy record in the past, then the window is not open. If there is a flying_monster_infestation_starts record and no flying_monster_infestation_ends record after it, then the window is not open.

This does two things:

You’re limiting the number of special flags and general book-keeping in the game. Most things just go into the history.
You have all the logic about a consequence in one place — right next to it. You don’t need to go hunting for all the different if-else statements in other parts of your code.

As a bonus, you get to know why exactly the butler isn’t opening the window. history can tell you when the deciding event happened, and possibly also who is responsible (if you save perpetrator ids with your event records).

It also gives you an easy option for effects to have a limited lifespan. Maybe the fact that you removed all gardening equipment 6 months ago shouldn’t affect the state of the garden today.

What’s more, you can now easily have effects that don’t come into effect immediately. When the player orders assassination of a prince and then immediately goes to the palace, maybe the royal family shouldn’t be already mourning. Maybe there shouldn’t be black flags all over the kingdom. Give the assassin a day or two.

Technical note: Yes, the history approach has worse performance characteristics than using simple flags. But with a little care, it’s not nearly as bad as you might think. For events where only the latest instance matters (which is most of them), access can be O(1) through a hash map. Size-wise, an average event can be 3 bytes (1 byte for event identifier, 1 byte for a timestamp, 1 byte for an id of the perpetrator).

2) Limit effects spacially and temporally

This one is easy. Avoid having things that affect huge areas of the world, forever. You probably will have some of those, but in general, be conservative.

For example, when player disposes of bandits who set up an operation near a local road, don’t try to simulate major ripple effects throughout the kingdom. Make the two nearest villages happier. Let the player be celebrated there for a while. Maybe unlock some weapons in the nearest blacksmith. That’s more than enough for the player to feel that their deed has consequences.

Note: You can still have large scale effects if you really want to. Set it up so that when the player defeats a set number of criminals, then the kingdom as a whole gets significantly safer (and the king can even summon the player to thank him for his work). Just don’t try to affect the kingdom from each small quest independently.

3) If there are more effects of the same kind, pick the strongest one and ignore the rest

This one might be controversial, especially for the more simulation-minded people like me — but I think it’s worth following nevertheless.

Let’s say the player needs to obtain a magic robe from a stronghold. He or she decides to use stealth, and to make that easier, here’s the plan:

Make sure the guards get drunk by delivering a barrel of wine at the barracks.
Pay some brigands to fake an attack at the stronghold, creating a diversion.

Illustration by Mary Hallock Foote, 1877.

Now, how do you approach situations like these, as a developer? The two obvious ways are:

Simulate. Both drunkenness-of-guards-on-duty and a faked-assault are things that are simulated automatically by the game. Just tell the game to make the guards drunk, and that there is now a faked assault by a certain number of brigands, and it will figure out what to do.

This is ideal if you can have it. But let’s face it, most game simulation won’t be rich enough to handle all the things that you (or your writers) throw at them. How many fake assaults do you want to have in your game? How many will the player tolerate before it gets repetitive? And, if you get in the habit of implementing a simulation for things that you only use once or twice during the game, will you ever finish the game?
Combine manually. Prepare for the eventuality that the guards are both drunk and under faked attack. Create new writing for that. “Hey, Capt’n. Capt’n. Wake up. There’s’n assault. Hic! On the south wall.” Make sure the player has extra easy time sneaking into the stronghold in this scenario.

This is less work than the simulation above, but not by much. You’ll have to write special code for basically all the possible combinations of effects. Again: combinatorial explosion.

Instead, just pick the strongest influence and ignore the rest. In our example, it’s safe to say that the faked assault is a stronger influence on the player’s ability to sneak in than the drunkenness of the guards. The watchmen are scrambling to defend the wall, getting weapons from racks, shouting orders, etc. The fact that they’re drunk is secondary.

When applied well, the player won’t notice, and you as a developer have saved yourself a lot of work.

The drawback is that the player might notice, and be let down. But my hypothesis is that this drawback is more than offset by the fact that you give the player more interesting options, and these actions lead to much more dramatic consequences.

So how do you judge the relative strength of two effects? Most of the time, one effect is just intrinsically stronger than the other one. Assault is stronger than drunkenness. Destroyed bridge is stronger than a tree fallen over the road. Killing a family member is stronger than insulting one. But sometimes, space and time play a role. Recent deeds, even minor ones, can override old ones. Let’s say that the player helped a blacksmith save the smithy from a fire. This was years ago but the deed is still remembered. Now the player comes back to the village and asks the blacksmith for a small favor, like borrowing a horse. But just before the player asks for the horse, he or she gravely insults the blacksmith. Insulting has a weaker inherent effect than saving someone’s livelihood but I think you’ll agree that it would be weird if the blacksmith obliged at that point. In this case, the more recent deed takes precedence over the more substantial but older one.

Last note: you can’t use this method everywhere. Some effects must be combined, and there’s no way around it. For example, if the player magically puts the whole garrison to sleep and orders the fake attack, then you have to write what happens next. You definitely can’t have the sleeping guards scramble to fend off an attack, and you probably can’t have the brigands just kind of ignore your assignment.

4) One type of effect per scene

First off, some definition. A scene in a game like Egamebook is a single step of the quest. It’s usually bound to a single place. For example, the quest of retrieving a magic sword from a wizard’s tower can have the following scenes:

Sneaking through the wasteland towards the tower.
Combat with two of the wizard’s minions on a patrol.
Entering the tower in disguise as a minion.
Finding the right room with the artefact.
Breaking into the chest containing the sword.
Combat with minions on the staircase.
Stealing a horse.
Chase through the wasteland.

Different players will have different scenes, according to their choices (another player might choose not to use stealth and just approach the tower head on, for example).

Now, how does a programmer make sure that this sequence is pleasantly influenced by the player’s past choices? We already know that it’s better to put logic into the given scene, querying history, instead of trying to "influence forward" by setting brittle state. We also know to try and pick only the strongest influence of a kind, and ignore the rest.

Yet, it’s still very possible (and very human) to go overboard. A single deed in the past could influence many scenes. For example, if player interrogates a former lieutenant of the wizard before even setting out to the tower, that could influence:

how easy it will be to cross the wasteland undetected (the former lieutenant knows the best path)
whether it will be possible to persuade the minions not to fight (the minions are more loyal to the former lieutenant than to the wizard)
how easy it will be to find the room (the former lieutenant draws a plan for the player)
how easy it will be to open the chest (the former lieutenant gives the player the key)

And so on. It’s not hard to come up with other ways a single interrogation could influence this quest at every step of the way. This, again, leads to a combinatorial explosion, because you will want to give the player at least a few options to prepare for the quest, and if all of these options influence most of the scenes, then the scenes will have to deal with a lot of effects. The player both interrogates the former lieutenant and the carpenter who built the chest. So the player can open the chest and also knows that it’s trapped. Now you have to deal with the combination of the two.

Then you come up with the brilliant idea that the minion robes have little jingle bells on them, and so can hinder the player’s stealth. So a player wearing those robes will have a harder time staying silent. Now you have to deal with a bunch of new combinations of consequences.

Instead, for each scene, decide on only one type of influence. Don’t make the chest trapped. Just have it locked and allow the player to break it, lock-pick it, or use a key. Don’t have the robes have the jingle bells, or make them irrelevant to the scene. The only kind of influence allowed for the chest scene is how the chest can be opened.

Other scenes will have other types of influences. The “finding the right room” scene can be about stealth. The player will hide better if he or she has the map of the place. On the other hand, the stupid jingle bells will make it harder to hide effectively.

Some kind of external distraction could make the player’s job easier when escaping on horseback. Don’t jam the distraction into another scene just because you can.

By partitioning types of influences into dedicated scenes, you avoid another source of the combinatorial explosion.

5) Player actions should be explicitly about one effect

This is a companion to the previous rule. When you give the player a chance to influence the future, make it explicit that the influence will be limited to one effect.

For example, when you say that blowing the Horn of Clay will bring reinforcements and also will make the player’s troops fight harder, then you’re making your own life a lot harder.

Instead, make the Horn of Clay “only” bring in reinforcements. Trust me, that’s more meaningful consequence than what players usually get from interacting with the game world. They will not be sad that the horn also doesn’t make the troops fight harder.

6) Build a framework for the most usual types of effects

Even when you’ve diligently used all the rules above, you will start seeing effects that are very similar across quests, and that don’t feel repetitive despite heavy use.

That’s when you should start thinking of simulating them.

For example, maybe a lot of the actions the player can do will give him or her a temporary companion. Start an escort quest? Here’s the person you’re escorting. Save a princess from the dragon’s lair? She joins you as a powerful warrior. Ask a mayor for help? Here’s a member of the town guard.

You could write custom code for every relevant scene that will check if you have a companion, and act accordingly. But given how many scenes will change because of that, that’s a lot of work.

Instead, just write the generic code for having party members. That means the code for characters following the player, code for chit-chat, updated code for combat… in other words, a lot of new code. But still much better than doing things manually.

Depending on the game you’re building, other such simulation-worthy aspects could be:

status (e.g. knighthood opens areas normally inaccessible to peasants, lowers prices, and adds dialog options)
magic powers (e.g. necromancy allows raising and commanding any dead body)
deterrence (e.g. a terrifying look will make enemies run from the battle earlier, and will make forceful interrogation more effective)
surprise (e.g. an ambush will have profound effects on the first few moments of combat)
anatomy (e.g. chopping off an arm will prevent its owner from using it)

7) Hold quests until they’re fun

This last rule doesn’t directly prevent combinatorial explosion but it’s somewhat related to the idea of previous actions influencing future quests.

Let’s say you have a good old dragon slaying quest. One of the scenes of this quest is actually finding the dragon’s lair in the mountains. By default, the player needs to basically search every valley and every peak of the mountain range. Not fun. But the player can also learn about the position of the lair from an NPC of one of the other quests, and there’s also a way to piece the location together from a book in a nearby city.

You might be thinking: great! Three ways to find the lair, each very different.

But then your players start exploring the game and almost all of them end up finding the lair by walking all over the mountains. Why? Because they stumble upon the quest before they talked to the NPC or found about the book. Even though the search for the lair is potentially interesting, in reality — for most players — it’s not. You have opened the quest to them before you had the chance to make it interesting for them.

Instead, wait with introducing the quest (or even spawning the dragon) until at least one other option is available.

This can make the path of the player a little more linear (you’re basically requiring the player to first do X or Y before offering Z) but I think that’s a fair price to pay for having amazing quests full of interesting choices that stem from the player’s past deeds.

Conclusion

I hope this was an interesting read. I’m glad it’s out of my system. If nothing else, this will be a great way to introduce newcomer writers to Egamebook.

Questions, ideas? Please reach out.