Minecraft Coding

http://codeflow.org/entries/2010/dec/09/minecraft-like-rendering-experiments-in-opengl-4/

This is pretty interesting read about doing something that looks like minecraft using shaders.

Computers

My development computer's harddrive died - it's back now but I've lost a little code and it's taken far to long to get working again.


This is good pdf about OOP and why it's not necessarily the best model for modern architecture.

Plans

I think I've finished messing with adventure games for now. I've added a link to the article in the sidebar and it's something I do plan to return to, the hardest part is done - walking around a scene, adding an inventory and interactions is relatively simple.

One item of point and click adventure games that does keep popping up in my mind is creating a design tool that brings up a matrix of all possible game interactions. All items and interaction points in the game would be listed in a grid like excel. The names would  run across the A row and down the 1 row, each cell would represent an interaction (use teddy bear on cave wall) for instance. This idea can even be extended a little - not every item can interact with every other item in most adventure games. Using item A to solve a puzzle often destroys item A so it cannot interact with anything else after that point. An adventure game has a finite number of interactions and they can be organised and search like a tree. For a world state w perform an action to get a modified world state  w'. I may not have expressed this well but it would be the kind of problem Prolog would solve very easily and it's something I want to have a poke at some point.



Anyway to the thrust of this post - I'm going to be writing a few little games, or the very start of a game like I did for the adventure game. I plan to do a Break Out game some time soon - as this does a very good job of opening up the world of arcade type games and after that maybe something I can get done quite fast; a bare bones roguelike or text adventure. But I'm also open to suggestions so if you'd like me to have a look at something then send me a mail or add a comment. Like the adventure game example I'll upload the code to Google Code (and it's quite likely I'll use my Engine project as a base)

How to make an Adventure Game

This article will cover what goes into the programming of an adventure game. The ideas will mostly be implementation agnostic but where code is provided or implementation specifics are discussed they use the Engine project from my book C# Game Programming as a base. All the code is available online under the MIT license.

• Engine Code from the C# Game Programming Book
• Adventure Game Example Code

The ideas covered here are widely applicable, navigation meshes very much like the one described are used in games such as Baulder's Gate, Planescape Torment etc. and with very little tweaking such navigation meshes can be used for 3D games, inventory and dialogue systems are also common in games with RPG elements.

What are Point and Click adventure games?

Point and click adventure games were a popular genre of games in the early 1990s and have recently started to make a bit of a come back. The most famous adventure games are probably the Monkey Island series in which you play, Guybrush, an aspiring pirate.

The Secret of Monkey Island

The user interface for adventure games can differ from game to game but the image above shows the Monkey Island interface. The player is presented with a nice scene and the player character is usually visible somewhere on screen. By default if the player clicks on the screen then the player character will try to walk to that spot.

Moving the mouse across items in the scene will highlight their names. In the above picture you can move the cursor over the lock of the jail cell. This is an object in the world that can be interacted with. The player character has a number of ways of interacting with objects and in Monkey Island they're listed at the bottom of the screen.

Click "Look At" then click the "Lock" object and Guybrush, your player character, will speak out-loud about his impression of the lock (none of the other characters in the game ever ask who Guybrush is speaking too, so I assume they all think he's mad :D).

Next to the commands panel there's an inventory panel which shows what Guybrush is currently carrying. Guybrush can interact with his inventory objects the same way he interacts with objects in the scene.

By now you've probably got a basic handle on the user interface and how the player interacts with the world. It's a good, straightforward, learnable interface.

Point and click adventure games aren't just defined by their interfaces. They generally have a strong story, to progress in the story the player must overcome various problems and figure out tricky puzzles. Most adventure games also allow the player to talk to other characters in the game using a dialogue system. These other characters are known as NPCs (non playing characters).

How can an adventure game be broken down into systems?

Adventure games are an established genre so it's relatively easy to break the game down into systems that need to be programmed.

The layers of systems that make up an adventure game.

The general systems are shown here in a series of layers. If a layer exists above another it uses the lower layers systems. This is generally a nice way to architecture code that keeps everything separated and clean.

The engine already does a lot for us, sprites can loaded, rendered and animated, text can be displayed and 'wrapped', so it fits inside a certain area, various fonts can also be used - that's quite a chunk of the adventure game code taken care of by the underlying engine!

The hardest part to program is the navigation system and that's what this article will focus on.

Navigation

The navigation system moves the player from where they currently are to where you've just clicked. There are many ways to do navigation systems and there is no one true way. Some adventure games use a first person perpestive and therefore totally side-step the problem (see ShadowGate and Myst)

Myst

Shadow Gate

Generally point and click adventure games do show the character on screen and it can be important where the character is positioned on screen to solve certain puzzles.

Navigation in games is generally referred to as pathfinding. If you want to search for more on this topic that's the term to use. Paths describe a line the player character can follow to get to the desired position without walking through walls, tables, small dogs etc. The path to be found is from where the player character currently is to where the mouse has just been pressed. It's better if the path returned is the shortest possible path or somewhat near the shortest possible path - you don't want the player character wandering all over the screen when you've asked him to move five metres to the left.

Pathfinding algorithms operate on a graph that describes where the player can walk. A graph here is a computer science term (don't worry the definition is pretty simple) that which is made up of a number of nodes and the connections between them.

Example graph

The above graph shows the only way to get from "The road outside" into the shop is via the "The shop door" node. This prevents the character walking anywhere crazy. You may have noticed a few things about this system:
-Doesn't seem to give the character much freedom, what if he wants to stand in the middle of the shop? The graph wouldn't let him.

That's right and this an issue we'll overcome by using a navigation which associates a walkarea with each node.

-How is the graph made?

We'll created from a navmesh, which is what we're going to look at shortly.

Finding the shortest path on a graph

The most common way to find the shortest path in a graph is to use a method called A* (A star). This is a method that searches the graph in an attempt to find the shortest path to a particular target node. It's widely used in games programming. The best resource for A* is Amit's A* page. In fact I think he does such a good job explaining it, I'm not going to try and do better. Read that page! :D

The shortest path from the road to the window

There's a version of A* in my google code repo. It's very basic and naive but it does the job for adventure game pathfinding. Here's a link. (I believe at the moment is crashes if a path between two nodes can't be found - I will fix that in the future :D)

A* starts at the start node and then looks at all it's neighbours, it gives the neighbours a desirability value and the algorithm is applied recursively to the most desirable neighbour. Desirability is usual a function that calculates the distance to the target and takes into account the desirability of all nodes in the current path to it. The algorithm stops when it finds the target node or cannot find the target node. That's the quick overview, for a better in-depth look check out Amit's website.

With A* under our belt we can now find the shortest path on a graph but we still need a graph to search.

Using a NavMesh

NavMesh, as you might guess, is short for navigation mesh and at it's most simple it's just a collection of polygons that describe the areas the player can walk. This mesh will be drawn on to background art using a custom tool.

Creating a nav mesh for a scene from Monkey Island

In the above image the blue polygons represent places the player can walk. The pink dots are links between the polygons, they indicated where a player can move from one polygon to the next. The graph will be created from the test pink linking dots and the centres of all the polygons. The end point and start points of the graph can be a position anywhere in the blue polygons.

A path is made from the player position to where the mouse has clicked. This means given a point (x, y) the nav mesh needs to be able to discover which polygon that point is in.

Polygon FindPolygonPointIsIn(Point point)
{
    foreach(Polygon polygon in _polygons)
    {
        if ( polygon.IntersectsWith(p) )
        {
            return polygon; 
        }
    }
    return null;
}

Something like the above code would do the trick but there's still the little question of how to check a point is in a polygon or not. In this case all polygons in the navmesh are convex and this is enforced by the navmesh editor. Convex polygons make testing intersection easier and help to create a nav mesh that's easy to work with.

Comparing convex and concave polygons.

I find easy to think of the difference by concave where one of the vertices is inside the polygon. In Chinese and Japanese kanji are used to represent ideas - looking at the following two kanji; guess which means concave and which convex - cool right?

Here's the text to see if a polygon is concave. A polygon here is just a class with a (List _vertices) list of points.

bool IsConcave()
{
    int positive = 0;
    int negative = 0;
    int length = _vertices.Count;

    for (int i = 0; i < length; i++)
    {
        Point p0 = _vertices[i];
        Point p1 = _vertices[(i + 1) % length];
        Point p2 = _vertices[(i + 2) % length];

        // Subtract to get vectors
        Point v0 = new Point(p0.X - p1.X, p0.Y - p1.Y);
        Point v1 = new Point(p1.X - p2.X, p1.Y - p2.Y); 
        float cross = (v0.X * v1.Y) - (v0.Y * v1.X);

        if (cross < 0)
        {
            negative++;
        }
        else
        {
            positive++;
        }
    }

    return (negative != 0 && positive != 0);
} 

The next test we need is the intersection test.

/// 

/// Determines if the given a point is inside the polygon.
/// Taken from http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
/// 
/// 


X position of point
/// 

Y position of point
/// Is the point in the polygon?
public bool Intersects(float x, float y)
{
    bool intersects = false;
    for (int i = 0, j = _vertices.Count - 1; i < _vertices.Count; j = i++)
    {
        if ((((_vertices[i].Y <= y) && (y < _vertices[j].Y)) ||
                ((_vertices[j].Y <= y) && (y < _vertices[i].Y))) &&
            (x < (_vertices[j].X - _vertices[i].X) * (y - _vertices[i].Y) / (_vertices[j].Y - _vertices[i].Y) + _vertices[i].X))

            intersects = !intersects;
    }
    return intersects;
} 

Now we can test if a point is inside a polygon we can check any mouse clicks to make sure the player is clicking in a walkable area. If no polygons are intersected then the character can't possibly move there and the click and be ignored.

The final step is to take the start and end points, the centres of the polygons the joining edge points and create a graph that can be fed into the A* algorithm.

The path is returned as a list of points and the character can be moved along this list. Here's the basic psuedo code to move the character along the path.

1. Get player character position -> pc_position
2. Get position of current point on path -> target
3. Get direction of pc_position to target -> direction
4. Add direction * walkspeed on to the pc_position.
5. Check if the PC is near the current point on the path.
5.1 If so increment current point on path
5.1.1 If current point on path is the end of the path stop moving the character.

The actual code I'm using is here in the UpdatePath function.

Animation

The final step is to render a sprite for the player character and animate that sprite according to the direction the player is moving. The code that moves the character long the path already works out a direction vector that the player is moving so that direction just needs mapping to the art.

Here's the art that I found on kafkaskoffee.com (I removed the green border in the version I used):

 There are three idle poses and three animations. The walk-right animation can be flipped in code to give four directions the player can walk: left, right, up down.

The way I translated the Direction vector to one of these animations was by making the left vector (-1, 0), right vector (1, 0), up vector (0, 1) and down vector (0, -1) and then seeing which the Direction vector was closest to by taking the dot product.

private Direction VectorToDirection(Vector direction)
{
    Vector up = new Vector(0, 1, 0);
    Vector down = new Vector(0, -1, 0);
    Vector left = new Vector(-1, 0, 0);
    Vector right = new Vector(1, 0, 0);

    double upDiff = Math.Acos(direction.DotProduct(up));
    double downDiff = Math.Acos(direction.DotProduct(down));
    double leftDiff = Math.Acos(direction.DotProduct(left));
    double rightDiff = Math.Acos(direction.DotProduct(right));

    double smallest = Math.Min(Math.Min(upDiff, downDiff), Math.Min(leftDiff, rightDiff));

    // yes there's a precidence if they're the same value, it doesn't matter
    if (smallest == upDiff)
    {
        return Direction.Up;
    }
    else if (smallest == downDiff)
    {
        return Direction.Down;
    }
    else if (smallest == leftDiff)
    {
        return Direction.Left;
    }
    else
    {
        return Direction.Right;
    }
}

I'm certain there's a better way to do but this it works. When the path comes to end the final Direction vector is used to decide which standing still sprite will be chosen.

Putting it all together

Little Man

I added a little man that can walk around the nav mesh.

The man comes from kafkaskoffee as a template to build characters from. I changed it to png with alpha and removed the borders.

In walk test mode you can click an area and the little man will walk to that position. This will work with any nav mesh not just the small box above.

One issue I've notice is that sometimes that man doesn't walk to the position. I'm not sure why this is happening (or I've already fixed it :D) but I'm sure I'll get to it with a little debugging.

