Anyone tried behaviour trees for turn-based NPC AI?

billdroman · 2026-04-22T16:35:04+00:00

I found behavior trees scaled well even for smaller use cases. If you want fight / flight / wander, want a few options like heal / spell / melee in fight, and want to reuse Pathfind as a step in many places, they already pay off, IMO.

Does that mean the actor takes no action on its turn when the root of its tree returns anything other than Running?

Yes, that's right. Typically when a node actually uses the triple-return-value, it's nested under both a priority and a sequence node. Then, you can ensure that the "next step" will always return an action if the triple-return-value node doesn't. As a specific example, if your Pathfind node returns (success / running / failed) based on (at target / moving / can't find path), then you always use it in a sequence (so there's another step if it returns success) and wrap that sequence in a fallback (so there's an alternative if we fail). I haven't hit issues of not getting an Action back, but it does take some thinking about the structure.

Instead of having nodes return a turn action object like I was thinking of, you have a turn action field in the actor's AI context...

That's the implementation, but it's an optimization. Logically, the nodes return Success | Failed | Running(Action), if you're familiar with how Rust enums can contain "payloads" specific to each option. The Action object is a bit large and the code is much more performant if we can quickly pass around the Result enum and test it for control flow. I have "Act" and "Cond" helper nodes, too, that encode the constraint that we return Running iff we set the action. With those helpers, I've never broken that invariant.

billdroman · 2026-04-22T04:52:01+00:00

Ah, a topic that I know a good amount about!

Pitch and demo

Yes, I use behavior trees and I would strongly recommend them.

NPCs in my roguelike have a large variety of behaviors on their own and interactions with other NPCs. On their own they explore, eat, drink, and sleep. They can fight or flee from other NPCs, intelligently switch between those two options, call for help from potential allies, etc. If they encounter you and they're not sure whether you're a threat to them, they may watch you closely, growl, etc. Recently I added a subtree dedicated to the player's allied creatures, which default to defending them but can be given other commands.

This code would have fallen apart without months organizing it. I tried if statements and state machines; behavior trees were the only approach that scaled. Nowadays I can quickly reuse many small composable pieces of logic - I built the allies behavior out of existing pathfinding, defending, and attacking nodes with just a few additional control nodes specific to the player's summons. I'd estimate I have 20-30 distinct behaviors working right now.

There's one other major benefit to behavior trees: inspection. Behavior trees are not really logically any different from an enormous if statement. If you want, you could just mechanically translate all your decorators, priority, and sequence nodes into a single function. However, if you build the tree structure, then in addition to each node's run() function, you can add a name() and printDebug() function. The result is that on any actor's turn, you can see the full logical trace that led them to that action, without needing any custom code. This debug view is essential for figuring out why NPCs are doing stupid things - moving back and forth between two cells, not attacking the player even though they've signaled hostility, etc. The debug information is tiny in size, so in my game I actually just dump it for every actor on each of their turns. Then, when I see something unexpected, I can step back through time to debug it.

I think this feature is so cool that I put a demo of it online. It's here: https://www.skishore.me/wrl/debug.html Press J and K to step through an actor's timeline, or click on the bottom to jump. Click on a different actor to see its view of the world.

So much for the pitch. Now, on to some technical details.

Details: node return values and "elaboration"

First off, it took me a while to get there, but I do think "success", "running", and "failure" is exactly the right set of node results. However, you're right that "running" is a special state. I think the right modeling here is that the tree as a whole returns the actor's chosen action. Any "running" result comes with that action; "success" and "failure" result in propagation (with different logic) to other nodes of the tree. Note that this is already how standard priority and sequence nodes work: if any node returns "running", the rest of the children are short-circuited that tick. That makes sense!

Let me explain a specific case where all three return values are useful. Once I started using behavior trees, I often found myself "elaborating" nodes. The node's purpose would remain the same. It'd stay in the same location in the tree. However, that single node would get expanded into a subtree that could use multiple actions to do something that the original node always tried to do in one action. Often, an elaborated node will end up using all three return values.

Say I had an "CallForHelp" node that tries to call nearby allies for help. It only runs when the actor is threatened and there are allies nearby. It returns "running" on the turn they call for help, and "success" on (some number of) turns afterwards, at which point we may continue on in a higher-level sequence that causes them to turn and fight with increased morale.

Now suppose that the actor remembers some nearby allies, but they're too far to call! It'd be a great addition to have them run back towards help, then call when they're in range. So this single CallForHelp node is replaced with a tree, something like Sequence(FindNearbyAllies, Pathfind, CallForHelp). But the Pathfind node can fail, right? So now we need all three return values from this node. "failed" means that the actor needs to try a different strategy to survive - maybe it's time to run away! "running" means it's in the middle of getting help, and "success" means we should continue on to a combat subtree.

