Bots Can Walk Up Stairs

I got a bit excited today when a Bot walked up stairs and back down again.  I had not attempted to force the AI controlled Bot to do this.

This was a scenario I needed to test with my new collision model but the Bot did it on its own :-)

A few weeks ago I identified that my previous design was not detailed enough to allow the characters to walk through doorways cleanly and completely failed if that doorway also included steps or was already on top of a structure.

For the last three weeks I have been coding and testing an improved version.  Physics engines are surprisingly difficult.  It should just be a bit of maths but the complex tiny reactions regularly produce unexpected and frustrating results.  I got there in the end.

New Design

Instead of sharing collision bounds with the projectile impact code, the new movement system relies on a separate pre-calculated detailed grid.  This acts like a height map just for the areas of the map that contain structures.  If there are no structures the player must be standing on the less detailed terrain.

I like the feel of the typical sliding sphere response but I was trying to avoid having to create, store and load oriented bounding boxes (OBB) for every structure.  This needed some thinking about.  The goal was to be able to give a reasonable collision response with the minimum of data needing to be loaded by the Xbox.  File loading on the Xbox is relatively slow and most games take a long time to load their levels.  This is inevitable but with careful design I can minimise it.

I like the use of grids because it only needs a very quick bit of maths to determine which grid any location falls in to.  The new design stores only three bits of information in those grids and only stores it where it is not the default.

I automatically calculate the highest point of any structure in each grid square.  I can then manually set an additional floor level and clearance height for any building that can be walked through.  This only needs to be where the structure has a solid ceiling.

Interior scenes will have ceilings that do not collide so the floors in these areas will calculate automatically.  It only tends to be doorways that have to be done manually.  I spent much of the last few weeks trying to automate this calculation but the results were never robust enough.  Either they collided where they should not or worse they allowed a character to fall through a floor!

In-game it is fairly quick to calculate the slope between where the character currently is and the most appropriate floor in the grid they are moving to.  If it is too steep then the entity cannot move there.

The design took a bit of tweaking to make sure that all edge cases were accounted for with the minimum of calculations but after a lot of frustration the end result has been performing well.

Artificial Intelligence (AI)

I gained some advantages from the new pre-calculations which are used to speed up the generation of the navigation mesh used for the AI.  The most notable is that the cover height is automatically available to me rather than the long calculation I had to do previously.

I was also able to create a much more reliable test to check if any path could be walked by a Bot.  This now matches the results that the entity gets when moving so there is much less chance of getting stuck and most importantly it checks the floor level.   This is what allowed an AI controlled entity to finally walk up the stairs and through doorways.

:-)

Video Production

I've done a small video before lasting just a few seconds but now I have put together a longer sample.  The Alien in this clip is not scripted it does all the behaviour seen based on the AI of the game.

It still needs a lot of polishing but it is workable already.  I say already but I have been working on the Artificial Intelligence and the behaviours for a couple of months.

==

Slightly stepping away from the game I want a little moan about how difficult putting the video together was.  I'd captured video screenshots before and I assumed it would be fairly easy to edit out the bits that I didn't think people wanted to see, like the opening menus and the levels loading.

I used Microsoft Expression Encoder 4 SP1 to capture the video of the game.  That initial video capture works very well.  Simply select the region to capture and press the record button.  Easy.   The result of that capture needs to be transcoded in to something usable by YouTube.  To do that it is necessary to use a different programme in the Expression suite.  This is where is all goes wrong. 

Microsoft have so restricted the free version of the Expression programmes that they are a pain to use for editing.  It defeats the object of a free trial version because having used that and taken all afternoon to remove a few frames I am unlikely to buy the paid for version.

Firstly the version I was using could only have one section of the video selected at any one time.  Therefore to remove several sections it was necessary to do each cut one at a time and spend minutes in between encoding and then reloading each completed bit.  To make matters worse it only used the original file name so I had to rename each clip in between.  That all sounds easy enough but I had to work all that out before I came up with a workable production method.  Wasting several hours.

The most frustrating bit was that along the way several of the encoded videos ended up with bad artifacts at their starts and the Encoder programme hung once and corrupted the xml file used for saving the jobs.  I was not impressed.

==

Following on from the above I now use Windows Live Movie Maker.  It is still limited but for a free product it does a good job and is easy to use.  I still need the Expression Encoder to capture the video in the first place:
Microsoft Expression Encoder 4 to capture up to 10 minutes of video.
Windows Live Movie Maker to edit the video, add transitions and background music.

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!

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.

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.

Behaviour

I've been playing with code to add behaviour to the bots. At the moment this only relates to basic movement. They will either chase an enemy or return to their original task.

I am pleased with the results. It has been fun getting the bots to follow me about. They dart in then move away and jostle for position to get a good shot.

I also like the way that when they don't have a target they resort to the pathfinding to get back to their previous task.

I took some pleasure when I led them all to the far side of the map then ran away from them. They turned round at different times and eventually all worked their way back across the map to where they started.

If you have read my previous comments about pathfinding you'll know I was having performance problems with this. The basic pathfinding is unchanged. I did as I expected and have pre-calculated all the paths that I know before the game starts. These are saved with the map. All other paths needed are calculated during the game.

I use one hardware thread (on the Xbox 360) for any pathfinding requested and another hardware thread for all of the rest of the AI. I had to do this just in case working out any one path took too long. I did not want the reactions or behaviour to be held up. So far it's worked well.

Artificial Intelligence

The very short attached video shows the initial AI that I have added that makes the characters follow members of other teams.



==

The AI code used in that video is no longer used in the game.