22
\$\begingroup\$

Are there frameworks for reasoning about questions such as: Given my quest and level design, is it guaranteed that for any combination of player choices there is no way for the player to lock themselves out of completing the game?

As an example, assume a quest like this:

  • The Player can betray NPC A and receive item b from NPC B as a reward, or
  • The Player can betray NPC B and receive item a from NPC A as a reward.
  • The Player can trade either item a or b for a key. This is the only way to obtain key.
  • Only the key opens a new zone. This is the only way to enter zone.
  • The player can kill NPC A. Upon death, NPC A does not drop item a.

With this setup, the player can lock themselves out of completing the game if they kill NPC A and betray NPC B. In this case, they can neither get item a nor b as a reward, therefore never obtain key, and never enter zone.

Now look at these two additional rules:

  1. If killed, NPC A drops item a.
  2. The only way to kill NPC A is through an item that can only be obtained from zone.

Adding either of these options / constraints ensures that the player can never lock themselves out of completing the game.

If you needed a while to read through these rules, then it means that it is at least a bit difficult to reason about them, although this is only a very small example. For any realistic number of options, constraints, NPCs, items, and quest branches, chances are high that we overlook a potential path in which the player ends up in the most frustrating situation: being unable to complete the game, and potentially finding this out only very late.

How do people reason about such things? I can imagine encoding some useful information into my quest descriptors, items, etc., turning it all into some sort of giant state machine and computationally validating that there are no dead ends. Or I can turn all the options and constraints into Prolog clauses and check for satisfyability. Both seems doable but expensive to build just for one game.

How do studios do this? Are there existing frameworks? Endless QA and hoping for the best? Leaving it to beta testers?

\$\endgroup\$
8
  • \$\begingroup\$ For the specific case of "what if the player kills an important NPC," the easy way out is to flag the NPC as unkillable until every quest connected to them is complete. For example, Skyrim does this with a flag on the Reference Alias. But that obviously does not solve the softlock problem in full generality, because softlocks might not involve an NPC dying. \$\endgroup\$ Commented Apr 28 at 8:27
  • 6
    \$\begingroup\$ Rather than prolog, the traditional answer to this sort of problem in the formal verification community is TLA (lamport.azurewebsites.net/tla/tla.html) which is designed for reasoning about these sort of overlapping 'once A then B' processes. But I'm not aware of any game that has used it. \$\endgroup\$ Commented Apr 28 at 9:46
  • \$\begingroup\$ If you are familar with the king's quest series by Siera games.. Then you know how easy it is for a game to be locked out of victory. \$\endgroup\$ Commented Apr 28 at 14:33
  • 1
    \$\begingroup\$ ‘turning it all into some sort of giant state machine’ You need to do this anyway, it’s called implementing the story logic in the game. If you take the time to just implement the tracking of story progress explicitly as a state machine from the beginning, you can then just do the verification on that directly (and then you also don’t need to worry about ensuring the model you’re using for verification actually matches the implementation in the game). \$\endgroup\$ Commented Apr 28 at 16:44
  • \$\begingroup\$ This seems like the kind of problem where logic programming languages like Prolog would shine - but I'm not sure if it's used in Game Dev or if there are Game Dev specific frameworks that do something like that (e.g., "syncing" your game scripts to prolog for verification), hence leaving a comment rather than an answer. \$\endgroup\$ Commented Apr 28 at 17:28

3 Answers 3

Reset to default
13
\$\begingroup\$

Game dependency graphs are a tool to reason about the problem you've described. A dependency graph is a directed graph representing how objects depend upon each other. In a mathematical context dependency graphs usually use the directed edges to show the "depends on" relationship. For instance \$A ➡ B \$ is read as "A depends on B" meaning B is the key for A. Most every dependency graph I've seen in game development uses the "is needed for" relationship - basically the opposite of the math version.

In a game development context, the graph nodes represent lock and key situations that gate progress through the game. This is another abstraction in that the locks and keys aren't necessarily literal. For example, if a game requires the player to have a double jump ability to access a high ledge, that's still considered a lock and key. The ability (double jump) is the key that unlocks access to an otherwise in accessible area.

Here's an more complex example from The Legend of Zelda: The Twilight Princess:

illustration from paper

The mission / quest dependency graph is on the left side and the right side maps those dependencies onto the game map. The illustration comes from the paper by Dormans & Bakkes that I'll get to later on.

We can use a game's dependency graph to examine the game's quest structure and look for problems. A fork in the graph occurs when multiple 'upstream' nodes depend on the same resource. If that key must be consumed to satisfy an upstream lock then you can easily identify content that will locked out if the player chooses one over the other. If that's undesirable, you can either change the key so that it's not consumed, or make a new key (or possibly alternative) available to the player.

Another thing to look for the dependency graph are cycles. These may represent "chicken and egg" scenarios and in that case you will either need to break cycles or remove them.

Dependency graphs can be also be used to actively generate lock and key type quests. Unexplored (a procedurally generated roguelike) uses generative grammars to essentially make dependency graphs for procedurally generated games. The basic idea is that you can start with a small graph and then replacing nodes with subgraphs. You can think of this in terms of adding side quests. For example if you started with this:

simple graph

You could replace the double jump node with this subgraph:

sub graph

Which yields the following:

more complex graph

