Procedural narratives: making decisions in isolation

In the previous entry, we said that the first two steps in creating a procedural narrative were to enumerate options that actors can take (including their immediate results) and to implement a naive graph search.

Let’s define this more concretely. The nodes in the graph are possible world states, with the start node being the current state. The edges are decisions. In this simple version, they are all decisions that the current actor could take. You can just breadth-first search your way through the graph, stop when the AI budget for this actor has been reached, and go with the best option you’ve found so far.

That’s straightforward — but how do we define “best”?

The best possible world state is the one that matches the actor’s goals most closely. In order to make this definition tractable, we require our goals to be formatted in a specific way. For instance, one goal might be to have a world under this actor’s control reach a population of fifty million. This is an excellent goal for our system because we can simply find the highest population planet under the actor’s control, subtract its population from the target one, and get a distance metric for that goal.

However, an actor can have multiple goals. To manage tradeoffs between them, we need to normalize these metrics according to their importance to the actor. This isn’t utility, really — it’s quite possible that it’s useless to have a planet of 49 million and worth everything to have a planet of 50 million. It’s not quite expected utility, either, but it’s a crude approximation of expected utility.

Once we have that, we can determine, for a given actor, how good a particular possible world state is. And that lets us find a preferred future.

Now that we’ve got that sorted out, we can take a look at potential refinements.