Using Petri Nets to Prove Our Game Makes Sense

For our first game, Steve’s Job, our studio developed a puzzle adventure game set in a split-apart reality. In point-and-click fashion, players must talk to characters and obtain items to solve puzzles.

The world of Steve’s Job¹ is split into three alternate realities (hate when that happens), and players are meant to freely run around all of them. So, when designing the puzzles and overall game flow, we wanted to make sure players always have multiple things to do at any given point in time – and that they can never get stuck and softlock themselves.

To help design this non-linear game flow, we used a mathematical model known as a Petri net aaaaand I’d like to show you how we did that!

Note: The interactive examples might be a bit finicky on mobile or small screens – soz! Note: The example Petri nets are rendered with JS, so make sure that’s available and enabled!

Now, Petri nets are perfect for modeling the type of conditions that came up, stuff along the lines of “When the player has item x, talking to character y will give them item z in exchange. Item x can be obtained if the player has item a and … and talks to…”

We can design Petri nets for these conditions and then analyze them to mathematically prove that there’s no way for players to soft-lock themselves.

What even are Petri Nets?    

Alrightyo, let’s look at a very simple Petri net. Most examples in this post are interactive, so you can click the blue box labeled t1 below and watch the circle move from p1 to p2! Good job!

A Petri net is made up from four elements, places, transitions, tokens and arcs between places and transitions. The image above, which is actually a complete Petri net, shows all four.

• A place, shown as a circle, can hold tokens. In the above example, the leftmost place is initialized with a single token, while the other one starts off empty. Each place can hold a non-negative number of tokens. In game design a place might represent a certain inventory item: n tokens in a place represent the player possessing n copies of the item.
• Arcs, shown as arrows, always connect a place to a transition, or a transition to a place. No two elements of the same type are ever connected. Tokens will flow along these arcs.
• The rectangular transitions are placed in between places. With regard to arc directions, in our example, p1 is an input place of t, while p2 is an output place.
• A transition can be fired, if, and only if, there’s at least one token in each of the input places. In that case, we’ll refer to the transition as enabled.
• When a transition fires, a single token is removed at each of the input places, and one token is created at each of the output places.

That’s pretty much it! In reality, the arcs can also be weighted², but I’ll gloss over that since it won’t be needed for what I’ll be showing – hence we’ll be only looking at so-called ordinary Petri nets where all weights are \(1\).

More advanced stuff    

Let’s look at some more simple Nets. Feel free to play around with them!

Creating and destroying tokens

We can also completely create and destroy tokens.

A source of tokens is a transition without any input places – such a transition is always enabled and will always place a token into each of its outputs.

A sink is a transition without any outputs – it’ll end up destroying its input tokens.

Multiple inputs and outputs

Check the network below.

Here, t1 has two inputs (p1 and p2) and three outputs (p3 through p5).

It can only fire, if there’s tokens in all of its inputs. Upon firing, it will place a token into each output.

A Simple Game Logic Example    

Okay, let’s model some game logic. In Steve’s Job, the player can talk to a cult of goose girls – developer self-insert let’s goooo – who will give them a goose. There’s a machine that turns this goose into grease. It costs one coin to operate and can only ever be used once.

The following Petri net models this interaction:

1. Initial State: The player starts off with a single coin in their inventory. In the Petri net, this is modeled as a token in the Has Coin place. A token in Machine Unused indicates that the machine has not yet been used, and a token in Goose Storage indicates that the goose is still with the cult.

2. Take Goose: The player joins the mysterious cult and, as a membership reward, is given a goose. This is modeled with the Take Goose transition. It requires that there’s a token in the Goose Storage place, which is the case in the current state.

3. Goose to Grease: The player walks up to a “Geese-to-Grease” machine. In exchange for a coin and the goose (i.e. by taking a token from the two respective places), the machine commits some goose cruelty and then happily dispenses a tub of grease. The transition also takes a token from Machine Unused, ensuring the player can never use the machine again, even if they obtain another goose and coin.

Analysis    

As mentioned before, the really neat thing about Petri nets is the fact they can be analyzed for certain properties, the most interesting of which is deadlock.

Most Petri net tools should have analysis tools. I used Workcraft, so let’s just check our Petri net for deadlocks:

Aaaaand it’s dead. We’ve already seen that the modeled objective can be completed, but of course, once that’s happened the player is “stuck” in the sense that they’ve finished.

To make our Petri net ready for analysis, we’ll add a Reset_Game transition. It can only be fired when the objective is complete (i.e. the player has the grease), and it restores the Petri net to the initial state.

Let’s check again:

