Behavior Trees for Meta Progression

Overview

After having established a decent set of systems for a full run (the game alternates between runs and a hub world the player returns to between them) it was time to implement meta progression and have the world state be driven by it.

I have always wondered, when playing big games, how fun and challenging it would be to manage the state of the world, especially when the triggers for its update branch. Obviously, for a roguelike, the system didn't need to be complex, but it still needed to be properly implemented in a way that was solid, designer friendly, and scalable.

My first thought was to create a Graph-based Event Flags System that is visualized using the editor. The idea sounded ambitious and doable. The issue was the scale of the tool, and, more importantly, the many similarities it would have with my already well maintained Behavior Tree System. I had an epiphany that I couldn't ignore.

System Structure

The system I imagined needed 3 parts to work properly: a flags/counters system that saves data persistently on the player's device, an API for other systems to set values to the flags, and a few BT nodes that can be used to design the flow and effects of those flags. The implementation, however, wasn't as straightforward as I thought it would be.

Flags Storage

Storing flags locally creates a little tradeoff. Plain files are easy for users to modify, which is less an anti-cheat concern than a bug reporting one, while obfuscated files are hard for us to debug.

Fortunately, I had heard about a technique called JSON Web Signature (JWS) which includes a header metadata, payload (or the data), and a signature which authenticates the payload. The signature is a cryptographic hash that is generated using a secret key in the app that gets obfuscated when the app is built. This doesn't guarantee security against seasoned nerds, but it makes tampering with the data a little bit harder.

The first line of the file is the signature, and the rest is the data it signs. There's a full example in the Debuggability section below.

That solved the issue and was surprisingly easy to implement. Every save creates a save file and a backup save file, that way, any signature mismatch will reject the file and use the backup file as a fallback. If both are corrupted or missing, then a new fresh one is created.

All the flags in the system are ScriptableObjects which makes it easy to reference them in other systems. This design made it easy to create the API calls that other systems can use to set flag values like the QuestManager to set flags when a quest is completed, ShopsManager to set flags when certain items are purchased, CombatManager when certain enemies/bosses are defeated, etc.

BT Custom Nodes

The most important piece of the puzzle is orchestrating all the above and having it produce gameplay value. Surprisingly, at least for the scope of the project and its systems, I only needed a handful of nodes to have this work and properly time how and when the BT runs.

Placed first in a Sequence, a CheckWorldStateFlags or CheckWorldStateCounters node acts as a guard: if it fails, the rest of the Sequence never runs.

BT Structure

Since most of the changes apply to the run mode (as opposed to the hub world), and since most (if not all) flags have to have their values set during the run, it was a natural move to have the BT evaluate the world state in the hub world.

The World State Evaluation BT runs every time the player enters the hub world. It starts with ResetWorldStateManagers, which clears what the previous evaluation gave the managers (quests, shop items, NPCs and their dialogue) so nothing gets added twice. A Parallel node then evaluates every quest line side by side, since they're independent from one another, and EndWorldStateEvaluation marks the end of the evaluation.

Each quest line is a Selector with one Sequence per step, in the same order the player goes through them. Every step starts with a CheckWorldStateFlags node that checks the step isn't done yet. The Selector runs the first unfinished step and skips the rest, so the tree reads left to right like the quest line itself.

Problems

This was such a beautiful idea in theory and in my head when I was away from my computer, but as I started implementing and testing it, a few flaws appeared. Some were critical, while others could be avoided by setting constraints on how the progression is designed:

1. If evaluation occurs in the hub world every time, it is inevitable that flag effects repeat, resulting in duplicate quests, shop items, etc.
2. Some flags are set in the hub world after the world state has been evaluated, so any consequences of the flag getting set won't take place until the player revisits the hub world.
3. Setting a flag in the World State Evaluation BT can sometimes be necessary e.g. to have a flag be set once a number of branches' flags are all set, so that other branches can just check for the one flag instead of checking the list of flags that set that one flag. The problem with that is the order of execution. If a CheckWorldStateFlags or CheckWorldStateCounters node checks for the one flag before the branch that sets that flag's value executes, it will fail and skip the branch, even though all the requirements to set that flag are in place, they just haven't been executed yet.

Solutions

Fortunately, all these were easy to tackle:

1. To avoid repeating effects, managers that get their data from the World State Evaluation BT reset that data on every evaluation, or at least reset the specific data that the World State Evaluator modifies.
2. To have the hub world's flags that are set after the World State Evaluation take effect, the BT executes ResetWorldStateManagers first, before anything else.
3. This is already partially resolved by adding the data reset node at the start of the BT. All that's left to do is have flags that are set in the BT trigger the BT to restart, which can be a part of the node itself, and it should trigger only if a new value is set to the flag.

Outcome