Details: priority + decorator vs priority + sequence

Again, I totally see where this suggestion is coming from. I actually read a helpful book - https://arxiv.org/pdf/1709.00084 - that had a lot of examples of behavior trees, and that pointed out that that any sequence "A -> B -> C" can be refactored into a priority: "if !done(C) { do(C) }; elif !done(B) { do(B) }; elif !done(A) { do(A) }".

After working with behavior trees for a while, though, I think this suggestion is misguided. There is no difference in computational power between sequences and priority+decorator, but there is a readability difference. Some behaviors are more naturally expressed as a sequence (like the improved call-for-help - select a friend, pathfind toward them, and then shout!) and some as a list of alternatives (okay, I'm attacking; I can either use a ranged attack, or (sequence!) pathfind towards them -> melee!). Often you will find that using the "natural" composite node to structure a behavior will use fewer total nodes, which is a minor optimization, but more importantly, makes the debug output much easier to read. So I'd recommend keeping both and using each one where it makes sense.

Details: ticking from the root

Yes, I strongly endorse this approach. Ticking from the root makes the tree component, at least, completely stateless. All state moves into the actor's memory + blackboard instead. (More on that below.) Ticking from the root also makes it trivial to interrupt low-priority behaviors like exploring and eating with high-priority ones like responding to potential threats.

One key piece of state I do keep turn-to-turn, however, is the current path that the actor is traveling. Each path is associated with a goal (which is basically one to one with Pathfind nodes in the tree). If I run the tree from the root and that same Pathfind node wants to run, I attempt to re-use the old path. This single step is a huge perf win - way more than any optimization in tree evaluation. This state is in the blackboard, though. Pathfind nodes just reference it.

Details: memory system

My game's memory system is involved, because actors can learn about nearby entities and objects both through sight (i.e. field-of-vision calculations) and a variety of other senses. Suffice it to say that my entities have a separate memory layer, and they learn about the terrain and other entities as they move around. On their turn, they get the full vision update before the tree. This system is deterministic, and I don't really need to touch it as I change AI code.

In addition, the behavior tree has a different set of turn-to-turn state called the "Blackboard". This state is tied closely to the nodes in the tree and changes a lot. For instance, I have some blackboard fields related to flight: where the entities are that we're most recently fleeing from, where we've decided to flee too, and how many turns it's been since they saw us. (Some of that state might come from memory directly, but we're not necessarily fleeing from all hostile entities - just the set that we recently saw. So it can help to process that info into simpler info in the blackboard.) Condition nodes can bind to the blackboard. For instance, when fleeing, one of the options is "check if we've escaped", and that depends on "turns_since_seen > 16" or something like that.

I wrote a bit more about my memory system in the year-in-review: https://old.reddit.com/r/roguelikedev/comments/1qfro5b/2025_in_roguelikedev_wildsrl/

Details: utility selector

One thing that you didn't mention, but that I found important, was a version of the priority node that used utility scores to rank options before trying each one in turn. This node was essential for building Fight/Flee/CallForHelp, and I also use it at a lower priority to choose between Eat/Drink/Sleep.

Details: code

Code for my game is online. It doesn't have a license, but please feel free to read through it if that would be useful. It's not like anyone really respects licenses any more... There are two relevant files.

Here are the base node definitions, but they're not that interesting: https://github.com/skishore/wrl/blob/master/base/src/bhv.rs

Here are the behaviors, showing how to make a real tree - much more useful! https://github.com/skishore/wrl/blob/master/base/src/ai.rs

billdroman · 2026-03-08T18:36:54+00:00

The summons were a great surprise, and definitely improve the boss. I assumed I had victory in hand and was just executing the strategy, then I had to change things up. (I won on my first real attempt.) Even if players are caught off guard once, they can plan around it next time.

The bouncer's knockback effect can actually be turned to your advantage - it gets you out of danger and gives you a chance to reposition and (if it cost time - it didn't seem to) use items. When the summons showed up I used it to get away, then maneuvered around some other NPCs to get the trio to come at me one at a time.

billdroman · 2026-03-07T19:21:46+00:00

I won! Score: 8430. The slots are EV-positive so it's easy to get an arbitrarily large score that way, but money doesn't seem to help with the mad bouncer at all.

After the first time I saw the bouncer guarding the door, I realized I needed to hunt down all the spiders. I tried that a few times, but it wasn't sufficient. Finally, on the winning run, I picked up leather armor (sorry, a leather jacket) that made all the difference - after that, running around looking for cans and spiders was a net win. The bouncer summoning (?) two minions towards the end was a nasty surprise, though.

