How do you create a nonlinear game that the player can always win?

I thought a lot about this question — and initially, I intended to ask this on gamedev.stackexchange.com — but due to its rather theoretical aspects, I think it might be more appropriate to address a rather mathematical spectrum of readers.

Imagine you had to design a dungeon in a game that comprises many puzzles that are mutually dependent from one another. If you lack an example, just think back to the times you've played Zelda or any other video game of this sort:

Rules:

The player may freely wander around the dungeon; some rooms are locked, some aren't. The main goal is to solve puzzles in rooms $\{R_0, ..., R_n\}$ to either achieve keys that help the player enter a locked room or in order to achieve an item that may allow the player to solve a puzzle in some room $R_k$ that, before, wasn't solvable without the ability of the item.

Every key works with every door. Once a key is used, the door is unlocked forever and the player loses the key. In the end, the player needs to reach a specific room $R_b$ where he can fight the dungeon's end boss in order to finish the dungeon. The dungeon is solvable iff the player:

• can reach rooms $R_0$ to $R_n$, regardless of the order chosen
• has collected all items $I_0$ to $I_m$ that he needs to fight the dungeon's end boss once the player enters $R_b$

The goal:

Your goal is to design the dungeon in a way that guarantees maximum nonlinearity, i.e., the player should, at any point of time in the dungeon, be able to try to solve as many puzzles as possible and thus be able to explore as many regions as possible without harming the solvability of the dungeon.

The problem:

For example, imagine the player has two keys, but then utilizes both of them in order to get through two consecutive doors. The player then finds himself in a puzzle room whose solution requires some item $I_\alpha$ that he should actually have gotten using the two keys that he now does not possess anymore. Unfortunately, the player finds himself in a gridlock — the dungeon is now unsolvable.

Can you guarantee that your dungeon design is free of gridlocks?

Disclaimer

I am not asking for any implementation, code or any of the like. This is a strictly theoretical question that I want to consider from a strictly mathematical point of view. Any suggestions that exceed these limitations (by providing any material such as the previously mentioned) are — albeit highly appreciated — explicitly not asked for.

This might not be exactly what you're looking for, but I think the safest (and probably easiest) way to accomplish this might be to design the whole dungeon to be (at least mostly) linear at first, then adding in some choices for the player, so it doesn't seem as linear.

Say you come up with some plan: Visiting the rooms in the order 1,4,5,3,2 will allow the player to succeed, so make sure the necessary items are placed to allow the player to do that. Then you could conceivably move some of the necessary items around - maybe they would find the item that allows them to open room 3 in the first room as well, but they wouldn't know if they should head to room 4 or 3 first, for a little non-linearity.

Alternatively, if the dungeon is fairly large, you could break it up into a few underlying linear pieces: Let's say it's got 4 groups of 5 rooms, call the groups $A,B,C$, and $D$. From $A$, you could complete either $B$ or $C$ first, while both $B$ and $C$ would need to be explored in order to get everything to work on the $D$ group of rooms. And from within $A$, perhaps you could start exploring the $C$ group, but couldn't finish until you'd exhausted $A$, just to layer in some additional complexity.

A mathematical object that would help seems fairly tough. I imagine either partially ordered sets or directed graphs could help you map out the dependencies. For directed graphs, the issue that seems difficult is that you've got two different things to consider - rooms and items. Either way, if the dungeon is complicated enough, then either of the above might grow too complicated to be of much help. I think partially ordered sets would be the most promising, and I can draw an example of how I picture it helping, if you're interested.

I wish I knew of a great mathematical tool could help you, so my most promising idea seems to be chunking the dungeon up into semi-linear groups. That way you can focus on a collection of smaller problems individually and make sure the dependencies all work out, and add in some complexity safely.

The maximum non-linearity is achieved by allowing the player to tackle all of the puzzles in any order. This means that all of the puzzles can be accessed without using any keys, and that the keys must all be used in a linear corridor which separates the area containing the puzzles from $R_b$.

However, I suspect this isn't what you're looking for, so you may need to refine the question.

Your notion of "nonlinearity" seems to have nothing to do with the mathematical definition of "nonlinear".

Anyway, a game of this sort can be modeled as a directed graph whose nodes are the "states" (complete specifications of all possible situations that a player can be in at any point of the game). An arc goes from any state to any state that can be the next one the player reaches. You want to ensure that a "success" state is always reachable from any other state. The trouble with this formulation is that the number of states can be enormous.

Feel free to -1 this as it is clearly not what you are asking for but, once upon a (distant) time, I used to amuse myself by writing non-linear text-based adventure games (I know… tragic). However, I suspect that there is no easy answer to your question other than mapping the nodes and possible routes - you may find a partial answer in something like Dijkstra's algorithm

Practically however and more of a cludge than a formula but I think the approach is still valid. Either avoid the lock-state by mapping outcomes of an action (bit like the computer ‘player’ in a strategy game) and blocking actions that lead to stalemate (downside is that that reduces the non-linearity) or, detect stalemates and provide eagles (unashamed Tolkien reference there – if the plot traps the heroes in an inescapable corner, solve it by sending in the giant eagles). The latter was my choice: Each location has dependencies (artefacts) and each dependency has an availability flag. If there are no available artefacts or if those that are available do not match the dependencies of any locked location then implement Operation Eagle… It could be a new character or puzzle in your example.

I suspect that there is a lot of ‘eagle’ code out there in mainstream games.