It’s deadlock-free! :confetti: This means we’ve proven that this interaction within the game is logically sound!

Analysis Part 2: Reachability    

Any Petri net can be transformed into a different graph, called the reachability graph (which itself really is just a representation of a state machine).

In this graph, the vertices are all possible states of the Petri net and the edges are transitions.

The above example has three states, i.e. three possible assignments of tokens to places.

We can also rephrase the deadlock-free property: A Petri net is deadlock-free if its reachability graph is strongly connected, i.e. any state can be reached from any other state.

The Big Petri Net for Steve’s Job    

Behold, the big network for the full game! Feel free to play around. The places have tooltips you can hover over that give some more context.

With this Petri net in our hands we can finally prove the game flow actually makes sense – by adding a reset transition and verifying deadlock-freeness.

Neat! And finally, here’s the big reachability graph:

The initial game state is aaaaall the way on the left and as the player progresses through the game, they move towards the right on the reachability graph. The final state, the game’s win condition, is all the way on the right and reached after triggering the Fix_Switch transition – repairing the light switch repairs reality, roll credits etc.

The reachability graph has 82 nodes, meaning that as far as progression is concerned, Steve’s Job has 82 possible game states³.

Let’s do some Game Theory    

There’s a neat connection here to the more formal approaches to game studies and game theory! Briefly put, a game can be seen as a state machine. Whenever the player takes an action, the rules of the game dictate into which state the game moves next.

In game-theory-lingo, the reachability graph is the game tree.

The player will try to reach some “good” or desirable state – here that’s the single win state. Taking the appropriate choices to influence the game’s state is where the gameplay happens.

The shape of the game tree also tells us about the nature of a game. Take, for example this one, for tic-tac-toe:

I’ve not listed all possible states here – even taking into account symmetries from rotating and mirroring the tic-tac-toe board, there’s 765 different game states. Games with such broad game trees are referred to as games of emergence.

Chess is an even better example with a ginormous game tree – after all we don’t have enough atoms in the universe to enumerate all possible chess games.

Game of emergence generally have a set of simple and general rules. This makes such games “easy to learn,” but because there’s so many possibilities they’re also “hard to master.” There’s never a clear path to victory⁴ and strategies are requires to (attempt to) navigate the game tree.

Adventure games like Steve’s Job on the other hand fall into the category of games of progression. The rules are more specific (“You need to talk to the cult, and then they give you a goose”) and the game tree is somewhat linear – certainly much less broad than that of even a simple emergent game like tic-tac-toe.

For further reading, check out chapter 3 of Jesper Juul’s Half-Real and unit 2 of Rules of Play by Salen and Zimmerman.

Savegames    

In the actual implementation of Steve’s Job, the Petri net’s places map to inventory items. Some, such as the goose, are visible to the player. For the other places, like our Goose Storage place, we’ve used invisible items.

After talking to the goose cult, we remove the invisible Goose Storage item from the player’s inventory – this makes sure they can’t get a second goose from the cult⁵.

Now, take a look at the data contained in the savegame – keeping in mind that the savegame really just is a representation of the game state.

[System.Serializable]
public class SaveGame {
    public List<int> inventory = new List<int>();
    public string scene;
    public Vector3 position;
}

Of course, we want the player to respawn in the same position and in the same scene. But as far as progression is concerned, we really just need to store the player’s inventory!

Closing Remarks    

I’ve actually found one paper about modelling games with Petri nets. The game the authors apply this to is more of an emergent game, and as such instead of whole-game progression, they’ve modeled complex individual game systems.

In the real world, the closest I’ve seen is the game flow diagram in the Game Design Document for Sam & Max: Hit the Road (just google search online for “sam and max gdd pdf”). It’s more about how the game’s screens are connected, but I’m sure that in conjunction with the list of puzzles given in the document, one could also create a Petri net for that game.

The Steve’s Job Petri net was originally designed by fellow goose girl Fionn, with whom I brainstormed the game flow on paper.

I’ve focused on the design of the puzzles, but that doesn’t mean our implementation is necessarily deadlock-free – there may still be bugs.

In theory, we could’ve implemented a representation of the Petri net in our game and have that serve as the back-bone for which interactions are possible, and to which outcomes they lead, at any given point. Doing something like that would probably be pretty interesting – I was considering doing something along those lines for my Bachelor’s thesis before real-time rendering and Vulkan stuff got the better of me :D

Of course, feel free to check out Steve’s Job, available for free on itch.io.

Also, if there’s anything you’d like me to know, reach out to me ^w^

Anyways, thanks for reading :3

🐾 Footnotes: