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! :)


royalexander said...

Hey mate, Roy Triesscheijn here. You where not the only one with speed issues with that code. I even took it offline shortly after you must've found it. I would just like to say that the new version is about 600x faster (not kidding). There was quite a serious bug in that code so yeah. Sorry that you've had to rewrite so much :).

The new version can be found at: http://royalexander.wordpress.com/2009/07/07/new-version-a-pathfinding-in-3d/

Gareth said...

Thanks Roy! I'll have a go at implementing it to see if I get any improvements.