Creating worker NPCs using behavior trees
I’m a huge fan of RimWorld, a base building game where you manage a group of colonists. Rather than directly controlling the colonists, you place blueprints for buildings, mark trees for cutting, and animals for hunting. NPCs will then decide what to do automatically, based on their skills and priorities.
I’ve made two games recently with similar mechanics. The first was Ruben’s Virtual World Project (RVWP), a hybrid basebuilder/topdown shooter. The second was Tin Mining, a mining sim created as an entry to Ludum Dare 48. Both of these games allowed placing building plans that NPC workers would then build out.
In this article, I will explain how I implemented the NPC AIs, and the problems I faced.
Choosing a Game AI framework #
State Machines #
A common way to implement game AI is to use a finite state machine. Different things an NPC could do would be modelled as states, and the NPC would transition between states based on conditions.
One problem with state machines is that you need to program and design for all the transitions. What if an NPC dies whilst performing work? It shouldn’t keep working like a zombie until it’s finished.
State machines work very well for simple behaviour, like that of an animal or a dumb guard. But my NPCs need to be able to perform complex work, often with multiple steps. The states would end up being pretty complicated. I wanted a more capable framework.
Another concern was reuse. Lots of work involves the same actions - moving to a location, picking up an object, running an animation. It’s possible for states to reuse behaviour using utility functions, but this can be a bit painful. I wanted my game AI framework to make reuse as easy as possible.
After researching game AI, the obvious choice for me was behavior trees.
Behavior Trees / Behaviour Trees #
Explaining Behavior Trees in full is a bit out of scope for this article; I highly recommend reading “Behavior trees for AI: How they work” by Chris Simpson. However, I will try to explain the basics.
Behaviour trees allow you to control an NPC’s decision making by combining reusable nodes rather than creating new states. They work best when the nodes are small and specific, for example, you might have nodes to check conditions or walk to a position.
Behaviour trees are basically a programming language in themselves, but for game AI. Execution starts at the top of the tree, and then works downwards based on the rules of different nodes. A node is either running, succeed, or failed.
In the above tree, there is a Sequence node with two children. Sequences will
run each child one after another, until either a child fails or they have all
succeeded. The first child finds a random position, and writes it to a variable
called $target. The second child walks the NPC to that position. If the NPC
successfully finds a position and walks to it, then the sequence succeeds. If
either child fails, for example if there is something blocking the path, then
the sequence will also fail.
To implement logic, you can use decorators to check conditions. If the condition is true, execution continues to the decorator’s child. if the condition is false, the decorator marks itself as failed and returns to the parent. This is very powerful when combined with a selector, a node that runs its children until the first succeeds.
The above tree will check whether the NPC’s needs, such as health and energy, before doing work. This will be checked every time the tree updates, which makes it possible for death or low energy to interrupt work.
It’s possible for behavior trees to include other behavior trees. The “FindWork” node above does this in order to perform work; each work type has a tree. Here’s the tree for construction work:
I implemented behavior trees in Tin Mining using the Behavior Tree Godot plugin. I wrote my own implementation for RVWP as I couldn’t find a good Lua implementation, it was fairly easy to implement.
Goal-Oriented Action Planning (GOAP) #
Just a quick mention of another framework that I considered. GOAP is an AI system that allows NPCs to work out how to achieve a goal based on possible actions. For example, the NPC knows that building a house requires wood, and cutting trees makes wood. GOAP allows it to put these two things together, and cut trees to get wood to build a house.
I think this isn’t necessarily mutually exclusive to behavior trees, it operates at a higher level. You may use GOAP to decide what actions to do, and then implement those actions using behavior trees.
Work Manager #
Allocating Work #
Now that we have a framework for performing work, we need a way to decide what work an NPC should pick up next.
When a worker isn’t currently working on a task, it periodically asks the Work Manager for an available task. The Work Manager allocates tasks based on distance and a heuristic weighting of the task. For example, moving dropped items to the stockpile is weighted higher than mining or building, to avoid items building up and clogging the walkways.
In order to avoid NPCs working on the same thing, the Work Manager has a reservation system that allows NPCs to lock a tile, entity, or piece of work.
Reachability #
It’s important that NPCs are only allocated to work that they can reach - this
is called a reachability check, and is typically implemented using pathfinding.
Pathfinding tends to be quite expensive, but there are some quick checks that
can skip the effort in a lot of cases. My Tin Mining game uses a graph to
represent all possible paths; if a tile isn’t walkable, it’s not on the graph.
This means that you can check whether work is probably unreachable by seeing
if it’s on the graph, an O(1) check.
Pathfinding is still needed because it’s possible to have multiple disconnected subgraphs on the map. Pathfinding to every possible work would be quite expensive, so I defer pathfinding until after the work is allocated.
One problem with this approach is that it doesn’t know how close the work really is to the NPC. The NPC might be three tiles from the work but 100 tiles to walk there due to obstacles in the way. A future improvement will be to use the actual walking distance rather than the direct distance.
Work theft #
When an NPC finishes mining a tile, it often reveals more tiles to be mined. In the time between the NPC mining the tile and finishing the work, another NPC may have been allocated to the neighbouring tile. This results in a lot of inefficiency, especially if the other worker is far away.
At this time, I don’t have a good fix for this due to the simple nature of my work allocator. My workaround for the meantime is to avoid gaps between the tile being mined and the worker looking for work - but this doesn’t work with multiple-step work, such as digging a tile and then placing a ladder.
In the future, I’d like to implement a global work allocator algorithm. Instead of considering each worker’s request independently, it should keep track of idle workers in each frame and allocate them all in one go.
Another option would be to add some form of work queue or reservation. This is how RimWorld resolves this problem.
Adjusting Priorities #
Because the Work Manager uses a heuristic to allocate work, it’s possible to change the heuristic to change how work is allocated.
In my tin mining game, I was having an issue where the workers would keep mining tiles and leave all the rubble and ore on the ground. Ideally, workers mine for a bit and then haul items back to the surface.
The first change I made to fix this was to make the dropped entities appear 20% closer than minable tiles, but also add an offset of 3 tiles so that workers prioritise close tiles. This mostly worked, but when mining long sections you can still end up with a lot of dropped items.
The second change was to make that 20% multiplier vary based on how many dropped items there are. When there are not many dropped items, hauling items is a lower priority. The more dropped items there are per worker, the higher the priority becomes.
# Calculate multiplier based on number of dropped items
targetDroppedItems = min(3 * numberOfWorkers, 200)
droppedItemsMultiplier = 0.95
if len(droppedItems) > 3*targetDroppedItems:
droppedItemsMultiplier = 0.4
elif len(droppedItems) > 2*targetDroppedItems:
droppedItemsMultiplier = 0.65
elif len(droppedItems) > 1*targetDroppedItems:
droppedItemsMultiplier = 0.8
# Calculate weight based on distance, the multiplier,
# and an offset to prioritise nearby tiles
weight = droppedItemsMultiplier * \
worker.position.distance_squared_to(item.global_position) + 3*3Debugging #
One of the hardest parts of designing complex systems is making it easy to debug. You want to know what an NPC is ‘thinking’, and be able to trace why it did something at a certain time. I use a combination of logging and UI debug tools to do this.
I have UI debug tools for the pathfinder, for inspecting work and locks on a tile, for showing the NPC behavior tree and current work, and more.
RVWP has an immediate mode based debug API that allows adding lines and labels to the world. This is very useful when designing game AIs, and can be seen in the RVWP animation in the above section.
local debug = rvwp.get_debug()
debug:draw_line(from, next_pos, "#fff")
for i=self.path_i + 1, #self.path do
debug:draw_line(self.path[i - 1], self.path[i], "#999")
endSo many bugs #
Creating complex systems from simple rules is a great way to get a lot of random bugs.
Running the pathfinder every frame would be expensive, so instead paths are cached by the NPC. This resulted in NPCs not being aware of map changes, causing them to fall down holes or get stuck behind new walls. The fix was to validate the cached path against the navigation graph whilst moving.
Another problem I kept running into were NPCs just doing nothing. One of the times this happened was because NPCs kept being allocated to work that would fail, perhaps it wasn’t reachable or wasn’t possible in some other way, Whilst I could make the work manager check every precondition, it wouldn’t be very flexible. I’d rather preconditions be implemented by decorators on the behavior tree for each work type. My solution was to introduce failure lock outs: if a piece of work fails, the NPC won’t retry it for 10 seconds.
RimWorld Regions #
The task of finding the nearest work by walking distance can be expensive. RimWorld has a fairly clever algorithm for doing this which I may investigate in the future.
RimWorld uses a system of “regions” to make looking for work based on walking distance super fast. Regions are essentially a higher-level pathfinding system - instead of pathfinding based on nodes, it groups the map into regions at most 16x16 tiles in size, but further divided by walls. It remembers how regions are connected. To find the closest work, you can iterate through the current and nearby regions. The developer of RimWorld made an excellent video explaining regions, I highly recommend watching it.
Conclusion #
My system is surprisingly effective despite being made out of simple rules and components. While in the future I’ll probably implement more complicated work allocation algorithms and a region system, it works well enough for now, allowing me to focus on implementing other systems and game play mechanics.
Comments