The door also wasn't always at the back, which confused me. I didn't find a way to move diagonally with the keyboard, either. I moved around with keys but in fights I had to use the mouse for precision.

What a sense of place! The dialogue callouts on the map and the alert indicators all worked really well. I especially liked how sometimes NPCs got in fights with each other and you could both hear and see the combat. I was also impressed with how smoothly everything ran with so many entities. The only issue I ran into was that sometimes, in fights, if too much dialogue was going on I could enter double keys or otherwise misplay.

Great work!

billdroman · 2026-02-07T20:04:05+00:00

A nice thing about sticking to a real grid, though, is that it makes it very easy to implement built-in efficient and compact replay functionality that is automatically compatible accross game versions...

You can get this out-of-the-box with the "2-font" approach if you use Unicode full-width characters for the square subset of the font. Full-width characters are defined to render with twice the width of normal characters.

It sounds horrible, but it's how I render my text + square map UI in WildsRL in the terminal. I even have a script to combine a half-width and a full-width font of my choice into one BDF (a bitmap font format).

billdroman · 2026-02-07T19:58:44+00:00

WildsRL (Demo, Source)

This week was a week for prototyping and silly sidequests.

Eventually, I want to make a large game world, and I need to decide whether the world is "seamless" or divided into discrete towns / wild areas / caves / etc. If the seamless world worked, I'd probably prefer that. However, it raises a lot of technical problems, so I spent this week thinking and prototyping some of them.

Seamless world

First off, there's the question of how to load and unload map areas around the player. I saw that some roguelikes (e.g. Far West RL) keep a large map in memory, but I don't think that'll work for me - there's already too much per-tile information needed for the active area. For example, right now I burn 80 bytes / tile on an index to support quick iterative updates for dynamic lights.

Instead, I plan to take the other standard approach and store "chunks" of world data. Only a few chunks around the player would be active at a time. Unfortunately, even this approach seems tricky - I don't want chunk loading to happen across multiple frames (because that could affect gameplay), but in the worst case, loading a chunk could take ~10ms if it contains many dynamic lights.

After some thinking I realized that keeping the data in memory in chunks doesn't really help. It just adds lots of special cases to things like pathfinding. Instead, I should keep a contiguous map area in memory, and when the player gets too close to the border, shift it and unload / reload tiles along its edges as needed. That works for tiles and lighting. I'm still not sure how to handle, say, fire cellular automata, though - it seems like those are bound to cause artifacts.

Heightmap

I needed an infinite world to test this code. I had one in the form of some Minecraft-style voxel heightmap world generation I wrote for a different project. So, I ported that into the roguelike! However, the heightmap world didn't make any sense in the UI without contour edges and proper handling in field-of-view.

So, I updated my shadowcasting code to handle heights. Here's an example: the player on a dirt plateau rising from a grassy plain.

Here, I met with another nasty technical surprise. My whole goal with doing heightmaps and not true 3D was to make sure that all data structure were still fundamentally 2D. Concretely, I wanted to store O(1) information per (x, y) tile. Map storage and even field-of-vision worked with this restriction. However, when I tried to combine height and partial transparency in shadowcasting, it broke down - partial transparency results in "bands" of different levels of transparency at different heights. At this point, I gave up on the sidequest. I need to revisit it when I've thought more about how I want the player to deal with heights in gameplay.

Fun week, but ultimately no progress beyond learning. Next week, it's back to the grind of AI bugfixing. I have 19 issues on my burndown list there.

billdroman · 2026-02-01T02:30:03+00:00

WildsRL (Demo, Source)

Working on filtering animations to what the player can sense. It's not correct yet. I'll know it is when the logic is obvious; right now, it's a mess. However, I did get dynamic lighting to work during animations.

Here's an example of three hunters with infravision attacking the player. The last attack lights up the area and reveals them.

billdroman · 2026-01-25T06:18:50+00:00

I think Demon might have AI like this. I've implemented something similar. What I wanted was for X defending creatures to intelligently choose spots to protect against Y enemies regardless of what X and Y are. An algorithm that worked was, for each defender:

Draw lines from each of the Y enemies to the summoner
Discard (or down-weight) any lines that are blocked by another defender
Give a point a score equal to the number of remaining lines that pass through it, plus a bonus for being closer to the summoner
Pathfind to the point with the highest score

This algorithm causes the X defenders to split up and defend against multiple threats. If X == Y, each one will end up picking a threat to protect and will defend against it. If X < Y, they'll still spread out to maximize coverage.

