Diabolical Editor

I noticed the other day that I had not mentioned much about the level editor that I use for Diabolical: The Shooter.  I've spent a lot of time adding features to it so I thought it worth describing.

The editor is used for shaping and colouring the terrain and for positioning the static models on to the map.  With hindsight I should have created a completely separate application but my original design was to be able to quickly play test any level I created so the Editor uses much of the same code as the game and is run from the game's main menu.

That works but there has been a lot of struggling to keep the game code tidy whilst also adding in the Editor methods.  This has resulted in a lot compiler directives of the type '#if EDITOR'.

To be able to use Windows menus I have had to do some messing about.  The WinForm menus are not fully supported in the XNA game loop.  I have an open source test project that shows how I have managed to get the menus to work with some limitations:
http://code.google.com/p/xna-game-menu/

The top level menus and the drop downs have to be coded by hand but they can launch forms created with the Visual Studio GUI.  The menus work fine for the Editor used only by me but I would never use the WinForm menus in an XNA game.

Over time I have added stacks of features, too many to list but just a few are: texture terrain with up to four layers, adjust the height of the terrain with various helpers such as flatten, noise, slope etc.  use a round cursor, a rectangular cursor, add structures, waypoints, triggers, static particle and sound effects and so on...

The whole terrain is based on a height map using a regular grid.  This makes finding heights relatively quick.  The grid only has one value, the height at each corner.  The limitation of this is that it cannot do vertical faces only slopes.  For the vertical cliff faces seen in some of these screen shots I have created 3D models.

To position the cursor I project a line from the view and calculate where it intersects the terrain.  At first the cursor always followed the view but I found this difficult to see what I was doing so now the cursor stays still unless I hold down the Ctrl key.

I am not sure if my method for finding the point on the terrain to position the cursor is efficient but it is fine for this editor.  I step along the line projected from the view, testing the height at each point.  The step being just under one grid width to ensure every grid is tested.  As soon as the end point of the line goes underground I know that somewhere between the last step and this step it intersects with the ground.  I then back step in smaller and smaller segments to get a nearly accurate point of impact.  I only need to know which grid I'm in.

I use the top left corner of the grid in which the line intersects the terrain as the centre position of the cursor.  For some modes I offset this by half a grid in others I stay with the corner point.

I can size the terrain cursor using a simple popup form.  Whatever action I carry out is done for every point under the cursor.  The positions are all easily calculated using simple maths.

The terrain cursor and the many helper shapes I draw are just simple lines drawn in 3D space.  The cursor samples the terrain height at the ends of each line and sets the heights a fraction above the terrain.  This means the cursor follows the contours of the terrain.

There has been a lot of work over the years getting to this stage with many features I have not mentioned yet.  If I knew then what I know now I would probably use an existing editor and spend the time writing an importer rather than adding all these features to my editor.  Having said that, I've learnt a lot and I do enjoy knowing that I did all this.

To complete the picture, this is a list of all the features of the game engine:

