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.

:-)