Milestone

Diabolical: The Shooter has just reached a significant milestone...   The Aliens can now shoot back.

It's taken over two and a half years of evenings and weekends, a lot of frustration mixed in with some fun but at last I can start to see something that resembles a game.

There is still a long list of features that have to be added and lots of adjustments to get the action to feel right.  I was concerned early on in the design about how to make the Bots target players without being too accurate.  I am pleased to say if anything they are not good enough shots but I have several ways to tweak that...

Perhaps I spoke too soon.  That hurt!

Behaviours are Working

I had enough coding time at the weekend to sort out the troublesome behaviours.  My test Bot will now run, walk, strafe or face the direction being travelled and hardly ever gets stuck.  It even ducks down behind cover.  Not always quite where expected but it does not look daft.

Compared to the frustration of a week ago I am very pleased with the results.

The main change was to be consistent with what code updates the movement.  It now always uses a route generated from the path finder class even if that ends up being a straight line.  There was a lot of tidying up to be able to do this.

To be able to strafe I had to add an enemy target location and then a bit of tweaking to smooth the movement, especially aiming up and down, to stop it looking too jerky.


I reached a convenient point to test it on the Xbox 360 and I am pleased to say it works well and I still get a solid 60 frames per second.  Not surprising because all the Artificial Intelligence (AI) and pathfinding code are carried out in separate hardware threads.


Now to make the behaviours find cover properly and to shoot back!

Blog Comments Problem with IE9

There has been a problem using Microsoft Internet Explorer 9 (IE9) to view this blog for the last couple of weeks.  The problem started sometime mid January 2012.   IE9 failed to display pages that contain comments even in compatibility mode!

Google Chrome and other browsers would display the pages correctly!

I have changed the comment posting method to use a Pop Up window instead of being embedded in to the page.  That appears to fix it.

Microsoft have not done themselves any favours with IE9.  First I could not order my Pizza because the payment page would not display!  The tick box to remember my login to this blog can't be used with IE9 because it stops some of the edit icons appearing and now the comments.

I have preferred to use IE since about version 4 but now I find myself using Chrome more and more often!

Bot Behaviour Is Difficult

I didn't think it was going to be easy but I am finding getting good responses from my Bots is more complicated than I had anticipated. 

The mechanism I designed works and I can add various types of behaviour but the slightest omission in my thinking and the Bot does something peculiar or just stands there.

I'm adding more and more detailed debug information to help work out what situations trigger what responses from the Bots.

I found there is plenty of information available about the high level designs of various methods like Behaviour Trees or State Machines but not a great deal about what behaviours a First Person Shooter (FPS) Bot needs to process.

I've spent a lot of time with paper, pencil and eraser sketching out charts similar to the following:

Then coding those and now trying to fill in the gaps that testing has highlighted as problems.

It is very frustrating at the moment but I am sure it will be worth it in the end.

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://forums.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.

Navigation Mesh Pathfinding

There are two schools of thought with navigation for bots within games.  One is that the level designer or artist should mark the the usable areas and cover used by the computer controlled characters.  The other method is for those items to be calculated by the computer.

As I am both the coder and the level designer one way or another I had to do some coding.  Rather than programme methods in to the editor to let me manually lay out the mesh I decided to get the computer to calculate the navigation details.

A navigation mesh is a connected set of closed shapes representing the area of the map that can be navigated by the non-player characters.  There are loads of articles and presentations on the Internet explaining the advantages of this type of design over others.

I have spent the last month, evenings and weekends, working on my version.  My first attempts were to use edge detection and I came up with a very nice outline of my map but I was unable to come up with a satisfactory solution for turning that outline in to the closed convex shapes needed for pathfinding.

My eventual solution was to fill the map with the largest rectangles I could.  They get smaller as necessary to fill all the areas of the level that a character can move to.

I call the rectangles rooms but as you can see from the picture they are not rooms as we would envisage them.  Just open spaces within the level.  Any edge of a rectangular room that touches another rectangle I call a doorway.  Again not a real doorway but a space that a bot can move between to get from one rectangle to another.

I am pleased with the way this fits round obstacles while still letting bots pass through quite narrow gaps.

This is all calculated by the editor at design time.  The grid size used is 4x wider and 4x taller than the in-game grid.  This gives 16x more precision than the run time terrain grid.  Not all of this information is needed for pathfinding.  Only the room numbers and the doorway locations need to be saved and then loaded and used in-game at run time for pathfinding.

The paths calculate relatively quickly.  With my previous pathfinding solution I used a grid based A-star (A*) method.  On my test map this was slow mainly because the level would have over 16 thousand nodes.  The new solution on my small test area has only 64 nodes and I expect a full map to have less than 200 nodes.  A factor of about 100 smaller.  In addition the new navigation mesh doorways are more accurately positioned than a simple fixed size grid.  The A-star algorithm is nearly identical but is working on a much small sample set and it starts with only open nodes.  On my development PC the path calculation appears instant.

The information I am now storing lets me include ceiling heights and path widths.  The new methods prevent large entities trying to move through gaps that are too small.

The last feature I added was to pre-calculate cover points.  There are two types but I do not differentiate between them at run time.  Cover that can be hidden behind and shot over and cover next to a corner that can be hidden behind.

The small orange squares shown in the pictures indicate where a bot might possibly find cover.  This is not guaranteed cover because the target will be moving and the bots size is unknown at design time.   At run time the artificial intelligence (AI) will try each suggested cover point in order and check if it provides cover for the size of entity trying to hide and if that spot enables the ability to shoot over the cover at the target.  Only a suitable spot will be selected by the AI for the bot.

My next task is to write the AI that will use the paths.  I already have a state machine AI solution but I found it is not flexible enough for my expectations.  I am now looking to write a goal based AI solution.  We'll have to wait and see how I get on with that.