With this rather simple system in place, developers and designers alike are now able to add quests, story and meta progression en masse rather easily.

Example

The example below demonstrates how the system works. It also served as the test case while I was building it.

Expected sequence

• The player needs to find the Drone NPC in the hub world and speak to it (exhaust its dialogue). The NPC will tell the player that towers (an enemy type in the game) are evil and that the player needs to take them down.
• A new quest for destroying 5 towers in total is added to the active quests.
• After the player destroys the 5 towers (in one run or across multiple runs), they will need to speak to the Drone NPC again, which, upon exhausting its dialogue, will tell the player that towers are multiplying in numbers and that the player needs to destroy 5 of them in one run.
• A new quest for destroying 5 towers in one run is added to the active quests.
• After the player destroys the 5 towers in one run, they will need to speak to the NPC one more time, where they're presented with a choice to keep the quests they were assigned to a secret. Agreeing to this choice rewards the player with coins and removes the Drone NPC from the world.

Implementation

By the way the sequence is set, a few flags and counters are needed, as well as a few calls from the QuestManager, NPCsManager, and DialogueManager.

Flags:

• NPC_DRONE_SPK_01 = false
• NPC_DRONE_SPK_02 = false
• QST_DST_TOWER_5_COMPLT = false
• QST_DST_SAMERUN_5_COMPLT = false
• DIALOGUE_OPT_DRONE_ENDQST = false

Counters:

• QST_DST_TOWER_5 = 0
• QST_DST_SAMERUN_5 = 0

BT structure

The Drone's quest line is a Selector with five steps:

1. NPC_DRONE_SPK_01 is false: add the Drone and its first line. Speaking to it sets the flag.
2. QST_DST_TOWER_5_COMPLT is false: add the "destroy 5 towers" quest. The CombatManager increments QST_DST_TOWER_5 during runs, and the QuestManager sets the flag once it reaches 5.
3. NPC_DRONE_SPK_02 is false: give the Drone its second line. Speaking to it sets the flag.
4. QST_DST_SAMERUN_5_COMPLT is false: add the "destroy 5 towers in one run" quest. QST_DST_SAMERUN_5 counts within a single run, and the QuestManager sets the flag when the quest is done, so the outcome persists while the count itself doesn't need to.
5. DIALOGUE_OPT_DRONE_ENDQST is false: add the final dialogue with the secrecy choice. Accepting it rewards coins and sets the flag.

Once that last flag is set, every check fails, the Selector fails, and the quest line is over without any extra node to end it.

None of this would require any new code. The flags, counters, quests and dialogue pieces are assets, and the logic is assembled in the BT asset, so a designer can create and tweak progression without a programmer.

The beauty of this system is that the world starts off the way it is in the editor and is built piece by piece based on the world state.

Debuggability

Since the system is a combination of a behavior tree and a set of flags and counters, I can debug the world state by viewing the behavior tree live and checking the local file holding the flag values.

Here's the save file right after the player finishes the Drone quest line from the Example above. The first line is the signature:

kQ7rT2xNfV9bLs4HcZ1pWm8YdE3uJa6oRgX0tBiCv5s=
{
    "SchemaVersion": 1,
    "ProfileId": "",
    "LastSavedUtcTicks": 639287208004213377,
    "BoolFlags": [
        {
            "Id": "a3f19c7e52d04b8e9c1f6d2a7b4e0c58",
            "DebugName": "NPC_DRONE_SPK_01",
            "Value": true
        },
        {
            "Id": "7c2e8b41f9a64d03b5e7a1c9d8f2463b",
            "DebugName": "QST_DST_TOWER_5_COMPLT",
            "Value": true
        },
        {
            "Id": "e96d4a0b3c7f42e1a8b5d9f0c2e7316a",
            "DebugName": "NPC_DRONE_SPK_02",
            "Value": true
        },
        {
            "Id": "1b8f5e2d6a9c47f0b3d1e8a4c7f9025d",
            "DebugName": "QST_DST_SAMERUN_5_COMPLT",
            "Value": true
        },
        {
            "Id": "d4a7c3e9b1f8460da2e5c7b9f3d1684e",
            "DebugName": "DIALOGUE_OPT_DRONE_ENDQST",
            "Value": true
        }
    ],
    "IntCounters": [
        {
            "Id": "5904375b06586af41bd4c25aedc0b193",
            "DebugName": "QST_DST_TOWER_5",
            "Value": 5
        }
    ],
    "CompletedEventIds": []
}

Future Improvements

• Having a parent flag enabled once a set of flags are set makes designers' lives easier, but it has an issue when pushing updates. If the set of required flags ever extends or changes after a player has already unlocked the parent flag, the changes won't apply because the parent flag value lives on the player's disk. A solution would be versioning every flag: in such cases I would change the version of the parent flag, which resets its value on the player's disk if it exists there.