Monday, 29 June 2009

Dysnomia - Development Diary Part Three

A bit of a shorter diary this week as I'm busy working on a number of things in Dysnomia that I'm not quite ready to show yet! Also, this week is more about coding than anything else, so non-techies may want to wait until the next entry when I should be showing off a little more of the game!

Optimisation is a very important part of game development. However, for simpler games you may not ever need to worry about performance - let's face it, if your game is running smoothly on your target platform from start to finish then going back over the code and optimising for the sake of it is ultimately pointless. Put the energy into starting your next game!

Likewise, spending hours and hours pondering over every line of code to ensure it's as efficient as possible will likely result in a convoluted and hard-to-follow program.

If you know your game is likely to use a lot of memory, either graphically or object-wise then you'll need to keep performance and optimisation in mind right from the start. Because I've never had to optimise a game before, I completely ignored all the issues. That is until I started to get frame hitches when running on the 360. Then I started to realise and put right many of the mistakes I had made.

Shawn Hargreaves, one of the XNA framework developers, has written a number of blog entries regarding .NET garbage collection and the 360. These three posts are the ones I found the most useful when starting to track down where I had gone wrong.

I noticed a definite "jerk" in Dysnomia that was occurring once every few seconds or so. After going through the code and commenting out the heavier update and draw methods, I couldn't narrow it down to one particular place in code. That's when I started to pay attention to the posts regarding garbage collection and how to either avoid or manage collections. I ran the CLR profiler against the game and found that (on Windows at least), I was seeing a level 2 (heavy collection) occurring every few seconds which would definitely correspoind to the glitches on the 360.

I started to look at my code and figure out where it all went wrong. To start with, I was using generic List() lists to hold my game classes. Enemies, spawn locations, lights, bullets - pretty much anything that changes in game is allocated on the fly and added/removed from its list. Each time an enemy died, it was removed from the list. When an enemy spawned, a new Enemy() was allocated and added to the list. Same with bullets. Those are quite complicated classes to begin with, and to top it off I was giving each enemy and bullet object its own Texture2D sprite. What the hell was I thinking?!

To fix the issues, I decided to follow Shawn's advice and went with his first "path" for avoiding garbage collection worries: Allocate as little as possible during the game loop.

I went back and re-worked how I managed my in-game objects. Rather than letting the List allocate for me, I created a Manager class for each of the lists. They work in much the same way as the ParticleEngine XNA sample in that the Manager classes pre-allocate all of the objects I will ever use in game, and use a queue to select the next object for use. When the object in question is no longer needed (if an enemy dies or a bullet hits something), it is set as inactive and placed back on the queue to be used again.

All of the pre-allocation is done when the level and content is loaded. After I've performed all my loading a allocating, I do a GC.Collect() before fading the level up and starting the game. This gives me a clean slate for the smaller allocations (Vector2s and value types mostly) that occur in-game.

Net result is that garbage collections no longer occur whilst the game is in progress. Okay, so now I'm starting to get into this optimisation stuff. I looked at the way I was using Texture2D for loading game content. I realised that having a spritesheet for each instance of a game class (enemy, door, light, bullet) was not the way to go. Too much unneccessary memory wasted.

Instead, in each of my game object Managers, I loaded the spritesheets for each type of object. For instance, I have a Spider enemy and a Slug enemy. Each enemy in my List in my enemy manager class can be a Spider or a Slug type. My manager loads one instance of a Texture2D for a Spider enemy, and one for a Slug enemy. In the EnemyManager.Draw() routine, I loop through all the active enemies in the List and choose the correct Texture2D to draw from, rather than having each Enemy class draw itself from its own Texture2D.

So that's just a couple of the ways I'm handling memory usage and garbage collection in Dysnomia. Allocate lots during load, allocate close to nothing during game. There are still some glitches to iron out in the AI routines that can get a little heavy, but I'm getting closer to that constant smooth 60fps gameplay I'm after.

Here's a bonus off-screen recording showing the action on the 360:

Monday, 22 June 2009

Dysnomia - Development Diary Part Two

Developing Dysnomia in my spare time makes the weeks fly by. This week, I'm going to write a little about the level editor behind Dysnomia and how I'm linking together map files, save game files and in-game "devices" which need to keep their status throughout a full playthrough.

The map editor is a functional but clunky Winforms application that doesn't use any XNA, but opts for GDI instead.

It allows the level creator to paint using tiles selected from several tilesheets, one for each map layer. The layers are drawn from the bottom up, starting with the floor tiles, then the walls, then anything overhead. There are a number of in-between layers as well, including separate layers for shadows and decals, which break up the tiled graphics without needing to duplicate tiles. For instance, rather than having "floor tile 1" then "floor tile 1 with top shadow", we simply place down "floor tile 1" in the floor tiles layer, then in the shadows layer we place down "top shadow".

The decals layer allows us to place down little "junk" items like littler, blood spatters, corpses, computer terminals and so on. We have a decal layer for the floor and one for the walls, allowing us to place rubbish on the floor and a computer on a table (tables being wall tiles).

The "specials" layer is used to place items that are replaced in-game with objects. Things like lights, enemy spawns, doors, healthpacks and other pickups all have a tile on the "specials" sheet which is used to represent them in the editor.

The editor also allows us to place down Devices used in the game. Door controls, turrets, terminals and all other interactive objects are placed in this way, and then a few controls allow us to change parameters for each device.

The editor saves each level to a separate text file, which contains grids of three-digit numbers representing a tile number. There is a grid for each layer. After the grids are saved out, additional information about the level is appended - the lighting level, map size and all the information about Devices.

The game will be split up into a number of levels, somewhere around ten in total. This number includes the area outside the mining outpost, on the planet surface. The player needs to scavenge items from the base to repair his ship and thus will need to return to the outside area (and the ship) every now and again.

All of the lower levels of the outpost are reachable via a central liftshaft. At the start of the game, the liftshaft does not work, and requires a number of motherboards to be replaced for each additional floor the player wants to reach. The map layout could be drawn as follows:

Outside -> Entry Halls
Floor 2
Floor 3

When the player crosses between levels, there will be a short pause for loading as the next map is read in and prepared for use. However, because the player can explore the entire base at will and return to any previous area at any time, we need to hold a state file on all the objects that the player can interact with. This state file will stay active from the start of a game until the player dies or finishes the game. The same state file will also be used for loading and saving games, so it must hold information on the player's status too - current map, position, health, weapon powerups, ammo etc.

I decided to wrap up all this information in a single class that is instantiated at the beginning of play. The class has its own Load() and Save() methods. The Load() method takes a string as the only argument, the string being the contents of a saved game text file. The Dysnomia editor has a generator to create a save file that represents the intial state of everything in the game. If a player starts a new game, it will be that file that is supplied to the GameData class, essentially creating a "new save" in memory.

Throughout the course of the game, the GameData class will be updated to reflect the current state of the game. For instance, if a player takes a motherboard out of a device, that device will be updated in the GameData class to show that it holds one less motherboard. The GameData class also holds the number of motherboards currently held by the player, which would be incremented at that point.

Some data in the GameData class will only be updated when the game is physically saved. The player's health, level and location would be some examples, as would the location of any enemies currently on screen. I feel that on the whole, it's a solid way of dealing with saving game progress, especially given the open-ended exploration nature of the game.

Tuesday, 16 June 2009

Dysnomia - Development Diary Part One

I now feel confident enough to write a little about Game 2, which now has the working title "Dysnomia". Dysnomia is the name of a real
moon of the planet Eris, and also means "lawlessness" in Ancient Greek. Dysnomia is the setting for the game - in fact, a mining outpost on the moon.

The backstory (though not fully fleshed out) goes something like: the main character, a space marine, was engaged in a firefight aboard a two-man fighter craft launched from a large battleship. Badly damaged in the fray, and with the mothership destroyed, the ship is forced to lock in a course for the nearest friendly base - a mining outpost on Dysnomia.

