Thursday, August 12, 2010

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 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


18 comments:

Rich said...

I love this post. I started programming an adventure game in C# (just recently moved to HTML5/JavaScript because I love the idea of making a game easily accessible). And I can't help but be enamored by the Purple Tentacle! =)

Dan said...

Html / Javascript is definitely the way to go!

Anonymous said...

Nice article. Would you please elaborate on how do you build the inital graph and how do you connect start and end points to the correct nodes in the graph ?

Silf said...

Hi! Really useful post thank you for that. Is it okay if I'll translate in on Russian and share with other developers? Obviously, I keep link to original post.

Dan Relluchs said...

Hey Silf, that sounds cool to me. If you do translate it please post a link here, I'd love to see it :)

Silf said...

Hi Dan! It's me again =)
So, as it's link to translation of your article to russian:
http://habrahabr.ru/company/luxoft/blog/148632/

Thank you!

Silf said...

So, just one question about article. Looks like both kanji is convave (by default http://en.wikipedia.org/wiki/Concave). Am I right?

Dan Relluchs said...

Cool!

The kanji on their own aren't words but here are the words:

凸面(とつめん) convex
凹面(おうめん) concave

Oh or do you mean the shape? Yeh you're right :D (I didn't notice haha :))

kur said...

Dear Daniel,

How can I contact you?

Dan Relluchs said...

Hey Kur,

I've sent you a mail to you email address, listed in your blogger profile!

-Dan

Evyatar A. said...

Hi,

First of all- great read! Really set me on the right path. I'm also working on JavaScript adventure game.

However, I'm having problems with the navmesh problem- I couldn't figure out how you convert the polygons and their connecting points to a A*-eligible list!

Can you shed some light on this?

Thanks again, and hope it's not too late to ask questions (it's only, what, 2 years?),
Evyatar.

Dan Relluchs said...

Hey Evyatar,


Not too late :)

A* just needs nodes and their connections right? And the nodes also need to store their position.

So I think in the editor - I have the user manually link polygons together. (It's nothing fancy). I think I must have stored the two edges between each link.

To gather the nodes iterate over the polygons, iterate over the links and calculate the node position. The links know which polys they connect so that can be used for the connection information


For the polygons node position I got the centroid I think. I seem to remember it's something like add the verts together and divide by the number of verts.

For the links the polygon edges should often be exactly the same but it's possible they're not so I took the smaller one of the two edges (just using the Vector length operation)

The I consider that edge as a line and get the middle of the line as the node position. Which is some more vector math, normalise(p2 - p1) gets you the direction, then you times that by half the height of the line.

If the player clicked somewhere in the poly I also added that as a node, so the character could walk anywhere he was allowed to.

It's been a while since I've looked at this code or post - so some of this info might be redundant but I hope that answers your question!

Let me know if any of the math stuff was too hand wavy.

I think I put the source up here:
http://code.google.com/p/csharpgameprogramming/source/browse/#svn%2Ftrunk%2FExamples%2FAdventureGames

Which will show how I actually did it :D

Bryan Powell said...

Dan, thanks a lot for this post. It really helped me get the ball rolling on my independent adventure game project.

Not many materials tackle the issues specific to these kinds of games. Do you have any suggestions for other sources of information on adventure game development?

Dan Relluchs said...

There's adventure game studio http://www.adventuregamestudio.co.uk/ which has been around for a long time, the site has a lot of information about building adventure games (more the design).

It's free. A lot of good stuff has been made with it Gemini Rue and the Blackwell series. I looked at it a long long time ago and I remember finding the scripting system a bit archaic but that may well have changed.

I'm still playing around with adventure game interfaces and will probably post some more updates. http://www.godpatterns.com/2012/12/playing-around-with-adventure-game.html
But I don't know if I'll really get into the guts of how everything is done.

Javier Gálvez Guerrero said...

I don't know if it's too late, but I need to try... haha.

What tool did you use to define the navmesh polygons and the graph nodes? Did you build one yourself or are there any available?

Thanks!

Dan Relluchs said...

I'm amazed someone would see this tool and want to use it! haha :D It's definitely flakely!

But with a little love could be useful. I made it myself, the code is somewhere in here I think:

http://code.google.com/p/csharpgameprogramming/source/browse/#svn%2Ftrunk%2FExamples%2FAdventureGames%2FEditor

I don't know how easy it'll be to get running

Javier Gálvez Guerrero said...

Hi again, Dan. Thanks for your quick answer.

However, I've tried to build the Editor project and lots of missing files appeared.

Which are all the dependencies I need to have installed in order to make it work?

Dan Relluchs said...

To be honest, it's a been a while!

It used Tao, which was a C# OpenGL binding (it's now called OpenTK and it's changed a lot). Tao included lot of bindings OpenGL, OpenAL, PhysFS etc, so I think all the missing files will probably be from Tao.

http://sourceforge.net/projects/taoframework/


Apart from that it uses the Engine project also included in the repo, I linked.