AI: Preparing a Behavior Tree + Utility

Well, while I said last time that there would be a rampaging lumberjack shooting down wolves, I’m not showing anything, as the results were bugged. The idea was that the lumberjack could choose between a knife (melee, very fast), a pistol (ranged, fast) and a shotgun (ranged, slow, AoE) to kill an endless horde of approaching wolves. Turns out that the AI was either using shotgun all the time, or a combination of knife-and pistol. Something somewhere was flawed, but instead of trying to solve this and scrap it, I chose to create another example, which is 1) a bit closer to the game’s concept 2) a bit more complex 3) a bit more interesting, 4) it will use a combination of behavior trees and utility AI and 5) it can use the overworld map that I’ve generated.

I’ve been thinking and thinking, and the more I’m thinking, the more it makes sense to combine a behavior tree (btree) and utility AI. It makes a lot of sense, as a behavior tree is good as an overall AI system (better than FSM) and utility AI is good for decisions, Utility AI will be used for (and wrapped in) Selector nodes, which are nodes that, on Tick(), select one of their children nodes and execute it.


There are a number of cities and dungeons scattered throughout the overworld. New dungeons spawn every so often. Monsters lurk in the dungeons, carrying treasure. A party of heroes wanders around the land and clears the dungeons. Cities can be used for healing or buying equipment (improving power and health). When a party of heroes dies, a new party is spawned.


So, here’s the interesting bit. I plan to implement a behavior tree that will look like this:

  • SelectGeneralBehavior (Selector node using Utility AI — the btree root node)
    • RetreatToSafety (score based on current health and relative power of enemy.)
    • Battle (score based on whether we’re in a dungeon or ambushed, and with ok health and relative power balance)
    • VisitStores (score based on amount of gold and proximity to city)
    • RaidDungeon (score based on proximity to dungeon , current health status and dungeon difficulty if known)
    • Idle (flat, really low score, if nothing better todo. E.g. when without money, full health and no dungeons around)

The tree is processed from the beginning every time we Tick(). Because, we only tick when an action has finished, or has been interrupted. Also, contrary to some other examples that I’ve seen somewhere, an action would not be “Go from A to B”, as this is a compound really; it implies scheduling and executing several “move” commands. In my case, an action is a unit action: something that cannot be broken down any further, e.g. MoveLeft, or Attack.

Above, every sub-entry is a subtree itself. Here they are, as I currently envision them

  • RetreatToSafety (sequence node)
    • HaveMoney
    • VisitTemple (subtree – only executes if we have any money)
  • VisitTemple
    • BlackboardEvaluate< SelectCity > (write= “path_to_entity”) // Look in the blackboard for “path_to_entity”; if not found, or it’s found but not a city, calculate it. This could be used later on other criteria for which is the best city, but for now pick the closest.
    • TravelToEntity (sequence node)
    • ACTION: Heal (only executes if we’re at the city)
  • TravelToEntity (sequence node)
    • BlackboardEvaluate< CalcPathToEntity > ( write = “active_path”, path_to =“path_to_entity”) // Look in the blackboard for “active_path”; if not found, calculate a path to “path_to_entity” and write it to “active_path”. This creates a path from where we are to “path_to” entity.  Note: if path is calculated, but we’re not on the path, then “active_path” needs to be invalidated, so that it can be renewed
    • ACTION: Move a tile along path // If it fails, fail node
  • VisitStores (sequence node)

    • TravelToCity (sequence node)
    • ACTION: Buy equipment (only executes if we’re at the city)
  • RaidDungeon  // just travels to a dungeon tile. SelectGeneralBehavior should do the rest
    • BlackboardEvaluate< SelectDungeon > (write= “path_to_entity”) // Look in the blackboard for “target_dungeon”; if not found, or it’s found but not a dungeon, calculate it. Criteria for selection would be dungeon level (if known) and proximity
    • TravelToEntity (sequence node)
    • RecordDungeonLevel // This is an instant action that, having arrived at the dungeon, it inspects what enemies are there and records it as the “level” of the dungeon. This would be useful when running SelectDungeon, so that e.g. we would avoid very high level dungeons.
  • Battle
    • ACTION: Attack // We’re here either when at a non-empty dungeon, or ambushed.  Will figure out how to implement some basic attack/retaliation thing between the party and the enemies.


So, that’s the high level plan. I’ve been working on the behavior tree machinery and the integration with the utility system, as well as some deep cloning code bug fixes, so it has been framework code so far. I’ve done a few unit tests and things seem to be working, so now towards something more concrete!

2 thoughts on “AI: Preparing a Behavior Tree + Utility

Leave a Reply

Your email address will not be published. Required fields are marked *