I'm getting quite close to the end of where I wanted to take this project it's been interesting (source code available at the usual place. The Engine has a had a few minor changes and the Shooter game also had to be updated).

*Walking bug fixed*
I'd lazily reimplemented a distance function and made a mistake in a it (float yd = point2.Y - point2.Y;). I've got rid of the entire implementation anyway and replaced it with something more natural. I'd starting writing the function with the end condition first and never really cleaned up properly - anyway all fixed and all awesome. Fix is checked in.

Trundle

The second image has had a bit of post processing added; the white doesn't really have a border or a drop shadow. The code now lets users test out paths, so it's getting closer to the idea of a simple walk around adventure game.

 Of course path smoothing can be added by using a spline to connect the nodes, more nodes could be added to each edge (or even the Funnel algorithm which I eventually gave up on adding :D), there's plenty of obvious improvements!

I'm not going to be doing character scaling, at least not any time soon, so this monkey island scene won't be my final test scene. The next step is moving a character a long the path and playing the correct animations at the correct time. The hardest bit will be finding some suitable test animations.

Amazing Teapot

For my current project I'm playing around with the basic code needed to make an adventure game. A game genre that's fallen by the way side a little. In the most recent commit (code available here using the simple Engine code explained in my book) I've added loading and saving of the navmesh and layers. Layers are, for now at least, just going to be sprites a little like Photoshop's layers.

The screenshot at the top is from Monkey Island and it's loaded in as layer zero. The there are two walkable areas that share a connection. In this particular screenshot the character sprite should shrink as he walks down the peer this would easy to add by giving each vertex a scale and then using those weightings to determine the current size of the character. Or it could be fixed absolutely to the Y position of the character in the world.

While searching around I found a link to my old article about formalising adventure game design - which I still think is an interesting concept and something I'd like to look at more. Then while searching a little more I stumbled on the website of xii games an indie game dev making an adventure game.

On one of his blog post he has this to say about adventure game design:

During the designing process of Resonance, I was careful to avoid these kind of tacked-on puzzles. As much as possible, puzzles that the player comes upon should be defined by problems caused by the plot with solutions involving the plot and rewards that move the plot along. Obstacles encountered shouldn’t be arbitrary or unrealistic. Puzzles should feel natural, as if you could encounter them in real life, and should be overcome in manners consistent with real-world logic. If the solution is not readily apparent, it should be hinted at in the normal course of the game, and if possible, should be tied in with the story.

