One of the projects I have been fantasizing about for the longest time is modular memory-driven task-bots. The ultimate goal was to create inhabitants in a world which could act independently and collectively.

Having programmed world-generators before, I wanted to populate the world with generic bots utilizing an AI that would dictate their behaviors and interactions. This way the world could grow in detail by allowing actors to enact on it.

I had already implemented the basic outline of a task pipeline in Javascript (because it made my life easier), but I wanted something more robust and scale-able, so I did this project in C++. I was prompted by the procedural-garden contest on the subreddit /r/proceduralgeneration to retry this (hence the theme).

With my approach, there are three components to the simulation: A world, a population and a set of actions to bind them together. I thereby had three models to create, and all three of them are explained in more detail below.

As an added difficulty I wanted the actors to retain information about previous interactions with the world, and use their knowledge about those interactions to influence their future actions.

With my world-model, I took the easy way out and just used Perlin-Noise to place water on a surface. All other objects in the world were simply placed completely randomly.

For my population model (and their “memory”) I simply made a class with a few characteristics and a location. This was going to be a lo-res simulation. The memory is a queue, where the bots look around, save information from their surroundings, push it in and manage this queue to interpret their memory.

For the actions binding these two together, I wanted to create a framework of primitive tasks inside a hierarchical task-queue system so individual entities could perform complex behaviors in a world.

I decided a good test model to guarantee the robustness of base functions (and the task-queue system in general) and thereby prevent memory-leaks (there were plenty) was a pile of ants in the grass … harvesting leaves.

I want to describe in more detail the structure of the task and memory systems, and to show how I build complexity from (mostly) robust primitive base functions. I also want to show some of the (not so) fun “ant-memory-leaks” you encounter while trying to figure out why they’re running in circles frantically looking for grass, or standing still and making my program lag.

General Structure

I wrote this in C++ using SDL2 for rendering (I had already written myself a little view-class for SLD2 previously). I also use a (slightly modified) A* implementation I found on github, because my implementation was irretrievably slow, and I couldn’t see why.

The map is simply a 100×100 grid with two layers – a floor layer (for path-finding purposes) and a fill layer (for interaction objectives and path-finding). The world class also handles a few cosmetic features, such regrowth of grass and vegetation. I say this now because these are the only parts that I won’t be covering in this article.

The Population

The bots were a class with a few properties describing the individual. Some of these were cosmetic, but others influenced the way they performed their actions (such as if they can fly, their view distance, what they eat, what they’re carrying, etc.).

Most important were a series of helper quantities that determine the behavior. These were: a vector containing their current A* path, so it doesn’t have to be recalculated every tick (this saves computation time and allows simulation of more bots) and: a queue of memories, which dictates how they interpret their surroundings.

Memory Queue

The memory queue was designed as a simple queue containing a set of memory objects, limited in size by a property of the bot. Each time new memories were added, they were pushed in the front, while anything hanging off the back was cut off. This way, memories could be more “fresh” than others.

If a bot wanted to recall information from memory, he would construct a memory object (a query) and compare it to those in memory. The recall function then returned a vector of memories that matched any or all of the criteria specified in the query.

class Memory{
  public:
    //Recall Score
    int recallScore = 1;

    //Memory Queryable? Array
    bool queryable[4] = {false, false, false, false};