The result is a (hopefully) more interesting experience that has guaranteed solutions. Joris Dormans (developer of Unexplored) and Sander Bakkes published a paper exploring this topic called Generating Missions and Spaces for Adaptable Play Experiences. Boris the Brave has some great blog posts covering the same work.

Regarding your question on how do other games deal with this: it depends. Some use models and tools to generate safe quest structures, some validate things manually (and hopefully patch mistakes). Some use things like "plot armor" to protect NPCs that are critical to the quest. Sometimes inventory items get a similar treatment: for example special arrows related to a quest cannot be consumed. A lot of these amount to varying the nature of the locks & / or keys. Dormans discussed different types of locks and keys here:

  • Locks might be conditional, dangerous or uncertain
  • Locks are permanent, reversible, or temporary
  • Locks might be asymmetrical (one way paths)
  • Locks and keys can be safe or unsafe
  • Keys can be single or multi- purpose.
  • Keys can be particular or non-particular
  • Keys might be consumed or persistent
  • Keys might be fixed-in-place

Some solutions are easier to implement but may run the risk of pulling the player out of the intended game experience. For instance, respawning a story critical NPC that died earlier in the game. In a serious game this would be a liability, but in a comedic game, it might be a feature.

\$\endgroup\$
3
  • 2
    \$\begingroup\$ +1, I'm not sure why this answer doesn't have a higher score than the first answer, TBH. \$\endgroup\$ Commented Apr 29 at 17:38
  • \$\begingroup\$ Mostly just timing. I had my answer up early when the question hit the Hot Network Questions feed and got a lot of drive-by views, so folks didn't yet see this answer and weren't casting a vote for which one they thought was better. \$\endgroup\$ Commented Apr 30 at 9:31
  • 1
    \$\begingroup\$ Thanks a lot for all the answers and comments! <3 I marked this one as the "accepted" one, because I found it most applicable in my case, but I also enjoyed the talk from @DMGregory 's answer a lot. \$\endgroup\$ Commented May 16 at 19:04
20
\$\begingroup\$

In a microtalk presented at GDC2016, Emily Short showed a bit of her process for this kind of validation. (Her talk starts about 15 minutes into this video)

She works extensively in interactive fiction, which often has this structure of lots of disconnected pieces of narrative content and player choices, each modifying some local state, making it hard to reason about all of the possible state transitions globally (and whether any deadlock states are reachable).

Emily short standing at a lectern, beside a slide featuring the cover art for Blood & Laurels and a flow chart of narrative scenes with shading / percentages indicating how often a simulated playthrough visited that scene. The caption at the top reads "Flow test: 1000 trial playthroughs dated 2013-12-18-0032

For Blood & Laurels, she describes using an AI agent that would play through the game, making random choices (and triggering any randomization / chaotic interactions within the system itself), and recording which scenes it encounters. Her team could then run thousands of these bot playthroughs to assess how frequently each scene gets reached, visualizing the result as the flow chart shown above.

You can use this to detect places where certain content is unreachable (or excessively difficult to reach) due to overly-restrictive trigger criteria, or cases where a bot gets stuck and can't make forward progress.

By recording the bots' routes along the way, Short and her team could inspect individual traces when something went wrong, to learn the exact reproduction steps so they could isolate and fix the problem.

\$\endgroup\$
0
\$\begingroup\$

Semi-frame-challenge: don't overcomplicate design

The biggest way games avoid this problem is by avoiding intricate quest paths to obtain quest items. Many games give players little to no choice in how quests (particularly main quests) progress. For the games that give players some choice in this regard, it's very, very rare to have multiple layers of choices with complex interactions between those choices.

For choices that exist, you may have:

  • Some quest objective which can be completed in multiple ways, e.g. "obtain item X", which you can do by killing the NPC, trading with them, or stealing from them.

  • "Funnelling" the quest paths so that all paths go through the same point (e.g. go talk to some NPC), before going off in different directions again.

  • Quests progress largely the same, regardless of whether or not you did some optional objective. If you did that objective, it instead changes something later on.

    This allows for fairly intricate quest paths which are relatively simple to design, with little room for things to go wrong (in theory, anyway - in practice, things always go wrong, particularly in unexpected ways).

Another simple solution would be to have one option the player can always do at any point (e.g. kill everyone). This would make it less of an issue to have some unintended dead ends in other quest paths - that may still not be ideal, but at least there'll still be a way to progress.

The main quest will be the thing both developers and testers will pay the most attention to, and will usually avoid making it overly complex to avoid the risk of breaking something crucial. If there's ever a possibility of soft-locking yourself out of a quest, that's more than likely going to be a side-quest, instead of a main quest.

Some games claim that your choices matter, and for some it's more true than others. But in a lot of other games, quest progression is either very linear, or you just have the illusion of choice (e.g. dialogue options which all generate the same response from the NPC you're talking to, although I'm not personally a fan of that).

The other option would be to take some specific quest, and draw decision trees for every choice you have at any point.

 / \ / \ betray A / \ kill A / \ / \ . . get b / \ kill B / \ ... from B / \ kill B / \ / \ / \

Then you can just see which paths don't work.

Naturally there'd be some risk that you missed an option somewhere.

Manually doing this doesn't scale well, but then again, it generally doesn't need to, because quests generally aren't that intricate. They generally aren't even intricate enough to require even this.

If you want something really complex, then your best option might be to check satisfiability or using formal verification, as yourself and a commenter have mentioned. I don't have specific recommendations in that regard.

\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.