AI Behaviour Tree

It has taken me a couple of weeks to get the Behaviour Tree processing up and running.  I still don't know how effective my artificial intelligence (AI) will be but the mechanism for controlling it is now in place and appears to work.

I am pleased with the design:

• Runs in a separate thread (separate hardware thread on the Xbox)
• Shares processing fairly between all the AI controlled entities (Bots)
• Unlimited levels of child behaviours
• Parallel behaviours

It is the ability to add parallel tasks that I needed.  I got stuck at that point with my earlier state machine version.

The problem I had with the state machine was that a Bot may wander about and while wandering needs to be able to look out for enemies in the area.  In addition when the Bot enters combat it needs to be able to shoot at a target while running for cover.  In this Behaviour Tree design the behaviour can replace its own parent behaviour or launch a new behaviour to enter combat. That combat behaviour then launches two more behaviours, one to shoot at a target and the other to decide where to move to.

Each behaviour is a separate class so I have things like, Hide, Chase, Evade, Combat, Find something to do, Wander, etc.  I had to create twelve separate behaviours before I could even test it.  This is because so many of the behaviours are made up of other behaviours and so few actually control the Bot.

To avoid creating garbage** I had to design the structures and classes carefully.  I finished by having only one instance of each behaviour shared by all the Bot classes.  Instead of adding the behaviours as needed and using the individual behaviour classes to store results, the results are passed in to and returned from the behaviour classes.  The results being stored between updates within their respective Bot's class'.

This image shows a simplified version of the design:

I have added a method to show on screen what any individual Bot is thinking.  I have this running in the game and I can see that the Bots respond to changes in the environment by changing their behaviour.

At the moment some of the behaviours themselves are not carrying out the actions that I would like but as each one is now independent and broken down in to smaller and smaller behaviours I can work through them to adjust each in turn to get the results I want.

==

** Garbage is the term used for adding and then freeing up memory on the heap.  This freed up memory needs to be collected for re-use by a framework process that is relatively slow on the Xbox. Just adding to the heap is eventually sufficient to trigger the slow collection process even if there is no memory available to free up.

GameTime in another Thread

I run all the AI in Diabolical: The Shooter in a separate thread.  On the Xbox this is a hardware thread.  While working on the Behaviour Tree that I am currently in the process of implementing I found I needed to keep track of time.

The time is used to avoid tasks taking too long and making the Bot look daft.  It did not take me long to realise that getting the main thread GameTime in to another thread is not that easy.  In fact the following post from the XNA forums convinced me that I should not try: http://xboxforums.create.msdn.com/forums/t/10587.aspx

In the post Shawn Hargreaves suggests using a Stopwatch.  As Shawn wrote a large chunk of the XNA framework I have a lot of respect for his suggestions and taking that advice usually saves me a lot of work.  So without any hesitation that is what I did. 

I need to pass the time round to lots of behaviours.  The Stopwatch is a class so I could pass that round easily.  It's results are TimeSpan's which are structures so not as fast for passing as a parameter.  I would have liked some of the convenience of the GameTime class however it was unclear from the documentation if it included its own timer so I decided to write my own wrapper for a Stopwatch.

As it turned out all I needed was the following:

// Use a stopwatch to keep track of 
// the time for other threads
public class ThreadTimer
{
    private Stopwatch threadTime;

    // Create and start the timer.
    public ThreadTimer()
    {
        threadTime = Stopwatch.StartNew();
    }
    // The time since the timer was started
    public TimeSpan CurrentTime
    {
        get { return threadTime.Elapsed; }
    }
    // Calculate the future time after a number of 
    // seconds has been added to the current time.
    public TimeSpan EndTimeAfter(float howManySeconds)
    {
        return CurrentTime + 
               TimeSpan.FromSeconds(howManySeconds);
    }
}

I start that class whenever the new AI thread starts:

private void ProcessBehaviourUpdatesThread()
{
#if XBOX
    // First move on to the desired 
    // hardware thread
    int[] cpu = new int[1];
    cpu[0] = 5;
    Thread.CurrentThread.SetProcessorAffinity(cpu);
#endif
    // Each thread needs it's own random
    random = new Random();
    // Use the time to prevent run away behaviour
    threadTime = new ThreadTimer();
    // Keep the thread processing requests
    while (!KillThreads)
    {
        UpdateBehaviour();
        // Allow for anything else that runs 
        // on this hardware thread to get a chance.
        Thread.Sleep(
               GameSettings.botLoopSleepMilliSeconds);
    }
    IsBehaviourThreadActive = false;
}

That 'threadTime' is then passed to the Update() method of each behaviour. 

While mentioning threads I also pass the Random class as well.  That is another thing that is awkward with threads.  For some reason each thread must have its own Random.  I pass the reference to that in the Update() as well.



I'm please with how my Behaviour Tree is coming along.  At the moment it is untested but already it is more flexible and neater code than the State Machine I was using before.  The main code is done and now I am adding the individual behaviour classes.  I'll probably go in to more detail when I have it tested.