• Walk round a 3D world
• - first person controls
• - over the shoulder view of yourself (more fiddly than it sounds)
• - resolution 1024x576 (for better performance on the Xbox 360)
• - jump
• - spectate
• - two player split screen
• Animated
• - blend animations
• - merge in arm movement to follow which way the player is looking
• - hold attachments that move with whatever they are attached to
• - shared animation files (and a way to get them in to the pipeline.)
• Physics
• - collide with characters and structures
• - projectile impacts
• - projectile trajectories (thrown grenades)
• Terrain and game editor (development only)
• - change heights
• - change textures
• Add and remove (only in the development editor):
• - models
• - triggers
• - particle effects
• - goals
• - trigger goal success
• - trigger add a new goal
• - trigger spawn player
• - trigger spawn non-players
• - trigger particle effects
• - waypoints for AI pathfinding
• - spawnpoints
• - weapon or equipment pickups
• Lighting
• - single shadow casting light
• - three effect lights
• - shadows (not a trivial task, many many months spent on this)
• Full menu system
• - select which map to play
• - customise the player character with hats etc.
• - load and save character choices
• - change music and effect volumes
• - in game pause menu, resume or exit
• - display goals outstanding and completed
• Combat system
• - select weapons
• - shoot weapons
• - throw grenades
• - melee (elbow bash while holding a gun)
• - projectile trails
• - impact damage decals (instanced)
• - impact effects, debris and smoke
• - explosions
• - muzzle flash
• - sound effects
• - drop weapons
• - pickup weapons
• - pickup ammunition
• Head Up Display (HUD)
• - weapon sights
• - sniper sights
• - zoom in
• - display ammo as used
• - compass
• - radar showing friend and enemy positions if close
• Non-Player Artificial Intelligence (AI)
• - pathfinding (A* using navigation rooms)
• - select a target if in range
• - shoot at a target
• - move to better cover to shoot from
• and I'm sure there's more...

Performance Solved

I have just had the oddest result by fixing one problem I have solved another.  As my wife just pointed out normally it works the other way round.  I normally solve one problem and create two other problems!  Not this time. :-)

To monitor performance while I play the game I use some graphs to avoid creating garbage.  These I display at the sides of the screen to show me memory allocations and CPU usage.  The memory bar goes up and eventually I can see garbage being collected with the momentary slow down on the Xbox.

On the other side I have a performance monitor that measures the time that hardware thread one Update and Draw methods take to complete and a third bar that measures the time taken for the Update that runs on hardware thread four.  These are my primary methods.  The graph is in milliseconds (ms) up to 17 and the bar changes colour to red when any result exceeds 16ms (one frame). 

For a long time I have known that looking in some directions causes a noticeable slowdown and the third bar shows red and off the top of the chart!  Visually the screen would stutter because the position of the view was not being updated quickly enough!  It was probably as annoying as the glitch caused by garbage collection.

As I had run out of things to try to get rid of my remaining garbage I decided it was time that I needed to deal with the performance related hiccup to make it feel nicer to play.

After a bit of fiddling I decided I could not guess where the problem was I needed some way to measure it.  I created myself a simple timer.

///   /// A static timer which displays the duration of a method in the trace output.  /// This is NOT thread safe and cannot be nested.  ///   public class MethodTimer  {  public static System.Diagnostics.Stopwatch Clock = new Stopwatch();  public static TimeSpan StartTime = TimeSpan.Zero;    ///   /// Mark the starting time to measure from.  /// This also starts the timer if it is not already running.  ///   [Conditional("DEBUG")]  public static void Start()  {  if (!Clock.IsRunning)  {  Clock.Start();  }  StartTime = Clock.Elapsed;  }    ///   /// Output to the trace window if the duration measured is greater than that specified.  ///   [Conditional("DEBUG")]  public static void Stop(string logName, TimeSpan logDurationOver)  {  if (Clock.IsRunning)  {  TimeSpan duration = Clock.Elapsed;  duration -= StartTime;  if (duration > logDurationOver)  {  System.Diagnostics.Debug.WriteLine("Method: " + logName + " took " + duration.TotalMilliseconds.ToString() + " milliseconds!");  }  return;  }  System.Diagnostics.Debug.WriteLine("The clock was not running when the Stop method was called!");  }    }

I put it either side of a method and get it to log a result if the time that method takes is longer than I expect.

I was surprised how quickly I got it down to one method causing my problem.  I won't go in to detail about the specific method.  It just simply attempted to do far to much every frame to get more accuracy than I needed.  I produced a much quicker but less accurate version.

Now for the great news.  When I tested that on the Xbox not only had my performance problem completely gone but so had ALL of my memory allocations, no garbage collection!  Two in one.