After drifting for three days and with systems failing, the marine lands the ship manually just outside the base. All attempts to make contact with the outpost have failed. The marine now has two missions:

1. To scavenge supplies to fix the ship. The ship requires:
- A number of replacement motherboards
- Several fuel rods, which are dangerous to handle and replace
- Navigational data which has been corrupted

2. To complete a report on the base and find out what happened to the inhabitants.

The game is a top-down shooter and borrows ideas from classics like Alien Breed and Gauntlet, whilst adding a few of my own ideas and mixing in a bit of light puzzle solving.

During the course of the game, the player will find many electrical devices in the outpost which require a certain number of motherboards to become operational. Some devices will be up and running, others will be missing some or all of their motherboards. It's up to the player to decide which devices to leave powered up, and which to borrow from for other parts of the outpost. Such devices include:

- Doors
- Computer terminals
- Automated Turrets
- Medibeds
- Electrical fences
- The main liftshaft which links the ten or so floors of the outpost

And of course, once the player has finished his report, he'll need to scavenge a large number of the same motherboards to fix his ship and leave the base.

The game's story will be revealed through visual clues and computer journal entries. As the character discovers more, the Report progress will go from 0-100%. Certain events will be worth a large amount of report progress, so the player won't need to access every single journal entry or discover every part of the base.

And now onto the technical side of things.

Dysnomia is my second XNA project. I began it directly after releasing Gravsheep on Xbox Live Community Games. Gravsheep didn't sell very many copies, but then again it was a fine example of a "polished turd" in that the gameplay and graphics were lacking in several departments, but it was very well finished with a good UI, smooth transitions and intuitive controls. I spent a long time making sure it played nicely with the features of the dashboard and the 360 which are often overlooked by other XNA developers. I of course intend to do the same with Dysnomia, only this time I hope the gameplay will be present too.

Dysnomia represents a huge leap in my abilities as a hobbyist game developer. I've been developing games for years, but this is the first time I've really put maximum effort into every aspect of the game. In other words, I'm not taking the easy way out. Every obstacle I've come up against, I have defeated with research and code, rather than simplifying my vision, or coming up with a half-assed solution.

It's also the first time I've worked with an artist. Leon Arellano replied to an ad I posted on the XNA forums, and his art style immediately fit the bill. He also has the exact vision I have for the game, and readily understands tiling and formatting graphics to work in a game. A perfect partnership so far.

I began the Dysnomia project with the GameStateManagement sample. In Gravsheep, all the gamestate and transitions were done by hand I was very proud of it. My implementation was nowhere near as elegant as the one offered by the GameStateManagement sample, however. All developers that want to eventually release on Community Games should be using this sample as a base, or developing their own solution to handle menus, transitions, multiple controllers, live profiles and so on.

I then began looking at Nick Gravelyn's TileEngine tutorial. A brilliant set of videos indeed. After part 3 I was happy that my way of doing tiling and scrolling was the right way (though I had never thought of layering before), and Nick's sample very closely matched the way I would implement such an engine. I took his code as of Part 3 and began implementing and expanding it to suit my needs. I already had a tile editor from Gravsheep, so it was a case of simply extending that to handle multiple layers. Layering in a tile engine was all new to me - I have no idea why I hadn't ever thought of it before.

Next, things all got a bit mathematical. For collision detection and for doing some fake dynamic shadows on the "lights" I had placed down, I needed some trigonometry. I'm sure most of this stuff would be simple for A-level or further Math students, but for me it was quite a stretch and took me a while to work out!

