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.

:-)

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.

Pathfinding

Over the weekend I was working on pathfinding. I'd already done some research and A* (A-star) pathfinding sounded to be exactly what I needed.

The code was fairly easy to design a basic solution and from the word go I had included a weighting system for squares I wanted bots to prefer. Such as near to cover.

Modifying the map file to include the weighting values took me longer to implement than the pathfinding.

The bad news. Even on the PC pathfinding took much longer than I had anticipated. At first I thought it wasn't working but when I left it 5 minutes it did calculate the paths. The problem was the first path I had given it was very long and it exceeded the 90,000 iterations I had set as my limit. I always add a limit when I use a while() to avoid endless loops!

I added some quick fix optimisation to my code. The first being to remove the closed list because it is unnecessary. A closed marker is more efficient.

At the moment I have also limited how many items it will check on the open list. The disadvantage is that on longer routes I may not get the best path, just any path!

I had also made some errors with the weighting levels I had set. These took some experimentation to sort out. Initially I had made the weights far too high and the paths got driven in to the wrong areas making them unnecessarily long!

At the moment on the PC, all my test paths now calculate quickly enough that you cannot notice unfortunately on the XBox 360 there are short pauses whenever a new path is needed! I'm already using a dedicated hardware thread on an otherwise unused core, just for the pathfinding!

That's where I'm at. I intend to pre-calculate as many paths as I can and I expect that will be sufficient but I am still researching and thinking, more than coding, on this bit.