AI: Overworld Adventures Test

This week I’ve prepared the “Overworld Adventures” testbed, which will be use to test out behavior trees + utility AI.

Here’s a video:

The map is a pre-alpha visualisation of the overworld map (no tiles yet for environment, sorry). There is the hero sprite (centered), the dungeon tiles (stairs) and the cities (shop tile). The hero wanders in dungeons, tries to kill monsters to get coins, and then goes to the cities to spend coins to heal and buy equipment (which increases health and power). The battle is “hero attacks, if enemy not dead, enemy attacks” , where attacks do Nd6 damage, where N=power. When the hero dies,  another is respawned. Heroes start with (power=5, health=50, coins=0) and dungeons contain one of four monster variants: (power=1/5/10/50, health=10/100/1000/10000, coins=power). I spawn 1000 dungeons and 100 cities, and new dungeons are spawned every several turns.

As explained above, the hero party is pretty dumb, so they get killed after a few dungeon runs, as they’ll encounter and try to tackle a difficult dungeon. The behavior tree is all specified and I’m currently about to add the utility AI logic.

Depending on how much time that takes, next step is even more exciting: a hunger clock! Cities will sell rations, coins can be spent on rations, walking the land costs rations, and decision need to be … rational, as when heroes run out of rations they die. I’ll implement some sort of score bookkeeping to see how the AI performs (aka how long it lasts before dying). Extra bits are proper pathfinding and visibility, as the hero currently knows all.

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!

AI: Blackboard and Input Cache

As I’ve been working towards the first Utility AI test, I decided to fix my poor implementation of a Blackboard class.  My blackboard is loosely based on this concept; it’s an intermediate storage of the decisions and calculations of the AI system, for example:

  • Where’s the closest enemy?
  • How many enemies are within melee distance?
  • Is my health at a critical level?

Before, it was effectively a bunch of map<string, DataType >, and I used strings to access. Of course accessing maps all the time is going to be deadly to performance if I’m doing hundreds/thousands of accesses per turn, so I wanted to switch to a more future-proof, efficient system, which has the performance of enums, without having to recompile when I’m adding stuff.

The new system uses the following semantics:

  • Property: A name for a blackboard entry, e.g. “ClosestEnemy”
  • PropertyGroup:  The group that a property belongs. All properties within a group have a single type. E.g. “Distance”
  • PropertyMap: A map of property group names to properties, implemented as a vector<vector<string>>. One entry is special and contains a list of property groups. This is stored in the global registry.
  • PropertyIndex: a pair (group_index, property_index). This is used to uniquely identify a property of a group

Now the blackboard is effectively a vector< pair< vector<T> /*property values*/, int /*group*/> >, and I’m using PropertyIndex to access it.

So,  we create the property index once from strings (e.g. specified in JSON) and we’re using the indices for fast access. One potential downside is that if we want to have only one property set for a group, and that property has an index of 10, we then need to allocate all 11 elements.  But this can be easily solved by putting the property in its own group.

Blackboards need to be filled explicitly. Then, there’s the Input Cache, which is my implementation of an automatically filled blackboard. From my last post regarding Utility AI , this would be the storage and calculation logic of values, which are the inputs to the response curves. So, these values behave exactly like a blackboard, but they’re just limited to be floats only, in range [0,1], and I should provide an automatic way to calculate these values if required. So, this can reuse the above mentioned machinery: fetching a value from the input cache is done simply by using a PropertyIndex, as the Input Cache uses its own group to store the float values.

Next time, a decision example of a lumberjack shooting an endless horde of wolves, deciding upon a use of a shotgun, a pistol, a knife and idling using Utility AI.