I think giving good reason to the puzzles is a very important point (and something that can be used to complement my formalisation of puzzle design)

The game looks interesting and I'll be keeping an eye on it.

An Editor

Two weeks ago I decided I was going to just play around with the start of making an adventure game. There have a been a few detours but I'm going to stick with it until I have something very simple complete - perhaps a character that can walk around a scene and a simple hidden key / door puzzle.

Most recently I was writing the code to allow the character to navigate the scenes and I've now uploaded it to the source repository.

The Editor project has a simple GUI editor to create NavMeshes. The next step will be adding a way to test the pathfinding, backgrounds and an animated character to move around the screen.

PathFinding Mark 1

Pathfinding now works. The above shows a collection of convex polygons with their joined edges connected. Click once inside the polys to start the path and again to end it and a line will be drawn respecting the polygon bounds. The funnel algorithm could still be implemented on top of this to make the path more optimal (but it would probably hug the edges more and look a little unnatural for an advenutre game.

You could do thing like tags polys or edges in the Astar graph for special animations like stair or ladder climbing. Though I don't know how much of a headache it would be to get the animation to sync to the structure of the stairs or ladder.

I'll clean this code up a little and update the repository soon.

Here's how the nodes and connections are made into a graph for the A* algorithm.

private Tuple CreateNodeNetwork(ConvexPolyForm polyStart, ConvexPolyForm polyEnd, Point from, Point to)
{
    _nodeGraph.Clear();
    // Store a map poly -> node to make it simple to work out the connection nodes.
    Dictionary polyToNodeMap = new Dictionary();

    PathNode startNode = null;
    PathNode endNode = null;

    // Create a node for the centroid of each polygon
    // Replace the postion of the start and end polygon.
    foreach (ConvexPolyForm poly in _polygons)
    {
        Point position;
        PathNode node;
        if (polyStart == poly)
        {
            position = from;
            node = new PathNode(position);
            startNode = node;
        }
        else if (polyEnd == poly)
        {
            position = to;
            node = new PathNode(position);
            endNode = node;
        }
        else
        {
            position = poly.GetCentroid();
            node = new PathNode(position);
        }

                 
        _nodeGraph.Add(node);
        polyToNodeMap.Add(poly, node);
    }

    // Create the edge nodes and add the links
    // !* This is where you'd add several nodes per edge, if you wanted.
    foreach (Connection connection in _connections)
    {
        LineSegment line = connection.GetShortestEdge();
        Point midPoint = line.GetMiddle();

        PathNode connectionNode = new PathNode(midPoint);

        // Add bidirectional links to connected polys and edge polys.
        polyToNodeMap[connection.StartPoly].Neighbours.Add(connectionNode);
        connectionNode.Neighbours.Add(polyToNodeMap[connection.StartPoly]);

        polyToNodeMap[connection.EndPoly].Neighbours.Add(connectionNode);
        connectionNode.Neighbours.Add(polyToNodeMap[connection.EndPoly]);

        _nodeGraph.Add(connectionNode);
    }

    return new Tuple(startNode, endNode);
}

It's a little scruffy - do I really need to pass that many parameters in, have the dictionary, lazily return those two nodes in a tuple? :)

Lines

I played around with my nav mesh trying to get the funnel algorithm working. I had it working in most cases but now and again the part that works out if the next funnel is contained in the current one got confused and while the funnel algorithm was cool it was not getting me much closer to have a walkable-area system for an adventure game.

Thus I started a new game state. It allows the player to add a 4 point convex polygon with 'a' key. The verts can then be moved around by dragging them. In the above picture the little square in the bottom right is the currently selected polygon and you can see the four circles representing it's vertices. You can't drag the verts in such a way to make a convex poly. There's quite a lot of useful 2d math bits in the above code. The green lines represent edge normals and the little red dot is the point on the nearest line closest to the mouse cursor.

The idea is when laying out the walkable area you drop a few of these boxes down and rearrange them to cover the walkable area. More verts can be added to the polys by presing 'i' near a highlighted edge. The polygons can be linked by clicking c then drawing a line that connects two edges between two different polygons. The blue circle shows the current connections.

It's pretty much there really. I need to add a layer of A* on top and wrap it all up in a nice interface where I can call something like WalkTo(x, y). Once that's done I'll clean it up and add it as an example to google code repo.

Dungeons

I've stuck A* path finding on the top of my, I guess, nav mesh thing now. It let's you make a nice big convex polygon, triangulates it and finds all the triangles centroids. Then you the user can choose two centroids and A* is used to plot a path.

I started doing this thinking a little about adventure games but this nav-mesh type code is quite general and could probably be used for all sorts of things. As I was drawing some of the images it reminded me of the old dungeon maps from Ultima Underworld (it would be easy to make a 3d mesh by doubling this and add some walls and then that's a pretty quick flat 3d dungeon).

(I really didn't want to write A* again as I've done a few times before but it appears I'd lost the code ;_;, so I quickly hacked out a new one, it's not a very good abstraction at the moment but it may get tarted up at some point. Amit is still the best reference on the net for A* and seems to go into a lot more detail than I remembered from last time I looked it up.)

I think at the moment the paths would be a little unnatural for an adventure game protagonist to walk (even if I stopped them being a collection of straight lines and made them into a bezier curve). I've had a closer look at the funnel algorithm and it actually seems pretty straight forward so I may even add that to this little experiment to.


* I've also rewritten the code that finds adjacent nodes, it's just as inefficient but it's now far easier to read.

Pink is as a debug color is the one true way

I've been playing around with the poly-tool thing I made last weekend. This time I've given each triangle a node and then linked adjacent nodes. Which forms a very pretty graph. This type of graph can be used as the basis of a path finding system, which seems to be where this is heading.

My method of finding adjacent nodes is inefficient and possibly a little bit wtf but it works and it's a pre-process step (something that wouldn't be done while a game is running) so I'm happy to leave it as is for now.

The node positions are pretty easy to find, I've used used the centroid.

struct Triangle
{
    public Point A { get; set; }
    public Point B { get; set; }
    public Point C { get; set; }

    public Point CalculateCentroid()
    {
        float x = (A.X + B.X + C.X) / 3;
        float y = (A.Y + B.Y + C.Y) / 3;
        return new Point(x, y);
    }
}

It's just the averaging of the surrounding vertices to find the centre (centroid point, apparently triangles have a number of notions of centre) point.

The next step would be to whack an A-Star algorithm on this and see what happens. I'm pretty sure in certain cases the movement wouldn't be optimal and would look a little odd. To get around this there are things like the funnel algorithm but I don't know how far I want to take this little demo / experiment.

Torchlight

 I was reading this article about the making of Torchlight and was suprised to see they used the Ogre 3D engine.

“We ended up using the Ogre 3D engine, which is open source,” says Baldree. “It doesn’t really cost anything, and it’s got really great support for older hardware. And given the size of the development team we didn’t want to spend a ton of time developing the latest pixel shader for a graphics card that only 20 or 30 people have.”

Ogre is a free open source engine with good C# bindings (if I remember) though I've heard it does suffer a little from Singletonitis. Still it's a great well test platform for development and it's open source.

The diving board

With the release of C# Game Programming: For Serious Game Creation, I've got a nice code base to create cool new examples and experiments and recently I've been thinking about adventure games.

Adventure games, the red headed step child of gaming, once so popular, now living in the basement, rarely making an appearance. Lucas Arts used to make some excellent adventure games, until they went mental and closed down lots of their studios so they could concentrate on funnelling large amounts of cash into the various Star Wars games that tended to implode. But before the crazy took hold some truly excellent games were created. Just in case you don't remember how excellent here's a fistful of nostalgia:

Day of the Tentacle! Awesome.

The Dig! Only game that's ever really felt like a movie to me (in a good way :))

Loom - if you've never tried this I recommend it. Something that you probably wouldn't see produced by the mainstream western games industry today.

Monkey Island - god I love a good "Meanwhile..." sequence.

Sam and Max Freelance Police another great adventure game

Full Throttle! Yes - this is how you create a believable fantastic world.

So I think the conclusion we can come too - adventure games were awesome and their departure left a gaping hole in the heart of many gamers. How did they fill this hole? They started making their own adventure games, using tools like the AGS - Adventure Game Studio. People have done wonderful things with AGS but it's an old tool and  the age shows. The scripting language is totally cargo cult land, a design that seems to come from guessing how how programming languages work - no arrays or any type of containers? Please!

So what's the first step you'd need to take, as a programmer, to make an adventure game? I think it would be a character walking around - moving the character and playing a walkcycle that'd be pretty simple, the harder bit would be defining where the character could walk and were they couldn't. To illustrate this:

The red area is the area where the character can walk. Click anywhere in this area and the character will walk the there. Conversely

This is area were you can't walk.


Tangent: So Japanese and Chinese - have you ever noticed they don't use the Roman alphabet? Lots of symbols instead, that's what you get when you've never had Pax Romana. Both Chinese and Japanese use lots of symbols known as kanji or hanzi and two of these symbols are:
凹
凸
The top is concave and the bottom one is convex and you're always going to know what those words mean when you read them. The meaning is encoded in the symbol! Crafty! The Roman alphabet has a similar history but it's largely forgotten and not really as useful - for example the letter 'A'.

Yes the letter A is supposed to come from cow? Who would have seen that!

The areas in adventure games were you can walk can be defined using one or more polygons. To be able to defined any area with a polygon it means we'll have to write some code that can deal with concave polygons. It's pretty easy to work with convex polygons - in fact OpenGL only supports the drawing of convex polygons but working with concave polygons is a little more difficult.

In the original Monkey Island code I suspect they didn't do anything with polygons, instead I think they would have had a bitmask over each scene. Then the mouse pointer position could be used to index the bitmask and find out if it's a walkable area. This is an easy way to program when you're accessing the frame buffer directly but these days most graphics are passed on using vertices, triangles and whatnot making it a little harder to use a pixel based scheme. The polygon way is also far more efficient and compact allowing it to be easily used with scenes that have much higher resolutions. (It's also applicable to other types of game, games like Baulder's Gate probably used a polygon based system to decide where the players could walk)  


My little project allows the user to drop vertices and the program links them together. The user can click the starting vertex to close the loop and form a polygon. At this point the polygon is filled in. In the case of a concave polygon, it has to be broken up into a number of convex polygons so OpenGL can draw it. Here's a screen shot.

 This should be quite easy to move into an adventure game and I think I'll be looking into developing that first step.  I want to get a character walking around a 2D scene with certain areas blocked off. I've not gone into the actual code but high level it's pretty simple - each area is a list of positions, this list can be transformed into an outline / triangle representation to feed to OpenGL so it can be visualized. To make the system useful for programming adventure games there needs to be a intersection test for a point - which I've written but haven't tested and a little code to save the data out.


Once I get a little further on in the dev stage I'll upload it as another example project for the Engine.

C# Game Programming Book

My book, C# Game Programming: For Serious Game Creation, seems to have now been published and is available on Amazon!

• Learn how to use OpenGL and C# together.
• Learn how to create the fastest game loop for C# using a Windows Form.
• Dive in C using Interop to get useful game functions such as timers.
• Learn how to use the latest versions of C# to write tighter, leaner code.
• Lightning Fast hardware accelerated 2D game programming
• Bitmap font rendering
• Joypad, mouse and keyboard input for games
• 2D and 3D math 
• Create a tween class - making animation as easy as flash.
• Create a nice fast game engine
• Create a 2d scrolling shoot'em up
• Game development techniques. pragmatism and project management
• Uniting testing
• Learn how to make the game you want to make.

It covers game programming using OpenGL (through the Tao libraries) using C#. It also runs through a simple arcade shooter game. So if you like the sounds of Game Programming in C# this is the book for you :D

I'm going to be updating this website with extra content and creating a code repository soon.
The repository for the Engine and the Shooter game is now available here: http://code.google.com/p/csharpgameprogramming/source/checkout

Electric Sink

It's summer, and I'm not really feeling in the programming mood after work, though there are a lot of projects that I'd be happy to start.

I've always be interested in Constructive Solid Geometry but never written an implementation. This pdf seems to be a good introduction.

Bonus Content: Kerning

Bitmap fonts and text were both handled in the C# Game Programming book but kerning wasn't. Kerning refers to the amount of spacing between characters in text. Without kerning the letters in words may appear to be spaced out oddly.

The code in the book produced text that looked like this:

Rather naively, I assumed this looked a bit funky due to kerning issues (hence this very topic to make everything nicer) but having revisited the code I see there is actually an error in the text class that means all the spacing is off.

Well this post will address both those problems. The first step is creating a font file that uses kerning. The ones included with the book are all monotype which means they don't use kerning at all!

Bitmap fonts are easy to make using Angel Code BMFont program. Here I've created a one texture page Arial bitmap font:

When you save the font file a .fnt file is created, as well as one or more texture maps of the font. If you open the .fnt file in a text editor and look near the bottom; you'll see that there is a section like this

kernings count=89
kerning first=32  second=65  amount=-2  
kerning first=32  second=89  amount=-1  
kerning first=49  second=49  amount=-4  
kerning first=65  second=32  amount=-2

Each line describes the kerning adjustment between two characters. For example if character 65 follows character 32 then character 65 should be moved back along the x axis by 2 pixels.

The kerning data can be represented quite simply by a dictionary that has a key of two characters and returns a integer kerning amount. The key can described by the following data structure:

 1 /// <summary>
 2 /// Used to as key to the kerning amount for two characters.
 3 /// </summary>
 4 internal struct KernKey
 5 {
 6     public int FirstCharacter { get; set; }
 7     public int SecondCharacter { get; set; }
 8 
 9     public KernKey(int firstCharacter, int secondCharacter) : this()
10     {
11         FirstCharacter = firstCharacter;
12         SecondCharacter = secondCharacter;
13     }
14 }

KernKey should be created in the Engine project; as it will be used with Text and Font.

This can now be used as a key to a dictionary of kerning amounts. The next task is parsing the kerning information from the file and adding it to such a dictionary. At the moment the FontParser.Parse method has the following function declaration:

public static Dictionary<char, CharacterData> Parse(string filePath)

This method returns a list of character information but this declaration must change if we're to also extract kerning information for the characters. A good way to handle this is to rename and re-purpose the entire function so that it's declaration appears like this:

/// <summary>
/// Create a font object from a .fnt file (and associated textures)
/// </summary>
/// <param name="path">Path to the .fnt file.</param>
/// <param name="textureManager">Texture manager to load font textures</param>
/// <returns>Font as described by the .fnt file.</returns>
public static Font CreateFont(string path, TextureManager textureManager)

This CreateFont function replaces the old parse method. It takes in the path to the .fnt file and then loads any textures, finally returning a new font object. It needs to deal with the possibility of textures already existing in the TextureManager. Textures should only be loaded once and if a situation arises where a texture is being loaded more than once a warning needs to be produced and the situation handled. The TextureManager needs an extra method adding.

/// <summary>
/// Has a texture of this name already been loaded?
/// </summary>
/// <param name="textureId">The id of the texture to check</param>
/// <returns>true if a texture exits, false if it doesn't</returns>
public bool Exists(string textureId)
{
    return _textureDatabase.Keys.Contains(textureId);
}

With this method defined the upgraded FontParser class can be given in full. Once the FontParser is written the Font class itself will need updating so that it is aware of the kerning table. Then finally the Text class will need to be updated to actually use the kern data (and this is the place we'll fix the bugs with the font rendering).

  1 public class FontParser
  2 {
  3     static int HeaderSize = 2;
  4 
  5     // Gets the value after an equal sign and converts it
  6     // from a string to an integer
  7     private static int GetValue(string s)
  8     {
  9         string value = s.Substring(s.IndexOf('=') + 1);
 10         return int.Parse(value);
 11     }
 12 
 13 
 14     private static string GetTextValue(string s)
 15     {
 16         string value = s.Substring(s.IndexOf('=') + 1);
 17         return value;
 18     }
 19 
 20     /// <summary>
 21     /// Create a font object from a .fnt file (and associated textures)
 22     /// </summary>
 23     /// <param name="path">Path to the .fnt file.</param>
 24     /// <param name="textureManager">Texture manager to load font textures</param>
 25     /// <returns>Font as described by the .fnt file.</returns>
 26     public static Font CreateFont(string path, TextureManager textureManager)
 27     {
 28         List<Texture> _texturePages = new List<Texture>();
 29         Dictionary<KernKey, int> kernDictionary = new Dictionary<KernKey, int>();
 30         Dictionary<char, CharacterData> charDictionary = new Dictionary<char, CharacterData>();
 31 
 32         string[] lines = File.ReadAllLines(path);
 33 
 34         int texturePageInfo = HeaderSize;
 35         while (lines[texturePageInfo].StartsWith("page"))
 36         {
 37             string line = lines[texturePageInfo];
 38             string[] typesAndValues = line.Split(" ".ToCharArray(),
 39                 StringSplitOptions.RemoveEmptyEntries);
 40             string textureString = GetTextValue(typesAndValues[2]).Trim('"');
 41             string textureId = Path.GetFileNameWithoutExtension(textureString);
 42 
 43             if (textureManager.Exists(textureId))
 44             {
 45                 // Really textures should never be loaded twice so it's worth warning the user
 46                 Console.Error.WriteLine("WARNING: Tried to load a texture that had been already been loaded. "
 47                     + "[" + textureString + "] when loading font [" + path + "]");
 48             }
 49             else
 50             {
 51                 // Assume texture files are in the same path as the .fnt file.
 52                 string directory = Path.GetDirectoryName(path);
 53                 if (string.IsNullOrEmpty(directory) == false)
 54                 {
 55                     directory += "\\";
 56                 }
 57                 textureManager.LoadTexture(textureId, directory  + textureString);   
 58             }
 59 
 60             _texturePages.Add(textureManager.Get(textureId));
 61 
 62             texturePageInfo++;
 63         }
 64 
 65         texturePageInfo++; // jump over number of characters data.
 66 
 67         for (int i = texturePageInfo; i < lines.Length; i += 1)
 68         {
 69             string line = lines[i];
 70             string[] typesAndValues = line.Split(" ".ToCharArray(),
 71                 StringSplitOptions.RemoveEmptyEntries);
 72 
 73             // Some fonts have kerning data at the end
 74             if (line.StartsWith("kernings"))
 75             {
 76                 ParseKernData(i + 1, lines, kernDictionary);
 77                 break;
 78             }
 79 
 80             // All the data comes in a certain order,
 81             // used to make the parser shorter
 82             CharacterData charData = new CharacterData
 83             {
 84                 Id = GetValue(typesAndValues[1]),
 85                 X = GetValue(typesAndValues[2]),
 86                 Y = GetValue(typesAndValues[3]),
 87                 Width = GetValue(typesAndValues[4]),
 88                 Height = GetValue(typesAndValues[5]),
 89                 XOffset = GetValue(typesAndValues[6]),
 90                 YOffset = GetValue(typesAndValues[7]),
 91                 XAdvance = GetValue(typesAndValues[8])
 92             };
 93             charDictionary.Add((char)charData.Id, charData);
 94         }
 95 
 96         return new Font(_texturePages.FirstOrDefault(), charDictionary, kernDictionary);
 97     }
 98 
 99     private static void ParseKernData(int start, string[] lines, Dictionary<KernKey, int> kernDictionary)
100     {
101         for (int i = start; i < lines.Length; i += 1)
102         {
103             string line = lines[i];
104             string[] typesAndValues = line.Split(" ".ToCharArray(), 
105                 StringSplitOptions.RemoveEmptyEntries);
106             // As before the order of the enteries is used to make the parsing simpler.
107             KernKey key = new KernKey(GetValue(typesAndValues[1]), GetValue(typesAndValues[2]));
108             kernDictionary.Add(key, GetValue(typesAndValues[3]));
109         }
110     }
111 }

The new parser class has additional code to read in the kerning information. It'll also uses the .fnt file to find all the textures the font uses and put them in a list. At the end only the first item of this list is passed onto the Font object. This is because, for the moment, we're not support fonts that use more that one texture. It's a feature that's easy to add and it may be addressed in a later update.

Here's the updated Font class that can store this new kern data.

 1 public class Font
 2 {
 3     Texture _texture;
 4     Dictionary<char, CharacterData> _characterData;
 5     Dictionary<KernKey, int> _kernData;
 6 
 7     internal Font(Texture texture, Dictionary<char, CharacterData> characterData,  Dictionary<KernKey, int> kernData)
 8     {
 9         _texture = texture;
10         _characterData = characterData;
11         _kernData = kernData;
12     }
13 
14     public int GetKerning(char first, char second)
15     {
16         KernKey key = new KernKey((int)first, (int)second);
17         int outValue;
18         if(_kernData.TryGetValue(key, out outValue))
19         {
20             return outValue;
21         }
22         return 0;
23     }
24 
25     public Vector MeasureFont(string text)
26     {
27         return MeasureFont(text, -1);
28     }
29 
30     public Vector MeasureFont(string text, double maxWidth)
31     {
32         Vector dimensions = new Vector();
33 
34         char lastChar = ' ';
35         foreach (char c in text)
36         {
37             CharacterData data = _characterData[c];
38             dimensions.X += data.XAdvance + GetKerning(lastChar, c);
39             dimensions.Y = Math.Max(dimensions.Y, data.Height + data.YOffset);
40             lastChar = c;
41         }
42         return dimensions;
43     }
44 
45     public CharacterSprite CreateSprite(char c)
46     {
47         CharacterData charData = _characterData[c];
48         Sprite sprite = new Sprite();
49         sprite.Texture = _texture;
50 
51         // Setup UVs
52         Point topLeft = new Point((float)charData.X / (float)_texture.Width,
53                                     (float)charData.Y / (float)_texture.Height);
54         Point bottomRight = new Point(topLeft.X + ((float)charData.Width / (float)_texture.Width),
55                                         topLeft.Y + ((float)charData.Height / (float)_texture.Height));
56         sprite.SetUVs(topLeft, bottomRight);
57         sprite.SetWidth(charData.Width);
58         sprite.SetHeight(charData.Height);
59         sprite.SetColor(new Color(1, 1, 1, 1));
60 
61         return new CharacterSprite(sprite, charData);
62     }
63 }

This new Font class can store the kerning data and it also uses it when measuring the font. The final class to be updated is the Text class.

 1 private void CreateText(double x, double y, double maxWidth)
 2 {
 3     _bitmapText.Clear();
 4     double currentX = 0;
 5     double currentY = 0;
 6 
 7     string[] words = _text.Split(' ');
 8 
 9     foreach (string word in words)
10     {
11         Vector nextWordLength = _font.MeasureFont(word);
12 
13         if (maxWidth != -1 &&
14             (currentX + nextWordLength.X) > maxWidth)
15         {
16             currentX = 0;
17             currentY += nextWordLength.Y;
18         }
19 
20         string wordWithSpace = word + " "; // add the space character that was removed.
21 
22         char lastChar = ' ';
23         foreach (char c in wordWithSpace)
24         {
25             int kernAmount = _font.GetKerning(lastChar, c);
26             CharacterSprite sprite = _font.CreateSprite(c);
27             var w = sprite.Sprite.GetWidth();
28 
29             float yOffset = (((float)sprite.Data.Height) * 0.5f) + ((float)sprite.Data.YOffset);
30             float xOffset = ((float)sprite.Data.XOffset) + kernAmount;
31             sprite.Sprite.SetPosition(x + currentX + (sprite.Sprite.GetWidth() / 2) + xOffset, y - currentY - yOffset);
32             currentX += sprite.Data.XAdvance;
33             System.Diagnostics.Debug.Assert((int)sprite.Sprite.GetWidth() == sprite.Data.Width);
34                     
35             _bitmapText.Add(sprite);
36             lastChar = c;
37         }
38     }
39     _dimensions = _font.MeasureFont(_text, _maxWidth);
40     _dimensions.Y = currentY;
41     SetColor(_color);
42 }

The inner loop now uses the kern data. The problem with the previous code (and cause of the bug) was that each character of the sprite wasn being position around it's center, the position needed to be adjusted so that it was the top left. Here's the Hello World again with the changes.

I think it's easy to see this version is far better!