Storytelling With A Star
In one of my past lives, and one of my alternate futures, I was an AI programmer. On BioShock 2 and The Bureau: XCOM Declassified I made various splicers and aliens do what they should do. It was all state machines and behaviors, but what I really got excited about wasn’t in those games — it was a technique called “Goal-Oriented Action Planning”, or GOAP. Here’s an explanation of this technique. It’s a planning system, one that gets AI to build a coherent plan for their upcoming actions based on the world state.
I think GOAP is really neat on its own, but the thing that really blew my mind was that it took an existing AI technique — the pathfinding algorithm A*, usually used for navigating 2d or 3d spaces — and applied it to a metaphorical space, the possibility space of AI actions. It reimagined the connections between actions as a graph of nodes that can then be navigated, stringing them together to come up with a complete plan. Brilliant!
Ever since I’ve learned about this, I’ve been envisioning new things as spaces that can be navigated. And since my interest these days is in narrative games, I came up with a few ways to use A* to help tell stories.
First: Generating Believable Worlds
The first one is a pretty standard use of GOAP, with a twist. If we envision a population of NPCs, with their own desires and goals, we can use GOAP to plan a set of actions for that NPC to take, on a high level. For example, Bertha, a big cuddly bear in a Stardew Valley-style game, wants to open a bakery. She needs to secure a location, then gather ingredients, then clean out the old stuff in the location, then tell everyone in town about her new business. (This is very high level for most AI systems, and one can imagine each of these goals being broken down into sub-goals, and those broken down, etc, until we reach the level of granularity needed for implementing this.)
Easy enough! Now, though, let’s procedurally replace one of the actions along this step, with, instead, a request for the player to carry out that task for Bertha. So depending on the task replaced, she might say “Oh, I’ve taken over the old feed store, but I need flour, honey, and butter in order to bake my pastries! Can you find those items for me?” Or perhaps “I’m all ready to sell my cakes, but I need you to tell everyone the bakery is open!”
What’s the benefit of doing this with GOAP instead of just hand-writing quests? Well, if generally NPCs are living their own lives and you can convey to the player that they are following believable and understandable goals (not always easy), it becomes easy for the player to see the NPC’s motivation behind this, as well as the eventual results of their actions. In addition, this has the benefits procedurality always does (hopefully): the chance to vary the player experience and even surprise the player with the outcomes.
Most conversations in games are already a graph of nodes, usually directed and branching. It’s easy, then, to imagine pathfinding through that graph of topics to build a coherent yet flexible conversation, with new nodes opening and closing based on player input, but always arriving at a planned destination (perhaps one of several possible destinations) — the critical narrative or gameplay information the player is supposed to glean from the interaction. This could be a way to make a conversation with an NPC feel natural — as the player focuses on various topics, the conversation flows there and presents only logical follow-ups to the current topic, while still presenting the player with what they need to know, and winding up the conversation at the desired end-point. This could also be used effectively to change NPC moods during the conversation — at one point perhaps the player has dug such a hole there’s no getting out of it with a friendship intact. Obviously, however, the challenge here is writing the content that supports an undirected wander through this grove! As Bruno Dias puts it, like most procedural generation, this is an approach that will get you 200% of the content for only 400% of the work.
And last, I think this technique could be used as a method to string together storylets in a way that leads to exciting possible paths through a collection of storylets to assemble an entire storyline. The benefit here is throwing together a collection of storylets with various gating and connections and rather than hand-authoring a path through them, letting the system connect the possible in surprising ways, and allowing easy additions of new storylets to the pool. Creating new paths through the story would be as simple as adding new storylet sets with new and existing connections and watching them hook up with the previously-discovered paths through the content. The challenges here would be tuning this content and the weighting heuristics to produce varied paths through the storylet pool — since A* is designed to find efficient paths, it will always take the same route unless something changes about the available nodes and connections! Here again environmental, game-state, and mood cues could be used as weighting heuristics, or perhaps other, cleverer ideas
The Proof is in the Pudding Which I Have Not Yet Had Time To Cook
The best practice for describing new techniques for any kind of game is to point at the shipped, successful game that you have made using these techniques. Next best is to have some cool prototypes and proof-of-concept work that show off your ideas to their greatest potential. Far down the list is a brief Medium article sketching out what might be cool about this stuff. But, given the realities of keeping a roof over my head through commercial game development, I haven’t had time to explore much about these ideas (the first one is a planned inclusion in a game that has a pitch prototype, but the quest system itself is not yet implemented). Between contract work, building prototypes for publisher pitches, and side projects that have grown to dollar-meal-deal projects, I don’t currently have any of these as more than ideas in a notebook. But now I have thrown open that notebook, both as a way to prod myself to build these in some form, and in order to let other people stab at these things if they’re interesting. Please let me know if you build something along these lines, if it works or if it fails, what the problems are, and anything else!