AI Rework - Queue-Based Interruptible Behaviour Forests

Haven't done a tech post before, but I've been working on rebuilding the AI systems this week and thought I came up with something  worth sharing since I haven't seen this idea proposed anywhere before. This post will probably not make very much sense to you if you haven't touched AI systems in games before. 

I'm almost certain someone out there has probably put this together before, just that whoever that is has not shared it with everyone else. Or it's been buried under the rest of the internet, as is usually the case. It doesn't quite neatly fall under any of the well-known AI techniques, but it's very simple in concept that I would genuinely be surprised if there isn't anything published about this whatsoever. 

The video above probably doesn't look any different from previous gameplay, but there are some new fixes and changes, like how Louise can now sprint towards you as part of using the attack before actually playing the attack animation. 

Why Rework the AI System?

So previously, I've been using Unity's new Behaviour package for these reasons:

1. It has a nicer UI than other BTs I've tried (...that is, until you start to require lots of fields on a node). 
2. It's officially supported. (but then they laid off the original team...?)
3. It supports running multiple graphs together (This is how I'm handling enemy block responses. You attack which fires an event, and they send that event to trigger a new subgraph of the entire graph. Whether it succeeds or not depends on the animation lock systems.)

(3) is probably the most important one here, since I'm taking more inspiration from Sekiro's bosses which are able to block and react to the player's actions, so there needs to be a system to allow for interruptions. This is where Behaviour Trees in general tend to fall apart, because there's no easy way to specify an action that overrides actions evaluated later on, and my system is quite hacky in the sense that it's just trying to interrupt each other in messy ways. 

Another issue I was facing with Unity's Behaviour was that it was just not performing well enough, especially on Nia's boss fight. I thought it was the fog effects at first, but I found that there is a significant amount of GC whenever the graph is restarted, and simply disabling the boss returned the frame rate from ~60 back up to ~240. Not too sure of the issue, and it could just be a user issue since I heavily customized some modifiers to provide a form of utility-based weighted random action selection, but it's bad enough that I couldn't continue with this solution. 

Looking at AI and Game's Dark Souls AI video, they apparently use Hierarchical Planners, which is something that I don't have any knowledge on myself. I don't really get how goals and subgoals function exactly, but there is a concept here of planning out actions and interrupting them based on the weights of each individual goal. Honestly, even as a programmer main I can't really make much sense of what's going on in these AI scripts, and I didn't want to give up the sequencing features of Behaviour Trees, so I tried to just smash them together. 

Specifically, for my game's requirements:

• Bosses have a lot of attacks and combos - some kind of action sequencing is required, and the easier it is to author  these, the better. 
• The entire game is purely on duels, so there's no need for patrol states or stealth alerting stuff. 
• AI must also be able to react to events, specifically player actions. Like in the Souls series, this should let them queue up a specific response action. (Like Godskin Apostle throwing his projectile as soon as you start healing in Elden Ring). 

The Idea: Action Queues & Interruptible Behaviour Forests

So, what I came up with was to take the concept of branches from BTs, and then just jam it all into a queue. The core concept is basically:

"Decide what you want to do and queue it up all at once, but if anything requires you to do something else just try to do that instead and forget about your original queue if you succeed in doing that."

What this means is that you have a set of Sequences of Actions, and they have some conditions or weight attached to them which are used to decide what to queue up. This is fundamentally the same as a branch in a Behaviour Tree, just that instead of storing them all in one graph, each branch is just stored as a list.

(Note: by queueing it all up at once, it reduces a lot of complexity since I don't need to care what Sequence I'm currently on, unless I'm holding onto another Sequence to override the current queue)

The important part comes from the action queue, because it allows you to essentially draw paths from any branch to any other branch, whereas a typical BT implementation would have the branches be mostly static. For example:

1. We have queued up the actions [A, B, C] as part of a sequence chosen by the AI. 
2. A is popped and is currently running. We now try to override the queue with a new sequence [D, E, F] from some other component in response to some other event.
3. When A completes and releases the animation lock, D is given priority to run over B and evaluated first, which manages to start. We then replace the remaining queue [B, C] with the remaining actions in the overriding sequence [E, F].
4. The final order of actions performed are [A, D, E, F]. 

Essentially, this chops up the branches of a BT and makes a behaviour forest, and now you can walk from any node in any branch to any other branch. Technically, this could be used for absolutely any event in the game if you write a way to link it up, so it makes the whole AI system extremely versatile. Blocking/dodging attacks, following up with even more branching behaviour, or just reacting to specific player actions all becomes possible in a way that just isn't easily possible for a BT. 

Obviously, this might not be scalable for a more complex AI doing cover or simulations, but as far as an action game boss AI that just wants to be able to react to player actions and perform (possibly branching) sequences of actions, this is perfect. 

Branching

In the above example, the overriding sequence replaces the current queue. But since it's just a LinkedList queue at the end of the day, we can always just insert more nodes at the start of the queue. So a Branch node that essentially holds a mini-sequence selector for actions can choose which action to queue up just like how the main behaviour chooses Sequences to run. Example:

1. Queue: [A, B, C] where B = Choose(D, E) (WLOG, assume D is chosen here)
2. A is executed, B is popped. Queue is now [C].
3. B is executed, which inserts D at the start of the queue. Queue is now [D, C]. 
4. Final actions executed are [A, D, C]. (Excluding B, since its only function is to push D onto the queue.)

Algorithm

Action: anything. I have this as an abstract class with bool Perform(agent) as the only method.
Sequence: An ordered list of actions to be queued up when this is selected. 
AI Runner: the component that manages the action states. 
Blackboard: holds data that is accessible by all actions through the AI agent. Video reference by git-amend.

Update Method:

1. Run any pre-computations. Things like distance calculations, etc. that can be shared across all actions. 
2. If the current action state is invalid, try to pop the next action from the queue if there is any. 
3. Decide on the overriding sequence to use. (In my case, I have a PriorityQueue that just takes the highest priority and ignores the rest.)
4. Update the action state.
   1. This updates timers and attempts to run the action, or will mark it as cancelled and clear the associated sequences if it timed out/failed.
   2. There can be a timeout for attempting to start, and a timeout for how long an action can be activated for. 
   3. If the overriding action was successful, then replace the  queue with the overriding sequence. (Queue up all the actions except for the first one, which just succeeded). Replace the current action state with the overriding action's state. 
   4. Mark the current update as having been overriden. (Since we evaluate overrides first and then the current node, if we don't have a flag for this we end up evaluating the override action twice.)
5. If the  runner is allowed to self-select the next sequence, then choose the next sequence and enqueue it. (This is useful for making the AI stay passive for a bit, such as after getting hit by something).

Other Extensions:

Priority Sequences - things that should be enqueued as long as they are available. Use conditions to control these. 
Example: if the AI doesn't have a target, then it should try to run the sequence with Find Target Action. 

Utility AI - just needs to be part of the selection process. 

Running into position before starting an attack - this is a built-in behaviour for my main attack action that allows it to set a desired range and a movement strategy. If it gets to that range during the attempt timeout, then it'll start the attack, otherwise it'll fail and try something else. 

tl;dr

Use an action queue, and the initial decision for what goes into that queue is enforced to be a shallow tree. 

Expose functionality for modifying that queue at runtime to enable the AI to react to things dynamically.