Procedural narratives: working toward an implementation

This is the start of the capstone to our discussion of actor-based procedural narratives. We discussed our goals, we described how to make decisions without referring to other actors, we described some potential improvements to that decision-making algorithm, we incorporated other actors’ actions into our decisions…

and now it’s time to write some code.

Before we do that, let’s look at the code we need to write.

We need:

  • the world
  • any background simulation (accounting for nature and other non-actors)
  • the mutations or possible actions
  • the basic elements of plot
  • a plot generator
  • an explainer

Now, we’ve implicitly discussed it, but let’s put this to the fore: we’re going to be producing tons and tons of possible worlds. We need a way to make these copies, be certain of not overwriting the actual world state, and process them as appropriate.

Using a functional programming language gives us security and copy-on-write semantics for free. We’re guaranteed not to overwrite the state of the world, ever. And many runtimes are smart enough to share unchanged state, which is awesome.

Another option is to store the decisions rather than the entire world state. This is a time/memory tradeoff; instead of storing world states, you recalculate them.

Previously we mentioned a constraint on the amount of prediction each actor does. We mentioned a number of possible worlds to evaluate at first. If we reinterpret that as a number of days in the future instead, we can change to a depth-first search. Now, instead of a queue of states to examine, we have a stack. This is much more efficient: you keep logarithmically many states in memory instead of a linear amount. However, it rather breaks best-first search, which previously allowed us to descend further along paths that seemed more promising. What we can do instead is probabilistically terminate processing on paths based on their depth and the expected utility.

In the context of a game, it should be relatively straightforward to identify the actions that can be taken. For a non-interactive work of fiction, it might be slightly harder. In either case, the plot is a heap of work.

Tune in next time and we’ll start the implementation. Maybe.