Multiagent Narrative Experience Management as Story Graph Pruning

In interactive narratives, experience management is used to control the world and the nonplayer characters (NPCs) a player interacts with, encouraging particular types of stories or discouraging others. The space of all stories in a narrative can be understood as a story graph, with story states as nodes and actions in the story as directed edges. In this article, we present experience management as a graph pruning problem. Starting with the full story graph, edges representing NPC actions may be pruned until there is at most one action per NPC per state. With the full graph available, the choice of what to prune may consider all possible futures, and we can ensure that undesirable stories are not reachable. By never pruning player actions, we ensure the player may make any choice and still be accommodated in the story. When this method was used to manage the story of an adventure game, players found our technique generally produced higher agency and more-believable NPC behaviors than a control. Finally, we discuss scaling the results of this method for practical use.