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