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.