Last time I talked about my gamedev exploration, I decided that I wasn’t going to talk about LOVE2D specifically. Love is what I am using as the foundation, but at least for now I don’t have anything Love-specific that is useful enough to share…

Anyway, a week or so ago I decided I wanted to implement some rudimentary behaviors for NPCs in the game. Making the world feel “alive” is pretty important to me. Something as simple as an NPC moving around the map would be better than them just standing like mannequins.

I began by looking into what game AI looks like and how it’s implemented by watching GDC talks and reading various articles.

If you’d like to skip reading this post and take a look into what I based my system on, here’s a list of things that I found useful.

• Wikipedia: Behavior Trees
• Behavior Trees Introduction, Zanid Haytam
• Behavior trees for AI: How they work
• Behavior Trees for Computer Games, Yoones A. Sekhavat
• (video) Behaviour Trees: The Cornerstone of Modern Game AI
• (video) GDC: AI Arborist: Proper Cultivation and Care for Your Behavior Trees

If you’d like to skip this post and take a look at the library I built to use in my “engine”, take a look at behave. This is what I’ll be detailing today.

BTW: I am an amateur so please make sure you do additional research on this topic. There are definitely things about this topic that I’ll butcher or simply not know about yet.

What are Behavior Trees?

Behavior Trees are directed acyclic graphs (no cycles) that allow modeling of tasks.

Tasks are nodes in the tree that do any kind of work and return a status that can be used to inform their parent, which can perform an action based on said status.

There’s also event-driven behavior trees, but I won’t go into that.

An example

The simplest behavior I can think up with is:

General execution of this can be broken down to:

• root executes
• can-see-player? executes
• if successful, execute shoot-at-player
• otherwise, execute walk-around

The nodes underneath the root are executed - and return a status that informs their parent. In this case, it isn’t exactly clear what the status is used for, so let’s talk about two things: Sequences and Selectors.

Sequences and Selectors

A Sequence is a node that has N child nodes. It runs each child until one of them returns a “failure” status, at which point it stops running any subsequent children.

In pseudocode, this might look like the following:

yes, this is just a function, figure out how to express as a type in your language of choice

sequence(children []node) returns status {
	for node in children {
		status = node->run()

		if status != success {
			return failure
		}
	}

	return success
}

A Selector is a node with N children that runs each child until the first “success”, at which point it stops running any subsequent children.

In pseudocode, this might look like:

selector(children []node) returns status {
	for node in children {
		status = node->run()

		if status == success {
			return success
		}
	}

	return failure
}

Where this becomes useful is in our example. While the main decision is “is the player visible?”, it can be modeled as a combination of both a Sequence and a Selector.

The first node in our behavior could be a selector: run until we get a success. The first node of that selector could be a sequence: run until we get a failure. The second node of the selector could be a simple leaf that cause the NPC to walk around.

In the sequence, we’d have two nodes:

• Can see player?
• Shoot at player

If we can’t see the player, execution halts and returns a failure to the sequence, which subsequently returns that status to its parent - a selector. The selector gets a failure status and moves on to the next node: walk around!

In the case that we can see the player, the player is shot and a successful status is returned to the parent selector - causing the walk around behavior to not be executed.

I do want to note that how you’d model this is entirely up to you, this could be modeled any number of ways. This is just what makes sense to me.

My Implementation

The library I wrote is called behave. It’s a bit naive, but works for my usecase.

To instantiate some behaviors, you create a root behavior. This root is not a sequence or selector, but runs through all behaviors regardless of their status.

local behavior = behave.Behavior("name", { nodes })

To add nodes to the set, you can either preconstruct the nodes and add them at the time the root is created or add them dynamically:

local node = behave.Leaf("name", function() return behave.Node.status.success end)

behavior:add(node)

The behave repository contains an example as well as API description, so check that out for more.

My Sandbox Sample

For clarity, I make a distinction between my game’s “engine” and the game’s content. I call the latter the sandbox.

As an example, the engine has a system for running behaviors at regular intervals, but doesn’t implement any on its own. It’s just the infrastructure. The sandbox contains definitions of behaviors, and they’re attached to entities when needed. It’s great to have these separated and keeps my code a lot cleaner.

To the point, chrsm!

One basic behavior I’ve implemented is “predefined movement”. I can attach a behavior to any NPC that basically says “move from point a to b”.

A simplified version of this code, written in Yuescript (a Moonscript alternative) is below.

Note that this simple version is just sideways movement and I haven’t run it, the actual movement behavior includes some pathfinding, collision detection, actual points (x,y not just x), and generally more configurable.

MoveSideways = (entity, p1 --[[ vec2 ]], p2 --[[ vec2 ]]) ->
  pos = vec\xy entity.position.x, entity.position.y

  state =
    direction: "right" -- which direction we should walk in
    paused: false
    pausedFor: 0.0     -- how long we've been paused for

  -- self here referring to the entity, btw; allows for cleaner code
  (self, dt) ->  
    if state.paused
      state.pausedFor += dt

      if state.pausedFor > 5
        state.paused = false
	state.pausedFor = 0

      -- early return, we don't want to run anything else.
      return Node.status.success
    elseif state.direction == "left"
      pos.x = @position.x + (-@velocity * dt)

      state.paused = pos.x <= p1.x
      state.direction = "right" if state.paused
    elseif state.direction == "right"
      pos.x = @position.x + (@velocity * dt)
      
      state.paused = pos.x >= p2.x
      state.direction = "left" if state.paused

    -- do the actual move and then return;
    -- there should be collision detection here, too.
    -- if you can't actually move to where you want,
    -- you could force a pause.
    
    Node.status.success

return MoveSideways

With this implemented, attaching it to an NPC is fairly simple:

import "behave" as behave
import "move_sideways" as BehaviorMoveSideways

entity = new-instance-of-entity

node = BehaviorMoveSideways entity, vec\new{5, 0}, vec\new{10, 0}
  |> behave.Leaf "move_sideways", _

behavior = behave.Behavior "default", { node }

entity\addBehavior behavior

At a regular interval each behavior is executed. This entity will move along the x axis of a map until it reaches x=10, at which point it will stop for about 5 seconds and then walk back to x=5.

As of right now, my implementation doesn’t share state across nodes, so implementing the pause behavior inside of the movement one here is necessary. I may implement this, or simply tie a Move and Pause node together as a selector. At any rate, this works for me at the moment.

Running this in game - along with a “blocked” behavior check to start a dialogue - looks like this:

;wq

That’s about it. Again, I recommend reading/watching the resources at the top of this post! The authors of those are much better at explaining these than I am.