It's not entirely true that all my memory allocations have gone, but as long as you don't make any new sounds (XACT) or respawn there are none and the tiny allocations that do happen from those methods take a very long time before they would trigger the garbage collection :-)

==

Downloads:
'Performance Tools' including the graphs mentioned above:
http://code.google.com/p/xna-game-menu/downloads/list

Update: 27 July 2012
I have just come across an article written a few years ago  suggesting the same method as above:
http://blogs.msdn.com/b/shawnhar/archive/2009/07/07/profiling-with-stopwatch.aspx

Memory Allocations

A couple of weeks ago I mentioned that I had managed to work out how to run the CLR Profiler with XNA 4.  I now understand enough to work out what the results mean.  At least enough to track back to the parts of my code that are allocating memory during the game and therefore creating garbage to be cleaned up!

I have not finished getting rid of all the allocations yet but I was able to run through some testing on the Xbox 360 without the Garbage Collector triggering too frequently.

I found the CLR Profiler daunting at first but once you know which bits to ignore it's not so bad.

For my purposes all I need is the Allocation Graph button.

There's a tiny bit to know before you'll get anything at all and that is to make sure the 'Allocations' Profile: is ticked before unticking 'Profiling active'.  The 'Calls' profile collects a lot more data and as far as I can tell does not help with finding memory allocations.

At the point in the game where you want to start logging from simply Alt-Tab out of your game and in to the CLR Profiler window to tick the 'Profiling active' box.  Then Alt-Tab back to the game.  If you do it the other way round and try and tick the Profile: Allocations after starting the application then nothing is logged!

You could log everything from the start of the game but I found the graphs just far too confusing to read if I tried to do that.

When you have played enough of the game to get some data, skip back to the CLR Profiler window and 'Kill Application'.

For my purposes I can now ignore everything except the 'Allocation Graph'.  Open that up and skip to the RIGHT hand end.  This is the biggest tip I can give.  You work backwards from the right hand end towards the left hand end.

Start at the largest allocations at the top right.

Sometimes you can easily follow the lines but when they get lost in the others, either increase the scale or just click on any one of the boxes in the line and the lines change to a cross hatching either side to make them easier to follow.  You can also double click a method to see the connecting methods either side.
Just work backwards from method to method until you recognise a method in your code.

So far I have found the changes necessary to avoid the garbage have been quite minor.  Most of my own allocations have been caused by List<T>.AddRange(...) where <T> is one of my own classes.  This is easy to fix by using a loop instead of the built in AddRange().

I have had one where it was caused by an internal XNA framework method but luckily I did not need to be doing that during the game, so I simply paused its update during game and restarted whenever the menus open.

I'm now left with a few tiny allocations that I have to go through one at a time to eliminate them.  Then I can enjoy testing again on the Xbox 360 to have a garbage collection free game, I hope.

==

EDIT:
Just came across a tutorial that explains how to use the timeline to only look at allocations over a given period.  This saves having to activate the profiling mid game:
http://spacedjase.com/post/2010/07/02/How-to-eliminate-frame-by-frame-Garbage-Generation-using-CLR-Profiler.aspx

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.

:-)

CLR Profiler

I should be creating levels but I've been distracted.  As I was running through them I kept getting stuck on the structures!  Mainly in tight door ways and similar small spaces.  This was spoiling the levels so I had to do something about it.

You may wonder what this has to do with the CLR Profiler.  Well I'll get there in a minute.

I needed to have a more detailed collision model for use during movement.  I already know my current method cannot be any more detailed because then it runs too slowly on the Xbox!

To solve that problem I have been working on a new design.  After a few optimisations to speed up loading I think the idea is workable on the Xbox.  In the process of testing on the Xbox I further got distracted by the garbage collection. 


Garbage collections appeared to be getting more frequest yet I am very careful when creating methods to avoid allocating memory.  I decided I needed to find out what I had overlooked before I got too far with a design that might make it worse!  This is what brings me on to the CLR Profiler.


