New Year, New Series, Old Tech - Battletech AI [Part 1/??]: Introduction to Behavior Trees

Back in 2016, I got hired at Harebrained Schemes to be the AI engineer for their upcoming PC turn-based squad-based strategy mech combat game. I got pretty wide room to build whatever system I thought would work, but there were constraints, based on the game we were making:

• Turn Based - a constraint or a liberty, I had a bunch of time (maybe a second?) to make a choice per unit per turn. This meant I could choose an action, but the expectation of quality was higher than an action game
• Squad Based - the AI units had to feel like they were working together as a group of up to four units, typically with some military training.
• Mech - the fiction was that these were big combat rigs, with human pilots inside. There was not freedom to write off bad decisions as robots being robots or alien brains.
• Combat - the AI needed to focus on, and have competency in, fighting. Being aggressive, starting fights, taking the enemy out when possible.
• Game - implicit, but worth calling out, the requirement is that the decisions were good, but "perfect" gameplay was an anti-requirement. We don't want to keep the player from winning altogether. 

In my initial conversations with Kevin, the designer that I would be working with, we talked about having a "playbook", where certain configurations of units (my units look like this, the enemy units are laid out like that) would lead to certain pre-scripted plans (from this configuration, we should try to flank to the left).

I pushed back on this. My gut feeling was that the number of configurations we'd have to set up, the number of scripted reactions, would be way too high. I was worried about matching the current state to a known input state in our playbook. I was worried that the scripted responses would feel too canned, and also that the response scripts would need to be interrupted as the player reacted.

Perhaps we could have made this work, but it didn't feel like a path to responsive, satisfying gameplay.

My mind went back to previous work I had done, working with Pattie Maes' Activation Nets for my thesis, which I knew had evolved into C4, which I hadn't done anything with. I chatted with Damian Isla at GDC, who got me thinking about Behavior Trees, which he had used on the Halo 2 AI, and he had given a GDC talk about them, so that felt promising.

My experience with most AI architectures is that the idea is simple, and the complexity comes in implementation. Consistent with that, Behavior Trees are an easy idea - decompose the big behavior space you want to work in, down to a small amount of actions, some of which might be alternative ways of accomplishing a goal. If I'm hungry, I have a goal to feed myself, which could be satisfied by making a sandwich or reheating a slice of pizza from last night, or getting ingredients from the store, and cooking a meal. These actions themselves might break down into tasks (going to the store, buying a list of items, coming back home, preparing the meal). Importantly, Behavior Trees provide structural support for a task failing. If I wanted to reheat the pizza, but my roommate had finished it all off, that task would not work, and I'd have to do a different option.

Lots of different people have made lots of different Behavior Tree implementations, and from my research, most of those implementations were targeting realtime, not turn-based use cases. This means that my implementation might better be called a "decision tree", a glorified flowchart that cascades down the tree, ultimately resulting in a set of orders that the AI hands to the game for the game to execute.

This isn't (just) a pedantic notational quibble - if you're doing realtime control, using Behavior Trees, you're going to want to be aware of ongoing actions and handle changing situations. Because BattleTech is turn-based, I had the luxury of doing a fresh calculation each turn for each unit.

At the time that I started, one of my friends and coworkers, Andy, had set up a small Unity project with existing Mech assets (thanks to an agreement to work with Catalyst who had a bunch of Mech models). Shortly after coming back from GDC, I hacked together a pretty tiny Behavior Tree as a proof of concept, where the mechs would walk toward player-controlled units, and fire some weapons. It wasn't a lot, but it showed all involved that this was a system that could work, and I could improve it to meet our requirements.

Next up: more depth on Behavior Trees