This blog series is a part of the write-up assignments of my A.I. for Games class in the Master of Entertainment Arts & Engineering program at University of Utah. The series will focus on implementing different kinds of A.I. algorithms in C++ with the openFrameworks library, following most of the topics in the book Artificial Intelligence for Games by Ian Millington and John Funge.
In this post, I will talk about my implementation of the blackboard structure to be used with my behavior tree, but also compatible with other decision-making behaviors. There are a ton of different approaches to implementing a blackboard structure. Depending on the target platform and the engine structure, they can be very different from each other. What I did in my AI engine is a more flexible version, but sadly, not the most memory friendly one.
What is a Blackboard
As the name indicates, a blackboard data structure is something with centralized information that allows different parties to read/write information from/to. Note that the different parties don’t necessarily need to be AI agents, they can be individual pawn agents, some strategic AI, or just a piece of codes.
The purpose of the blackboard is to provide a clean, convenient and centralized space for others to access some relevant data.
I have read through the source codes of Unreal Engine 4’s source codes of their blackboard, which is a tightly packed data structure that optimizes memory space, and used it as a reference for my own implementation.
In my structure, the blackboard entries and the underlying containers are split into three different scopes, one for global scope, one for tree scope, and one for the tree-task scope. By doing this, we allow different trees to write the same information (currently opened tasks, currently running children tasks of tasks) onto the same blackboard without conflicting with each other. However, this also means that the size of our blackboard data might be dynamically changing or needs to be sufficiently big enough for the trees that are using it. However, this provides much bigger flexibility and allows different decision-making algorithms to use it without having to worry about setting up all the entry at construction.
One important function of the entries is the ToString() function. This this the one function that we use run-time type information to get the entry’s data type and create a unique string as a key to use in our blackboard.
The ToString() function of cBlackboardEntry_TreeTask looks like this.
The interface of the blackboard class is pretty simple. It allows the add key, get value, and set value operations for different scopes with function overloading. Inside those operations, you can see that it is actually calling the corresponding functions in the cBlackboardData class to perform operations on the correct scopes. This is because I use the underlying cBlackboardData as the actual container, by doing it this way, I can change the actual container implementation in the future if I want, or maybe switching between containers for different target platform/hardware.
Blackboard Data Container Class
In my blackboard data class, the underlying data is stored with three unordered maps along with three arrays (with void*) which contain the actual data of different data types. The unordered maps store the offsets of the corresponding entry inside the arrays from the beginning memory location. How the get/set/add key operations are actually performed will be explained later.
In the implementation of the get/set/add key operations below, you can see how the underlying memory operation is done. Given an entry, we will first get the string key value from it, and then use it to search the unordered maps. If we cannot find that entry in the maps, my current implementation will automatically create a new one and set it with the default value of that data type. Once we retrieve a key-value pair from the maps, we calculate the correct memory location with the offset in the key-value pair and cast that memory location to our data type to perform get/set action accordingly.