Multi-Threaded Code Is Hard

I know that title is probably stating the obvious to anyone who has tried it but it bears repeating.  I have other articles that refer to the same in different ways.

Nearly a month ago I thought I was nearly finished with the change to the physics to get it ready for networking, just a few peculiarities to sort out.  Little did I know how long some of those 'peculiarities' would take to find. 

Today I have finally confirmed that one of the hardest problems to find was, yet again, caused by multi-threading.  When the player shot towards another character sometimes but not always the shot would fire, the muzzle flash would display but no projectile trail was shown and the enemy was not damaged.

Lots of debug code and head scratching later I narrowed it down to the line of sight intersect code with the enemy bounding spheres was returning a distance of zero from the muzzle of the shooting weapon.

In my head and all the maths I did and all the debug code said this was an impossible situation but there it was on my output window, length zero to target and the shot in reverse!  Aaaaah!

I got so frustrated I started looking at Unity3D and the possibility of re-writing from scratch and targeting the Xbox One instead of the Xbox 360.  After installing Unity3D and taking a quick look at that I decided all I would be doing was moving from one frustrating problem to a different set of frustrating problems. 

The break from XNA gave me some time to think and I eventually noticed that the spheres I use to intersect with are updated in a different thread to where I calculate collision.  I am not sure how I prove this next statement but all the elements of the position of the spheres update atomically (in one operation) and therefore cannot be out of sync on an individual level but my guess is that as each vector contains three floating point numbers any one could be out of sync with the other two.

Anyway, I've changed the code to lock the changes to the spheres and I can no longer reproduce the problem.  At last :-)

Just when you thought this article was over, sorry... moments before writing this up I have come across another error.  This time with particles.  At least this time I can see immediately it is also caused by multi-threading.

My last word on this today...  That particle code has been unchanged for a very long time but threading problems can hit you at any time and may not be easily repeatable!

Assumptions...

You know all the sayings about assumptions.  They all boil down to don't take things for granted but how do you know when you are making an assumption?

I have been chasing a problem with my grenade throwing code. They would disappear unexpectedly or explode at the wrong time or place.

I have lots of visualisation to confirm that the calculations are being performed and that the positions were correct and in view!

It turns out that the confusion was because I had unconsciously assumed that my update thread was always in advance of my draw thread.
Nearly everywhere else in the code the update does not matter if it runs out of sync with the draw thread but for grenades that have to bounce, the difference was noticeable.  The collision is calculated in one thread but the grenade is drawn in another thread in real time.

Overall the update thread does less work and so has plenty of spare performance therefore it seamed logical in the back of my mind that it would process the collision faster than needed.  What I had not allowed for is that it might have started after the draw thread. 

I had varying results that I could not explain.  Sometimes working and sometimes not which I now know is because it is multi-threaded.  The launching of the grenade could sometimes be picked up instantly by the draw thread because that is where it was in its cycle but the update thread could be a few milliseconds or even a frame behind that draw.

Problem solved and another lesson learnt :-)

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.

:-)

Cylinder Collision

I've just finished tidying up my code following a change I had been planning to do for some time.  I've changed the collision bounds for characters from multiple spheres to a single cylinder.

The red outlines in the following picture best illustrate what I mean.

Although cylinder to cylinder and cylinder to sphere collision is a tiny bit slower to calculate than sphere to sphere collision the end result has made the overall code much more efficient.  There are far fewer iterations and less calls to the final physics bounce calculations.

Another minor distraction from getting the animations done!

Collision

I've just been asked on a forum how I went about collision. As it links in to the model editor changes I made in the last post I thought I'd write up a summary.

To cut a long story short I have written three collision systems. The first two were Octrees based on a Ziggyware example. These worked nicely until I tried to get a smaller level of detail. The exponential amount of data this produced in the first version made the load time on the Xbox 360 about 7 minutes for a simple level! The second variation got down to 24 seconds load time but I still had not got the level of detail I wanted.

The final solution was grid registration. This assumes that even in a 3D scene most of the objects are positioned on a 2D plane. The world is mainly on a single level until you go inside a building.

The solution is to simply divide the world up in to a grid. Then work out where on that grid any object falls. It can fall in to several grid squares. Objects above each other would be in the same grid square.

When working out if a moving objects hits a stationary object first check the grid they are in. Then simply loop through all objects in the grid and carry out whatever collision test is needed.

My collision as previously stated is based entirely on spheres. Each object, animated, rigid, moving or static is divided up in to big spheres and then smaller spheres.

Every model and every sphere has an index and large spheres contain the index of the smaller spheres within and the smaller spheres contain the index of the triangles within.

The triangle are for use with positioning decals of bullet impacts which I won't go in to here.

Bump collision is now a simple series of loops testing each sphere in the moving object with each sphere in the static objects that are within the same grid. Working from the larger sphere to the smaller spheres. If any smaller spheres intersect then work out the overlap and use that to calculate an amount to push the spheres and therefore the models apart.

The collision of moving object against moving object does not use the grid but is fundamentally the same.

As I have a maximum of 32 moving objects at any one time in the game, I just test all 32 against each other. This is done first, so the end result is that moving objects could fractionally overlap other moving objects if they bounce off a static object but a moving object cannot end up overlapping a static object.