I know that the CLR Profiler is the tool for finding out what allocates memory on the heap, which is what ultimately triggers the distracting garbage collection.  The trouble is I have always failed to get it to work.

I gave it another chance this weekend and at last I have useful results from it.

This is what I needed to do to get it to work for me:

Get version 4 of the CLRProfiler:

http://www.microsoft.com/en-us/download/details.aspx?id=16273
I suspect that this was the most important thing.

Then Read the Manual:

It comes with it and in the FAQ's it explains that if you are profiling a 32 bit app, even on a 64 bit system you must use the 32 bit profiler NOT the 64 bit profiler.
XNA games are all 32 bit.
Up until I read that, the profiler never started profiling!
As soon as I started using the 32 bit version it started to log results.  Easy if you read the last few pages of the manual!!!!!

The CLR Profiler comes in a compressed file and you can unzip it to anywhere.  After having done that I created a folder and copied the 32 bit binaries and DLLs in to a more convenient location.

Run As Administrator:

I created myself a shortcut and in the Advanced properties set the shortcut to Run As Administrator.  That saves a bit of time each time I run it.

Start In The Game Executable Folder:

Another important bit, for my game at least, is to set the 'Start In' folder in the shortcut to be the folder containing the executable of whatever game I need to profile. 

My game threw an exception because it could not find a folder it needed.  Changing the 'Start In' folder fixed that.

I didn't do those things immediately it took me a little while to work out what I had to do to get it to work.

Getting The Results

I can now run the CLRProfiler from the shortcut, select Start Application and then browse to the executable and run.  Play the game and when I exit I get some results.

Initially I was getting far too many results because all the level loading gets in the way.  I find the results easier to understand if I start profiling when I get well within the main game. 

Simply remove the tick from 'Profiling active' then start the game using the Start Application button.  My debug version already had a way to pause so I can swap applications.  I use the alt key to pause and bring up a test menu.  That was useful to enable me to skip to the profiler and tick the 'Profiling active' to start.  Play the game a bit then skip back and use 'Kill Application' to end.

The log files come up and...  now I have a lot of confusing data to understand.

Luckily there are several other sites I have been reading to learn what the results mean:
http://www.flatredball.com/frb/docs/index.php?title=FlatRedBallXna:Tutorials:CLR_Profiler
http://geekswithblogs.net/robp/archive/2009/03/13/speedy-c-part-4-using---and-understanding---clr.aspx

Now I can try to make some changes to my code to reduce the garbage collections.

Diabolical In Ruins

The good news is that the level is deliberately within ruins.

I am very pleased with the models I purchased from Dexsoft Games.  I've edited and extended the set of ruins for my own use and I am pleased with how the first level is coming along.

Game Testing

My wife's mum and brother came round for breakfast this morning and I could not resist showing Matthew, my brother-in-law, progress on the game. 

I should point out that Diabolical is designed to be the type of game Matt and I like to play.  We have been playing coop shooters together for many years.  When we lived next door to each other and prior to Internet gaming being popular, we had a network cable strung between our houses to play anything we could that had some form of network game.

Back to today.  I was very pleased that not only was my code in a fit state to test on the Xbox 360 but we had great fun shooting at each other.  As my current test level only has one alien Bot at the moment the coop bit only lasted a few seconds.  After that we just kept shooting each other, dying and selecting to respawn.

Split screen play meant that hiding was not possible but the rather sparse test map has more than one path to everywhere so while one was distracted with chatting the other one of us would take advantage.

It was fun and everything worked without a crash or a glitch.  It was a shame I haven't got further with the maps but next time I hope to have a finished or near finish level.

For some time now I have been creating models, buying models and starting to put them in to a form I can use in a game level.

It's taken me a bit longer because when I changed the game to run the update in a separate thread it broke the level editor!

I've now fixed the editor and slightly improved it so I can get back on with building the maps.