    //Memory Attributes
    std::string object;
    std::string task;
    Point location;
    bool reachable;

Memories consist of a simple object containing a few properties. These properties of a memory are considered “associated” with each other. Each memory is also given a quantity “recallScore”, which iterates each time a memory is recalled by the recall function. Every time the bot recalls memories, it does a single-pass sort over the queue from the back, switching the order of memories if the recallScore of the older memory is higher than that of the new one. This way, some memories could be more “important” (for large memory sizes), and retain their place inside the queue longer. Over time, they would be pushed out by new ones.

Memory Queries

I also added a few overloaded operators to this class, so I could do direct comparisons between the memory queue and a query, comparing “any” or “all” properties, and so when overwriting a memory it only overwrites the properties specified. This way we can have a memory of an object associated with a location, but if we look there again and the object missing, we can update our memory by overwriting it with a memory containing the new fill-tile using a query matching the location.

void Bot::updateMemory(Memory &query, bool all, Memory &memory){
  //Loop through all existing Memories
  //"memories" queue is a member of Bot 
  for(unsigned int i = 0; i < memories.size(); i++){
    //If all matches are required and we have all matches
    if(all && (memories[i] == query)){
      //We have a memory that needs to be updated
      memories[i] = memory;
      continue;
    }
    //If not all matches are required and any query elements are contained
    else if(!all && (memories[i] || query)){
      //When overwriting, only overwrite specified quantities
      memories[i] = memory;
      continue;
    }
  }
}

I learned a lot trying to program this system.

The Task System

The nature of the game- or rendering-loop is that for every tick, the exact same functions are executed repeatedly, although I specifically want non-cyclic behavior in my bots.

Here I explain two approaches to viewing the structure of the task system, designed to counter this effect.

Bottom-Up Outlook

From the bottom up, I decided to approach this by constructing a set of “primitive actions” for the bots to perform, which each individually only last for a single tick. With a good library of primitive functions it should be possible to combine them into a complicated action consisting of many primitive actions.

These primitive actions are for instance:

//Primitives
bool wait(Garden &garden, Population &population, int (&arguments)[10]);
bool look(Garden &garden, Population &population, int (&arguments)[10]);
bool step(Garden &garden, Population &population, int (&arguments)[10]);
bool swap(Garden &garden, Population &population, int (&arguments)[10]);
bool store(Garden &garden, Population &population, int (&arguments)[10]);
bool consume(Garden &garden, Population &population, int (&arguments)[10]);
bool move(Garden &garden, Population &population, int (&arguments)[10]);

//Continue with secondaries here...

Note that these actions contain reference to both the world and population, such that they can alter them. Here:

• Wait makes you do nothing for that tick.
• Look parses your surroundings and pushes new memories into your queue.
• Swap takes the item in your hand and replaces it with the one on the ground.
• Consume destroys the item you are holding.
• Step takes your current calculated path to your destination and performs a single step (with tons of error checking).
• … and so on.

All task functions are members of my task class, and these base functions are quite robust after extensive testing and are well suited to construct more complex tasks.

//Secondaries
bool walk(Garden &garden, Population &population, int (&arguments)[10]);
bool idle(Garden &garden, Population &population, int (&arguments)[10]);
bool search(Garden &garden, Population &population, int (&arguments)[10]);
bool forage(Garden &garden, Population &population, int (&arguments)[10]);
bool take(Garden &garden, Population &population, int (&arguments)[10]);

//Species Masters
bool Ant(Garden &garden, Population &population, int (&arguments)[10]);
bool Bee(Garden &garden, Population &population, int (&arguments)[10]);
};

In these secondaries, we construct the functions by simply chaining together the other tasks:

• A walk task is just multiple steps (with error handling)
• A take task is a look and swap task (necessary due to ant memory handling, I’ll explain later)
• An idle task is choosing a random location and walking there (using walk), then waiting a number of ticks (using wait) and repeating this cycle for a given number of times
• … and so on

The other tasks are more complex. The search task queries the memory for any memory matches of locations containing the object “food” (whatever that is for a given species of bot). It loads those memories and walks to all of them, “searching” for food (in the ants case: “grass”). If it has no recollection of food, it strolls randomly and then looks around. By looking and inspecting ( = “look” with viewRadius 1; i.e. only looking at the tile beneath it), it can update its memory with its surroundings and search for food intelligently and in a directed manner.

A more general forage task then consists of searching for food, taking that food, looking around (to update the memory and look for neighboring food), returning home, and caching it.

