Refactoring Wilderplace's AI system

In this post, I’m going to walk through Wilderplace’s AI system. The AI system controls how characters move and perform actions.

Debug level that demonstrates lots of AI entities doing what they do.

A couple months ago, after adding a handful of AI entities ad-hoc, I hit a breaking point. There were too many inconsistencies between entities, too many minor bugs, and in general, adding new content came with a sense of dread. It was time to refactor. I took a week to finish a re-write. The rewrite introduced a clean split between configuration and code, resulting a more manageable and scalable system.

There’s an aphorism that any sufficiently complex program contains a bad implementation of Lisp. I’m proud to announce that Wilderplace has reached that complexity threshold. A Lisp-like S-expressions evaluator is at the core of the AI refactor. S-expressions make the separation between code and configuration possible without sacrificing flexibility.

AI’s role in Wilderplace

I didn’t expect AI to be an important part of Wilderplace. There were supposed to be two characters with AI: loggers and demons. I thought I’d end there, focus on making mostly-static levels interesting. Then, unique interactions between the loggers and demons inspired me to add more characters with more behaviors. Then, relationships started to emerge between the story and the gameplay. Over time, AI became a big part of the game.

Here’s a series of interactions between the logger, healer, and spirits.

This is the first time I’ve written a game, and I didn’t do much research into best practices for AI systems. The system evolved to meet gameplay and narrative requirements. It’s “goal oriented”: entities (like loggers) have goals (pathfind to the nearest tree), they perform actions (chop down the tree) when they meet goals, and goals can be heirarchical (after chopping down a tree, pathfind to the exit and exit the board).

There are now ten different characters and I have plans to add more. The levels where one careful move cascades into a complex interaction between different actors are my favorite to design and play.

The old system

The old AI system wasn’t designed to support more than a few entities. There was no separation between configuration and code so it relied on code duplication. I wasn’t sure if the cast of entities would grow, so I didn’t bother with abstraction early on. Let’s walk through some simplified versions of the functions that power the old system now, so we can later understand how they changed after the refactor.

Wilderplace uses an action queue to manage it’s game loop (I wrote more about that here), and the old AI system necessitated adding a new queue function for each entity type to the game loop. These queue functions ran every time the player took a turn. Here’s the logger’s queue function:

// Called every time the player moves
function loggerQueue() {
  const state = getState();
  const loggerIds = getLoggerIds(state);
  // For each logger, try to do things
  loggerIds.forEach((id) => {
    // A central queue that handles all state updates.
    behaviorQueue.push([
      // These are "behavior functions"
      () => loggerMove(id),
      () => loggerDisable(id),
      () => loggerChop(id)
    ]);
  });
}

Each behavior function checked game state and decided whether or not to dispatch and action to trigger a state update. Here’s an example:

async function loggerMove(id) {
  const state = getState();
  // loggers's pathfinding logic is defined inside getLoggerMove
  const { start, dest } = getLoggerMove(state, id);
  // Update state
  if (!isEqual(start, dest)) move({ id, dest });
}

Each entity pushed 3 or 4 different behavior functions to the queue. For the sake of illustrating how much code was involved in adding each new entity, let’s also look at the pathfinding function, which is called loggerMove. Don’t worry about reading all the details:

function getLoggerMove(state, id) {
  const logger = getBoardById(state)[id];
  // No move if logger has spirits or sleeping.
  if (logger.spirits.length || isSpiritWorld(state)) {
    return null;
  }

  const movementMap = generatemovementMap(board, (tile) => {
    // Callback to test each tile & generate movement scores.
    // ...Lots of complicated code here.
  });

  let goalSets = [];
  // First target: drone
  const dronePos = getDronePos(state);
  if (dronePos.length) {
    goalSets.push(dronePos);
  }
  // Second target: tree
  const treeTilePos = getTreePos(state);
  if (treeTilePos.length && !logger.hasRemovedObstacle) {
    goalSets = goalSets.push(treeTilePos);
  }
  // Third target: exit
  if (logger.hasRemovedObstacle && !logger.spirits.size && gatePos.length) {
    goalSets.push(gatePos);
  }

  const threats = getWardenPos(state);
  // pathfind returns results from a* pathfinding
  return pathfind({
    origin: logger.position,
    movementMap,
    goalSets,
    threats
  });
}

Loggers, demons, and every other entity type used this pattern. Every new entity introduced a lot of new code. New code meant lots of opportunities for inconsistencies which slowly proliferated, making it increasingly hard to add more content.

The new system

The refactor split the old system into two parts: code and configuration. In the new system, entities share a set of generic functions and then a configuration object defines entity-specific behaviors. Here’s the generic queue function:

function aiQueue() {
  const state = getState();
  const actorIds = getActorIds(state);
  actorIds.forEach((id) => {
    behaviorQueue.push([
      () => move(id),
      () => action(id)
    ]);
  });
}

Behavior functions are also shared. Move is similar to loggerMove from the old system:

async function move(id) {
  const state = getState();
  // Pass config to a generic getMove function
  const { start, dest } = getMove(state, id);
  // Update state
  if (!isEqual(start, dest)) move({ id, dest });
}

Inside getMove, we evaluate configuration, generate a movement graph, and pick targets:

function getMove(state, id) {
  const entities = getEntitiesById(state);
  const actor = entities.get(id);
  const goalSets = [];
  const threats = [];
  const movementMap = {};

  // Get ai configuration based on entity type
  const config = aiConfig[typeFromId(id)];
  entities.forEach((target) => {
    config.targetSets.forEach((exp, i) => {
      // Add position to goalSet when evaluate passes
      if (evaluate(exp, { target, ...ctx})) {
        goalSets[i].push(target.position);
      // Add position to threats list when evaluate fails
      } else if (evaluate(ai.threats, { target, ...ctx})) {
        threats.push(target.positions)
      }
    });
    // Assemble movement map
    const pString = target.position.toString();
    movementMap[pString] = evaluate(ai.movement, ctx) ? 1 : Infinity;
  });

  return pathfind({
    origin: actor.position,
    movementMap,
    goalSets,
    threats });
}

The three evaluate calls in the above code sample handle all entity-specific logic, which is provided by config. There is one evaluate to pick goals, one to pick threats, and another to score tiles on the movement map. We’ve factored out all entity-specific logic by using config. What does config look like? Here, we start to see some S-expressions. This is the logger’s AI configuration file:

{
  // movement defines where on the board an entity may move.
  movement: [
    'all',
    // Logger has no spirits.
    ['==', ['actor', 'spirits', 'length'], 0],
    // Logger is not sleeping.
    ['==', ['state', 'spiritWorld'], false],
    // Target has traversable property (not an obstacle).
    ['target', 'traversable'],
  ],

  // `threats` weights the movement graph to avoid positions that match threats.
  threats: [
    'match',
    ['target', 'type'],
    [TYPES.WARDEN],
  ],

  // targetSets is a list of targets, used for movement and for triggering
  // actions. Higher targets in the list are prioritized over lower targets.
  targetSets: [
    // First target: drone
    ['==', ['target', 'type'], TYPES.DRONE],
    // Second target: plant
    [
      'all',
      // Logger has not yet removed obstacle.
      ['==', ['actor', 'hasRemovedObstacle'], false],
      // Target is a plant obstacle
      ['==', ['target', 'type'], TYPES.PLANT_OBSTACLE],
    ],
    // Third target: exit
    [
      'all',
      // Logger has removed an obstacle.
      ['ctx', 'actor', 'hasRemovedObstacle'],
      // Target is a gate.
      ['==', ['target', 'type'], TYPES.GATE]
    ],
  ],

  // targetActions is a set of actions that will be
  // triggered if, after actor moved, the actor's
  // position matches the target's position.
  targetActions: [
    CREATURE_DISABLE,
    CREATURE_REMOVE_OBSTACLE,
    CREATURE_EXIT,
  ],
}

movement, threats, and each target in targetSets are expressions. In practice, some of these expressions are more complex and/or get generated from code or shared as variables.

We’ve looked at where evaluate gets called, and we’ve looked at our configuration. The final piece of the new system is the evaluate function itself. Here’s a simplified version:

// fns is a collection of functions in the Lisp-like syntax.
const fns = { 'all': Function, 'none': Function, 'actor': Function, ect... };

// Expression is an array where the first element is the name of a function,
// for example: ["==", 1, 2]. Evaluate returns the result of evaluating all
// the functions in the expression down to primitive values.
function evaluate(expression, ctx) {
  function run(exp) {
    // We have our final primitive value, so return
    if (!Array.isArray(exp)) return exp;
    // Separate the function name from it's arguments
    const [name, ...args] = exp;
    // Get the actual function based on name.
    const fn = fns[name];
    // Traverse expression, evaluating inside-out
    // so child functions resolve to primitive values that are inputs
    // to parent functions.
    return fn(ctx, ...args.map(run));
  }

  return run(expression);
}

Get an expression, get back a primitive value. The version I’m using in Wilderplace handles stateful expression types that I left out (useful for, for example, seeing if there are any targets of a given type on the board).

Why use S-expressions?

An S-expression system maximizes flexibility and expressiveness within a clearly defined bounds. With S-expressions, I can query the game state in sophisticated ways, but I won’t, for example, accidentally break the game loop. Another advantage is that I’m already fluent with them. I’ve worked with Mapbox GL expressions for years, which use a similar syntax.

There are fine alternatives. I could have used a configuration format that didn’t require an evaluator. For example:

const loggerConfig = {
  goals: [DRONE, PLANT_OBSTACLE, GATE],
  actions: [CREATURE_DISABLE, CREATURE_REMOVE_OBSTACLE, CREATURE_EXIT]
  threats: [WARDEN],
  sleeps: true,
  obstacleCarryLimit: 1,
  exitsBoardAfterReachingLimit: true,
  /* ...ect */
}

If I took this approach, I’d need to handle a growing number of conditional behaviors (sleeping, obstacle carry limits, ect), and I’d need to write code for every new condition, and I’d need to evaluate those conditions for every entity type. It’s less flexible, and requires reworking more internals of the AI system when adding new types of behaviors.

At some point I should learn more about game development best practices, because I have no idea how AI systems are normally implemented, or how the popular game engines do it. I hope I’d be pleasantly surprised to learn there’s an obvious, better way to build expressive AIs.

Was it worth it?

I’m suprisingly satisfied with the new system. It came together quickly, and now adding new entities is fast and painless, code sharing between entities is simple, and there are fewer opportunities to introduce inconsistencies.

The two latest entities: toadman and malfunctioning automaton

After finishing the AI rewrite, I did the same thing with the rendering system. Now, expression evaluation powers sprite and animation picking. Everything except the state update logic inside spell functions is now configuration. Maybe I’ll rewrite that spell system to use expressions too.