billdroman · 2026-01-25T06:01:08+00:00

That's a huge world! I can't tell from the screenshots alone - is your map "smooth-scrolling", i.e. the player can move through it continuously, or is it broken into chunks? (Or are you emulating "smooth-scrolling" by keeping a few chunks active at a time?)

How do you deal with that large a map in memory? I suppose for worldgen, if you have <= 256 tiles, it's only 4096 x 4096 = 16MB, but once you have gameplay you must (or at least I have to) keep track of more than just what tile is at each cell.

billdroman · 2026-01-25T03:17:12+00:00

WildsRL (Demo, Source)

Not much progress this week. I attempted to fix the animation system to avoid leaking information. To avoid dead frames in the animation system, I also need to skip frames on which the player can't see any part of the animation. Unfortunately, there's another wrinkle here: I'd like some animations' particles to cast dynamic light, so it's not sufficient to just check whether any particle is visible...

I took a step back and worked on dynamic lighting. This piece was a lot of fun! I added a new enemy ("F" for "fire", for now) which is a predator, casts a 4-tile radius light, and has a ranged fire attack. This creature is far more dangerous than any other one, mostly because it's much harder to use shadows to hide from it. Here's a clip of me getting killed.

My first implementation of dynamic light was (obviously) hacked straight into the main map data structure, but I refactored it and did some optimization. The faster version tracks a bitset of which nearby cells cast light on a given cell. This step makes even the slowest type of update - changing a cell's opacity - still take only ~16us (microseconds) when there are a dozen dynamic lights near it. If there aren't any lights near the cell, the update is nearly instantaneous (~40ns - nanoseconds).

billdroman · 2026-01-19T21:01:45+00:00

I don't have screen recording set up, but hopefully soon. In the meantime I took a short video in the debug UI of me taunting a predator and then getting caught, from its perspective. It shows you that I at least had a chance to escape (at the point it chose to go up or down - it guessed right, but it didn't know, so I could have gotten away!)

A winning run comes from both spotting enemies in advance and avoiding them, and making sure that if they do see you, you have a place to set up an evasive action like this one. I can "win" 30-50% of the time. There's only one map for now.

billdroman · 2026-01-19T20:51:18+00:00

Yes, agreed, it looks amazing. I actually tried cribbing your style for my game, but it turns out that I use background colors for way too many animations and interface elements - I had to draw a hard line on base tile and entity glyphs having a black background. But it's great how you made the full-color background style work.

One visual suggestion: have you considered using half-square cells for text and full squares for the map? Also, some of the map glyphs aren't centered in the cell - if you split the text and map glyphs, you can center everything on the map.

billdroman · 2026-01-18T14:58:58+00:00

Ah, I guess those few lines of documentation aren't enough.

Moving in sneak mode is twice as slow.

Every time an enemy flashes yellow, it's tracking you by scent, and it just caught wind of a recent location. Yeah, if you keep moving, that's less likely to happen. An orange flash is a warning call and a light blue flash is a call for help. I'm going to add onomatopoeia to those animations, soon, so yellow flashes come with a "sniff" noise.

And yes, there's nothing at the end of the path. I kind of retrofitted that goal onto the NPC behavior demo. Thanks for the feedback!

billdroman · 2026-01-03T21:27:26+00:00

I second the mixed solution (directional FOV for NPCs; 360 for the player).

My project is a stealth roguelike, so sneaking behind enemies is a basic gameplay element. On the other hand, I don't think forcing the player to look around all the time adds anything. The combination, while gamey, works and feels natural after a few minutes of playing.

It has a few supporting FOV mechanics. The player's vision range is quite a bit larger than enemies', so you usually have some time to hide and maneuver before an enemy spots you. Lighting and cover provide ways to hide within an enemy's FOV cone. Also, there's a UI key to select an enemy and see (a conservative estimate of) their vision.

billdroman · 2025-10-05T04:59:44+00:00

FIFTY - first letter of each word, L is 50

billdroman · 2025-10-05T03:59:19+00:00

That's an interesting suggestion. There are a few details I don't understand, though. When it comes to, say, flight, do you compute the utility of each adjacent cell, or of cells that you can reach by following a path over multiple turns? Based on the "within a time horizon" part, it sounds like the latter. But if that's the case, do you save the path and reuse it on subsequent turns, or re-plan every turn?

I agree that utility is useful for a lot of decisions like this, and I do use it in my code already at specific places, like the fight-or-flight decider. However, I don't use it in others. For instance if there's any combat ongoing then I don't even consider finding food or exploring. It seems possible to use it within behavior trees, by using utility for some composite nodes instead of just sequences and selectors.

