Generating a Storyline Procedurally
Published
I did some research on named element recognition in a previous article, in which I also mentioned my interest in procedurally generating stories. I talked a bit about the Hero’s Journey pattern which supposedly drives most myths and a good chunk of Hollywood writing as a very convenient and effective pattern but this pattern obviously isn’t enough to generate a convincing story as the described sections are too broad and not actionable as is.
Indeed, there is a need to implement a more restrictive approach. I’m a big fan of the Wheel of Time books and with the tv show coming out, I was reminded of a singular fact: Robert Jordan, the author, mentioned that when he began writing it he knew how he wanted it to begin and how it would end so he wrote the first chapter and the final chapter of the cycle at the very beginning of his work. Now, this is a 14 books long series (excluding the New Spring prequel) or 19 days audiobook and the very start and the very end where the two very first things written by the author.
Why is this interesting? This illustrates a very important property in storytelling: while the initial and final state of the story are up to the author (and additional anchor points, or “cool scenes” as I like to call them), there are restraints imposed on the author from the fact that the flow of the story must be consistent, logical. A given event would have consequences for the story further down the line (if a character dies, he won’t reappear later except if the plot accomodates for it), but we can also reverse this: a given scene can have conditions.
Let’s say we think of an emotional scene where the character’s best friend dies. This scene requires some preparation:
- The hero’s friend must have been introduced in the story earlier. Else, it would make no sense whatsoever.
- Events must have shown that the characters have a bound for the death to be meaningful. The death event therefore requires previous scene showing friendship between the friend and the hero, or some kind of character building.
With these elements considered, we’ll approach the problem by creating an algorithm that takes an initial state and a terminal state as inputs and outputs a skeleton for a story. We’d also like to have the possibility to specify required anchor points for the story, to be able to steer in specific directions. To do this, we’ll be working with Prolog as it fits our needs, and is also a great opportunity to expand our toolbox since Prolog has proven its worth in the field of Natural Language Processing and Procedural Generation.
So, why Prolog?
Prolog is a logic programming language, which is a completely different beast compared to other languages I’m used to (Python, C#, Rust…).
Prolog is focused on defining facts and relations between them. Once these are defined, a user is then able to perform “queries” and Prolog will try to resolve it, such that all facts and relations contained in the query are true.
Here’s a quick example:
% Define facts. These can be whatever we want, so we'll describe a simple useful situation: a love triangle with additional information on parents
%% facts of the same type must be declared in succession, except if "?- style_check(-discontiguous)." is included at the top of the file
parent(lucas, bob).
parent(fred, alice).
parent(john, thomas).
loves(bob, alice).
loves(alice, thomas).
% now we'll define a simple query, lover parent, which gets us the parent of the person who loves a given target
lover_parent(PARENT, LOVES) :-
parent(PARENT, X),
loves(X, LOVES).
% now we can execute the query 3 ways. Either we can specify only the parent or loves, or we can specify both inputs. Prolog will try to resolve queries so that all elements are true.
% the '?-' signifies that we are using a prolog CLI, or that the given instruction is to be executed when the file is loaded/imported.
% now, we'll try to get the parent of the one who loves alice. In this case this should be lucas
?- lover_parent(P, alice).
P = lucas
% the previous query was correct and we got lucas as an answer, but we can also provide the parent instead of the loves argument
% let's see who is the target of the affection of fred's child. Alice is fred's child, and alice loves thomas, so the answer should be thomas
?- lover_parent(fred, L).
L = thomas
% finally, is thomas the one that the child of fred loves?
?- lover_parent(fred, thomas).
true.
As you can see, Prolog allows us to perform queries on known data in a relatively straightforward way. Prolog works by checking described clauses and performing backtracking and values substitution, which seems quite fitting when we consider our objective as described in the previous section.
So why Prolog?
- The language itself lends itself well to our problem. While other languages could fit the bill they might be too rigid but, most of all, logic programming with backtracking is non-trivial to implement and to use. Prolog comes with great features out of the box and is a proven tool for NLP (see IBM’s Watson).
- Backtracking and clause solving involves a lot of recursion. Languages usually have some level of security included to avoid both infinite recursion and too much resource usage. Prolog stacks have a very small memory footprint and can perform much deeper recursions than what is possible in some other languages. For example, python has a default stack depth limit of 1000, while Prolog goes to a few million.
Storytelling as Pathfinding
In this article, we’ll implement our story as a directed acyclic graph, i.e. a sequence of nodes with edges which do not create a loop.
This implementation is more restrictive and less powerful than what I envision in the future, but it will make for a nice starting point for our algorithm and help us get better acquainted with prolog. As explained before, Prolog relies on facts and relations between facts to solve queries. A collection of such facts and rules is called a knowledge base. So, here’s what we’ll do: we’ll think of a simple story pattern and implement it in Prolog.
So what story should we go with? Well, let’s say there is a monster on the prowl in the vicinity of a town, and we want our hero to be the one to defeat it. So, what sequence of event would bring about such a result? Well considering we are dealing with monsters and I talked about the Wheel of Time, let’s imagine we’re dealing with a Fantasy-like, medieval world. In this case, it would be expected for our hero to be a peacekeeping person (such as a knight) or an adventurer. But how did our hero get this status? Let’s set a few facts in our knowledge base to illustrate.
?- style_check(-discontiguous).
% Knighthood is usually a noble role, while adventurer is open to all kind of backgrounds, so let's start by defining the background of our hero
% we'll call these facts "events" since all the others can be classified as events, but these 2 are exceptions. Disregard this detail, it is of little importance in our implementation and only serves to mark all possible events in our database but there is no practical purpose
% So our hero is either a noble or a commoner
event(hero_noble).
event(hero_commoner).
% and can either become a knight or an adventurer depending on his background
event(become_adventurer).
event(become_knight).
% so we'll create links, or edges which we'll use for pathfinding later
edge(hero_noble, become_knight).
edge(hero_commoner, become_adventurer).
% also we'll create an initial node for pathfinding purposes
event(start_story).
edge(start_story, hero_noble).
edge(start_story, hero_commoner).
% depending on our settings, there is no reason why a noble could not become an adventurer so we'll add a connection
edge(hero_noble, become_adventurer).
% his family might oppose it though so, you know what? Let's say there is a reason why he became an adventurer: he ran away from home and needs to make a living.
event(run_away_home).
edge(hero_noble, run_away_home).
edge(run_away_home, become_adventurer).
% Right. We've only dealt with "events" but it would clearly be possible to add layers to the story by specifying nodes indicating the reason why the hero ran away (such as an arranged marriage for example).
% And now, the important part: fighting the monster. Once again, branching paths are joining together
event(fight_monser).
edge(become_knight, fight_monster).
edge(become_adventurer, fight_monster).
% and the result: we win, or we lose. Our path branches again.
event(win_fight).
event(lose_fight).
edge(fight_monster, win_fight).
edge(fight_monster, lose_fight).
% if the hero win, the story stops there. Else, we'll add some meat to the story
% the hero will train harder, or go find some sort of legendary weapon before challenging the monster again.
event(train).
event(find_weapon).
edge(lose_fight, train).
edge(lose_fight, find_weapon).
event(fight_monster2).
edge(train, fight_monster2).
edge(find_weapon, fight_monster2).
% this time he wins, and we wrap everything nicely by joining the paths in the end_story node.
event(winner2).
edge(fight_monster2, winner2).
event(end_story).
edge(winner, end_story).
edge(winner2, end_story).
So, with all this we have a succession of events which are more or less easily extensible. We also have branching plot and everything wraps up nicely with the presence of the start_story and end_story nodes which will make pathfinding between start and end a breeze.
This article is already quite lengthy so I’ll spare you the details on Pathfinding in Prolog and just share the algorithm, but you can google it easily.
path(A,B,Path) :-
travel(A,B,[A],Q),
reverse(Q,Path).
travel(A,B,P,[B|P]) :-
edge(A,B).
travel(A,B,Visited,Path) :-
edge(A,C),
C == B,
+member(C,Visited),
travel(C,B,[C|Visited],Path).
story(ANCHORS, PATH) :-
path(start_story, end_story, PATH),
forall(member(M, ANCHORS), member(M, PATH)
).As explained before this version of the algorithm is basically a pathfinding algorithm, with added checks on the presence of given anchors in the generated Path.
Prolog will find all valid paths (use ”;” instead of enter after a query to get other valid results).
% let's find all stories possible. I should have a few more events defined in my basic setup so you might not get the same results
?- story([], PATH).
P = [start_story, hero_noble, forced_betrothal, run_away_from_home, become_adventurer, fight_monster, winner, end_story] ;
P = [start_story, hero_noble, forced_betrothal, run_away_from_home, become_adventurer, fight_monster, loser, train, fight_monster_2|...] ;
P = [start_story, hero_noble, forced_betrothal, run_away_from_home, become_adventurer, fight_monster, loser, find_weapon, fight_monster_2|...] ;
P = [start_story, hero_noble, become_knight, fight_monster, winner, end_story] ;
P = [start_story, hero_noble, become_knight, fight_monster, loser, train, fight_monster_2, winner2, end_story] ;
P = [start_story, hero_noble, become_knight, fight_monster, loser, find_weapon, fight_monster_2, winner2, end_story] ;
P = [start_story, hero_peasant, become_adventurer, fight_monster, winner, end_story] ;
P = [start_story, hero_peasant, become_adventurer, fight_monster, loser, train, fight_monster_2, winner2, end_story] ;
P = [start_story, hero_peasant, become_adventurer, fight_monster, loser, find_weapon, fight_monster_2, winner2, end_story] ;
false.
% looks like it works properly. Now let's add some "anchors", aka mandatory events.
?- story([find_weapon], P).
P = [start_story, hero_noble, forced_betrothal, run_away_from_home, become_adventurer, fight_monster, loser, find_weapon, fight_monster_2|...] ;
P = [start_story, hero_noble, become_knight, fight_monster, loser, find_weapon, fight_monster_2, winner2, end_story] ;
P = [start_story, hero_peasant, become_adventurer, fight_monster, loser, find_weapon, fight_monster_2, winner2, end_story] ;
false.
?- story([find_weapon, hero_noble], P).
P = [start_story, hero_noble, forced_betrothal, run_away_from_home, become_adventurer, fight_monster, loser, find_weapon, fight_monster_2|...] ;
P = [start_story, hero_noble, become_knight, fight_monster, loser, find_weapon, fight_monster_2, winner2, end_story] ;
As you can see, we’ve managed to specify a knowledge base of events and set connections between them so as to get branching paths. A more complex implementation would have a focus on composability and prevent infinite cycles but for now I think this is a pretty cool initial setup.
This was one of my first forays into logic programming and Prolog; I found Prolog requires a different mindset to use compared to my usual languages but it’s a nice tool to know. I hope I’ll get to show you more neat stuff, and a more complex story generator next time!