Firstly, a function to work out the point on a circle. I've actually done this previously, so I wrote this one myself.
private static Vector2 PointOnCircle(ref Vector2 C, int R, int A)
A = A - 90;
float radA = MathHelper.ToRadians(A);
int endX = (int)(C.X + (R*(Math.Cos(radA))));
int endY = (int)(C.Y + (R*(Math.Sin(radA))));
return new Vector2(endX,endY);
I use this in collision detection to cast a point out in front of the player according to the player's angle of rotation. The tilemap is then checked for walls at that pixel location and if a wall tile is found, a per-pixel test finds out if a collision has actually occured. This per-pixel test uses the colour information of the sprite of the tile in question to allow for oddly-shaped walls.

private static bool PointInTriangle(Vector2 P, Vector2 A, Vector2 B, Vector2 C)
Vector2 v0 = C - A;
Vector2 v1 = B - A;
Vector2 v2 = P - A;

float dot00 = Vector2.Dot(v0,v0);
float dot01 = Vector2.Dot(v0, v1);
float dot02 = Vector2.Dot(v0, v2);
float dot11 = Vector2.Dot(v1, v1);
float dot12 = Vector2.Dot(v1, v2);

float invDenom = 1 / ((dot00 * dot11) - (dot01 * dot01));
float u = ((dot11 * dot02) - (dot01 * dot12)) * invDenom;
float v = ((dot00 * dot12) - (dot01 * dot02)) * invDenom;

return (u > 0) && (v > 0) && (u + v < 1);
I'm not even going to pretend to know what's going on here. I took these calculations from a maths site and converted them to C#. All I know is that it's using Normals to calculate whether a given point (P) is inside a triangle made up of three points (A,B,C clockwise). I use this to calculate the position of the player's shadow when he walks past a directional wall light. All that math for an effect that half the players won't even notice. That's what I mean by not taking shortcuts this time. If I understood how all this math worked, I'd be developing 3D games for a living.

private static float fAngleBetween(ref Vector2 vPointA, ref Vector2 vPointB)
float fAngle = (float)Math.Atan2((double)(vPointA.Y - vPointB.Y), (double)(vPointA.X - vPointB.X)) - MathHelper.ToRadians(90);
return fAngle;
This function calculates the angle between two vectors. I use this during enemy AI routines to cast out a ray between the enemy and the player to see if there's anything blocking the enemy's path. First of all I use this function to find the angle between the enemy and player, then use a series of collision checks using cocentric PointOnCircles, increasing the radius each time.

That brings me onto the last bit I want to talk about for now - the AI. A simple enemy chase/wander routine just wouldn't cut it for Dysnomia as the level layouts pretty much require aliens to be able to find their way to the player. After sitting and thinking about how to implement pathfinding behaviour, I decided to find out how the professionals do it. A* is one method, and is touted as being the most efficent method of pathfinding in games. I had heard of A* before, but didn't know it was an AI algorithm.

After reading and actually understanding the concept, I wanted to see if anyone had written a C# implementation of A* pathfinding. Sure enough, Roy Triesscheijn had everything I needed on his blog.

However, after implementing Roy's source and modifying it to work in Dysnomia, I found that trying to calculate paths for multiple enemies each update (or even every 50-100 updates) was too slow, especially as the paths became more complicated. I got around this by implementing a number of behaviours.

- Enemies have three AI states - Idle, Following and Pathfinding
- Enemies start out with an Idle state
- Every update:
- If the AI state is Idle, we check to see if there's a direct line of sight between the enemy and the player. If so, we set AI State to Following. If not, we calculate a path and set AI State to Pathfinding.
- If AI State is Following, move enemy toward player.
- If AI State is Pathfinding, move enemy to next node in the A* discovered path.
- AI Counter is incremented
- If AI Counter reaches 50, reset AI State to Idle

Using this method, the enemies will follow a set AI pattern for 50 updates before calculating a new path. We don't calculate a path if the enemy can head directly towards the player. There are also path length limits in place, so if the A* algorithm doesn't find a path fast enough the enemy AI state is set to follow the player. Whilst this means that enemies that are too far away will not be able to get to the player, it also allows the AI to run as smoothly as possible.

There's a lot more to talk about, but that'll do for a first update. Enjoy this video! :)