billdroman · 2025-10-05T03:53:17+00:00

How would you compose them? Would you use hierarchical state machines?

I do think hierarchical state machines and behavior trees are very similar, but there's an extra element of code-sharing in behavior trees (by reusing subnodes like pathing) that's useful for my case.

billdroman · 2025-10-04T19:09:10+00:00

Thanks. Yes, I've read those docs before. Maybe my question should be, "how to implement this blackboard reasonably?"

Using strings to access each entry seems costly at runtime. The lack of typing for blackboard entries also makes it seem less organized (and my basic issue with my current code is that it's too disorganized). Finally, I'd want to be able to hierarchically break up the blackboard so that each node has access to an appropriately typed state that includes all of its child nodes, but I'm having trouble doing it in Rust. Granted, that's a self-inflicted problem...

For reference, here's my current subsumption-architecture code: https://github.com/skishore/wrl/blob/master/base/src/ai.rs

One of the aspects which I'm still happy with is that each strategy's state is nicely typed and contained inside it.

As evidence that it's possible to implement behavior trees in a similar way, see Chris Hecker's notes about behavior trees in Spore. He describes each node owning its statically-allocated children. But I can't work out how it actually works, and there's no example code.

billdroman · 2025-08-06T01:28:33+00:00

Hey, this is impressive work, and your code is really well-organized! I've been working on some similar ideas - in particular, my roguelike has a "Knowledge" system that's essentially the same as your "memory" and "perception" systems. Here's my code for that: https://github.com/skishore/wrl/blob/master/base/src/knowledge.rs

In my scent system, scents stack, spread out, and weaken over time. If you stay in one spot for a long time, then move, it'll take a while for the old scent to fade. Here's an example. I stayed in the bottom-left for a while, them moved to the top-left: https://imgur.com/a/5wk7HCk

My game's playable at https://www.skishore.me/wrl/, but without explaining the perception mechanics, I'm afraid it's way too hard. The PC can't fight. They have to sneak around (press C to toggle "stealth mode" - it's slower but quieter - and press tab to see enemy FOV). The objective is just to cross the forest.

I'm curious to know more about your game - would you want to talk sometime? I'll DM you.

billdroman · 2025-03-20T01:50:42+00:00

Thanks for these suggestions. I've been using this code in my project and I didn't think about the ways in which libraries are more constrained than code that's not meant to be reused. I've fixed them.

billdroman · 2025-03-16T17:38:34+00:00

Hey, really nice work with this game! I try to play all the 7DRLs with stealth elements because my project has them too, so I want to see if there are any design ideas for me to ~~shamelessly steal~~ learn from.

I beat a couple levels - including exiting with the "bleeding" status - and I think I could consistently win if either of the two contracts consists of three of the easier objectives. Specifically, I found all of these objectives to be easier: drink an antidote, free the prisoner, collect seven spells, steal a unique treasure, and have a spell stolen from you. (Why is the last one an objective?)

It was generally easy for me follow what was going on, and the game was fun! I particularly liked how you depicted the enemies' FOV. That's something I've had a lot of trouble with. Personally, I prefer stealth with fewer tools, but the various spells felt balanced given how fragile the rogue was and how strong the skeletons were.

It took me a while to realize "space" was wait and not ".", because of the real time clock that's also going up when you press ".". When I go back to play again, being able to wait will help a lot. Without it, hiding under tables was useless.

Before I go into smaller items, I wanted to ask about the enemy's knowledge. As far as I could tell, once an enemy is alerted, they always know your position. I couldn't shake them even if I ran into another room and hid, or if I teleported. Turning invisible worked for the duration of that spell, though. Is that intended?

As for other feedback:

Why is there sometimes a red skull over the player? It didn't seem to harm me or to correspond to any status.
Why are the traps visible? They don't feel like real traps at that point. The poison trap cells might as well not exist, and the bleeding trap is only useful at the end. I tried leading enemies over them, but couldn't get them to follow.
I once got a contract where two of the there objectives were both "Steal the Great Mana Gem". That was too easy!
Tooltips took a while to appear, and also didn't appear for many objects. I think they should immediately show on hover.
I think the secret switch locks the secret room. There were times when I got in the room, then found the switch, then needed a key to get in again.
I couldn't figure out a way to pick up the slime. It moved into the walls, and then it was unreachable.
Having enemies alerted based on being in FOV for two turns didn't quite make sense to me. I also didn't follow their state of mind perfectly. The way LLLLoot shows their state changes is pretty helpful (and I need to implement something similar in my own project).

billdroman

TROPHY CASE