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. 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 games in which you play 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 usual 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 item in the world that can be interacted with. The player character has number of ways of interacting with things and in Monkey Island they're listed at the bottom of the screen.

Click "Look At", click the "Lock" 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 there is a inventory which shows what Guybrush is currently carrying, Guybrush can interact with these items that same way he can interact with the scene.

Now you've probably got a basic handle on the user interface and the player interaction with the world. It's not too complicated. 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 with wrapping and with various fonts - that's quite a chunk of the adventure game code done!

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 true one way. Some adventure games use a first person perpestive and therefore total 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 position 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