Finally, a bot is defined by its “species” which dictates the genus of AI I bestow upon it. Each species is associated with a single master task which dictates their entire behavior, consisting of a cascade of smaller and smaller tasks, easily defined by a set of memory queries and primitive tasks. These are tasks such as “Ant” and “Bee”.

Top-Down Outlook

From the top down, this system consists of a “task-master” class, which coordinates the master tasks and their execution for each individual bot on the map.

The taskmaster has a vector of master-tasks, each associated with a bot. Each master task in turn has a queue of sub-tasks, which are loaded when the task object is first initialized with an associated task-function.

class Task{
  public:
    //Members
    std::stack<Task> queue;
    bool initFlag = true;
    int args[10];
    bool (Task::*handle)(Garden&, Population&, int (&)[10]);
    int botID;
    std::string name;

    //Constructor
    Task(std::string taskName, int taskBotID, bool (Task::*taskHandle)(Garden&, Population&, int (&)[10])){
      name = taskName;
      botID = taskBotID;
      handle = taskHandle;
    }

    //Launch a Task
    bool perform(Garden &garden, Population &population);

    //Continue with primitives here...

Each task object in the queue stores an array of arguments that it passes to its associated function handle. These arguments dictate the behavior of these primitive tasks, designed to be as general as possible. These arguments are passed by reference so the task object in the queue can store its arguments and have its sub-functions change them, so you can do things like iteration to enable behaviors like waiting a certain number of ticks, or requiring collection of a certain number of items, etc. The subfunctions change the value of the iterator (argument[n]) of the parent function by reference, and make their success condition dependent on it’s value.

Every tick, the taskmaster goes through his list of master-tasks and executes them, by calling their perform method. The perform method in turn looks at the top element of the queue inside the task, and executes it with the arguments from the task. This way you cascade down the task-queues, always performing the top-most task. The completion of a task is then mandated by its return value.

//Execute Task Function
bool Task::perform(Garden &garden, Population &population){
  //Debug Message
  if(debug){std::cout<<"Bot with ID: "<<botID<<" performing task: "<<name<<std::endl;}
  //Change the Name and Execute the Task
  population.bots[botID].task = name;
  return (*this.*handle)(garden, population, args);
}

When a primitive task returns true, it has reached its stable point or should at least not be repeated (e.g. step returns true when you are at the destination). Thereby its return condition is fulfilled and it is kicked out of the queue, so the next task can be executed on the next cycle.

For a task containing a queue of tasks, it returns true once its queue is emptied. This way, you can construct complex tasks with a queue and sub-queue structure, where the same functions are called repeatedly, but each call they iterate the game state and task state by a single step.

Finally, the master tasks take on a simple structure where when they are called each cycle, they only load a task if they are empty, and otherwise they execute the tasks loaded in their queue.

//Species Functions
bool Task::Ant(Garden &garden, Population &population, int (&arguments)[10]){
  //Initial Condition
  if(initFlag){
    Task forage("Search for Food", botID, &Task::forage);
    forage.args[0] = population.bots[botID].forage; //What are we looking for?
    queue.push(forage);
    initFlag = false;
  }

  //Queue Loop
  if(!queue.empty()){
    //Get the Top Task
    Task newtask = queue.top();
    queue.pop();

    //If our new Task is not performed successfully
    if(!newtask.perform(garden, population)){
      queue.push(newtask);
      return false;
    }
    //If it was successful, we leave it off
    return false;
  }

  //Return Case for Mastertask
  initFlag = true;
  return false;
}

Using my queue loop (see code), I can execute the same function multiple times and every time execute the top item in their queue, kicking items out if calling their perform method returns true.

Results

All of this was wrapped up with libconfig so it would be easy to alter the parameters of the simulation. It was very simple to code in a variety of master tasks (I made ants and bees) and the definition and loading of a new species using libconfig was astoundingly easy.

//Anthill General Configuration File
debug = true;

//World Generation Parameters
seed = 15;
water = true;

//Species that the simulation recognizes
Species: {
  //Ant Species
  Ant: {
    masterTask = "Ant";
    color = (0, 0, 0);
    viewDistance = 2;
    memorySize = 5;
    forage = 2;
    trail = true;
    fly = false;
  }
  Bee: {
    masterTask = "Bee";
    color = (240, 210, 30);
    viewDistance = 4;
    memorySize = 30;
    forage = 4;
    trail = false;
    fly = true;
  }
  Worm: {
    masterTask = "Bee";
    color = (255, 154, 171);
    viewDistance = 1;
    memorySize = 5;
    forage = 3;
    trail = true;
    fly = false;
  }
}

Population: (
  {species = "Ant"; number = 40;}//,
  //{species = "Bee"; number = 12;},
  //{species = "Worm"; number = 5;}
)

They were loaded into the simulation elegantly. With my new and improved path finding, I could simulate a high number of individually acting bots, harvesting food in a 2d plane.

The modularity of this system allows fast redefinition of new species, with their behavior dictated by a simple master task. In the above settings, you might have noticed I simply reskinned the AI of bees as worms, who simply have a different color, different path-finding constraints (can’t fly), different eyesight, and a different memory size, altering their general behavior, as all of this is utilized by the primitive task functions

Debugging Ant Memories

The complex task and memory structure led to unforeseen difficulties and a high demand for exception handling.

There were three particularly difficult memory bugs that forced me to rethink my sub-systems:

Ants running around in a circle

One of the first bugs I encountered was when ants were frantically running around in a pattern in a closed of square, looking for grass in pile of dirt. This issue arose because I hadn’t yet implemented memory updating. Ants had memories of locations of food, and as soon as they picked up the grass and looked again, they formed a new memory.

The problem was that the new memory was at the same location, but the old one remained. This meant that as they continued to search for food, recalling and retaining locations of food that were no longer valid, and these old memories persisted over the new memory (they were remembering that sweet, sweet grass).

This was fixed by making sure that object data is simply overwritten in old memories if we view the same location and the object has changed. (e.g. I see that there is no longer grass there, but I don’t remember that there used to be grass there). In the future I might just give memories an “invalid” property so bots can remember old information that might be important, but no longer valid “manifest” (“I saw a bear here, but it is no longer here”).

Ants picking up stuff under other ants

Occasionally (especially with a high number of ants and a high grass-density) two ants would arrive on the same grass-tile in the same tick and attempt to pick it up. This meant the first ant arrived, looked around and grabbed the item in 3 steps. The second ant in turn would to the exact same thing, except right before he picked up the item, the other one snatched it away. He want happily along his way, having looked at the exact same environment as the other ant on the previous tick, and worked off his memory queue in the same way (because their memories are identical at this point). This leads to the second ant “ghosting” the first, never picking up items and instead just walking over the other ant who is actually working. I noticed this because with simulations of supposedly 5 ants, I only observed 3 walking around. This took a long time to find.

The problem was fixed by making the swap task primitive and forming a “take” task, which first looks on the ground to see if the items is there. If it is there, it “swaps”, and if it is not, it “waits” 2 turns to guarantee it gets the hell off the other ant. One time it is a two tick action, one time it is a single tick action.

Unreachable Locations

Another nasty bug that forced me to rethink my memory handling, was that certain locations that an ant could see were unreachable for them. This was caused by my lazy placement of “grass crosses” on land, which sometimes would overhang on the water. This forced my to generalize my step task.

When querying the memory to look for food, ants often had memories of spots they couldn’t actually get to (they saw the grass over the water and wanted it bad). If this wasn’t marked in their memory (like I did with a “reachable” boolean), they would continue to recall the memory and push it up in their queue, until its the only one left and they cause extreme lagging because they’re continually doing path-finding operations every tick trying to get there and failing.

The key was to have our step task update our memory if it can’t find a valid path to a location, marking it in our memory as unreachable. Additionally, our search task only queries reachable memories for locations of food.

Outlook

In general, I would say yes – I do regret spending the last week of my life wasted away on a sick programming binge cause I was inspired to make the bots do what I tell them to do (but also what they want to do!). I had to pull a lot of tricks out my programming hat to get this to work, and had to learn a lot of new things.

The system I have constructed is not 100% robust, and there are a few artifacts I can still observe. For example the look parse-direction is top-down and left-right, which means that the latest memory is the one that is in the bottom right corner. When recalling memories to go search for things, this means they tend to head south-east. You can especially observe this for large simulations, where the “bald patch” of grass grows quickly, and tends ever-so-slightly southeast, no matter the seed.

Improvement

I think in general, there is lots to do when trying to simulate more complex memories of more complex beings.

This includes increasing the robustness of the memory handling functions, but also adding new primitives such as “think”, and derived high-level tasks such as “decide” or “dream”. “think” might be a primitive action form to query a memory. “dream” in turn might constitute multiple calls to think: picking a random memory, taking a random property, and repeating this over and over to enforce frequent themes or important associations.

There are three other concrete things I plan to do in the future:

• Add task interruption and prioritization handling
• Add inter-entity communication
• Add a group structure, so entities can formally identify with each other

The task interruption and prioritization handling might be necessary for inter-entity interactions, as a bot can’t blindly continue what he is doing when spoken to (he must somehow “listen”) or when attacked (“flee” or “fight”).

Inter-entity communication will probably consist of one or two primitive tasks for exchanging memories or querying other bots memories (such as “say” or “ask”). This way information can be transmitted, such as the location of food or other resources.

I hope to implement these tasks and plot the speed with which resources can be accumulated by a large group, doing this both with and without communication. The population already tracks the amount of food collected each tick. It would be interesting to show if sharing memories can impact efficiency.

Future

One key feature to simulating societies would be adding group structures and giving these groups macro-scale properties, such as their general “goals and responsibilities”. This gives us a form of “seed” from which we can derive high-level tasks, that are delegated down a hierarchy of group structures to “lower” high-level tasks, directly influencing the world. This also brings with it a form of political structure.

This system is quite self-contained, with the visualization simply placed on-top. It would be very simple to reskin this as humanoids walking around, collecting resources and storing them in some location to grow it in size. The nature of the growth of habitats for example could be very strongly coupled to or entirely decoupled from the actions of the bots. Different species could be different tribes, with different characteristics, and different tendencies.

I could also combine this with my previously made map-generation programs (by extending the world class), to give the world some more reality.

Final Words

I plan on reskinning this with humans and implementing these last few features in the coming time. I will probably release my full source code when I am more satisfied with the state of my system (its still a little messy here and there).

Stay tuned for a follow-up article. I leave you with this video of bees searching for pollen in flowers, coded from the same basic fabric.

… and the Bee Task member function:

bool Task::Bee(Garden &garden, Population &population, int (&arguments)[10]){
  //Just Search for Flowers
  if(initFlag){
    //Define our Tasks
    Task take("Take Food", botID, &Task::take);
    Task eat("Eat Food", botID, &Task::consume);
    Task search("Locate Food", botID, &Task::search);
    search.args[0] = population.bots[botID].forage;
    queue.push(eat);
    queue.push(take);
    queue.push(search);
    initFlag = false;
  }

  //Work off our allocated queue.
  if(!queue.empty()){
    //Get the Top Task
    Task newtask = queue.top();
    queue.pop();
    //If our new Task is not performed successfully
    if(!newtask.perform(garden, population)){
      //Put the Task back on
      queue.push(newtask);
    }
    //If it was successful, we leave it off
    return false;
  }
  initFlag = true;
  return true;
}