August 3, 2012 at 13:21How to write adventure?
- Transfer
As part of writing my quest, I came across a wonderful article on game mechanics in adventure games, and I bring it to your attention.
This article will tell you how adventure development works. Most of the ideas presented are abstract, but in places where the code is presented or implementation details are discussed, the engine from my book “C # Game programming” is used . All code is available online, under the MIT license. The approaches discussed in this article are widely applicable not only to adventure games. For example, the idea of navigation meshes, once developed, is used in games such as Baulder's Gate, Planescape Torment, etc. With just a slight change, navigation meshes can also be used in 3D games. The system of interaction with the inventory and the dialogue system can be modified for most games with RPG elements.
Adventure games were a popular genre in the early nineties and have recently begun to gain popularity. The most famous quest is probably the Monkey Island series, where you play as an ambitious pirate.
The adventure user interface may vary from game to game, but in the picture above it shows the “Monkey Island” interface. A game scene is available to the player, and the character is somewhere on the screen. By default, when you click on a scene, the character will tend to get to the specified location. When you move the mouse around the game screen, things that can be contacted will be highlighted. For example, in the top picture, you can move courses along the castle on the dungeon cage. The character has several ways of interacting with objects and in the game “Monkey Island” they are listed on the lower half of the screen.
Choose “Look at”, press “Open” and Guybrush will whisper his impression of the castle (none of the characters in the game comment on the fact that Guybrush speaks with objects, well, I suppose they think he's crazy: D) .
The following is an inventory that shows what items the character currently has. Guybrush can interact with things in the inventory, as well as with objects in the game scene.
Now, I hope you got a basic presentation on the user interface and interaction with the game world. It really is not very difficult. Naturally, quests are determined not only by interfaces. Basically, this type of game has a strong plot, during which the player must overcome various problems and solve ingenious puzzles. Most quests allow the player to communicate with other game characters using a dialogue system. These characters are also known as NPCs (non-playing characters, non playing characters).
Adventure is a long-established genre, which means that the game can easily be divided into subsystems that will be programmed in the future.
The core of the system consists of a series of levels. If one of the levels is higher than the other, this means that the lower one is used as a sublevel of the system. This is a good solution for creating an isolated and clean architecture. The engine already does a lot for us: loading and drawing sprites, rendering and animation of objects, text can be drawn with alignment and various fonts - these parts for the game are already done!
The most difficult part of the program is the navigation system, and most of the article will be devoted to it.
The navigation system moves the character from the current location to the point on which the click was made. There are many ways to implement such a mechanism, but there is no one true one. Some quests use a first-person view, and therefore shifting to the side is a problem (take a look at ShadowGate and Myst).
For the most part, quests display the character on the playing space and sometimes it is important where the hero is to solve a certain type of task.
Navigation in games generally consists of finding a path. If you want to search more information on this topic than in this article, then this is a suitable keyword. The path is the line that the game character must follow in order to reach the desired position without passing through walls, tables, small dogs, etc. A path is searched between the points of the current location and the position where the click just occurred. Best of all, if the constructed path is the shortest or most accurately approaches the shortest - you do not want the game character to wander around the screen when you ask him to walk five meters to the left.
Path search algorithms are built on graphs that describe the movement space of the game character. A graph is the term in their field of theory of algorithms (don’t worry, the definition is very simple), which is built from a set of vertices and the relationships between them.
The above graph shows only the path between “Roads from outside” to the store through the “Store door” node. This prevents the character from wandering around the screen crazy. You can notice several things in the system:
- Doesn't the character seem to have too little freedom, but what if he wants to stop in the middle of the store? The count will not allow him to do this.
This is an absolutely right question and we can solve it with the help of a navigation system that associates the zone of permissible movement with the nodes of the graph.
How is the graph constructed?
We will make it out of a dare, which we will consider a little later.
Finding the shortest path in a graph
The most common algorithm for finding the shortest path in a graph is the A * (A star) algorithm. This method searches the graph in an attempt to find the shortest path to the selected node. This algorithm is widely used in games. The best resource for A * is the A * Amit page . Essentially, I think he did a great job explaining this method, and I'm not going to even try to do better. Read this page! : D
This version of A * is available on my google code repository. Of course, it is very basic and simple, but it works and finds the shortest paths. Here is the linkfor implementation. (The program will crash if the path between the two vertices cannot be found - of course, I will eliminate this in the near future: D)
A * starts work from the start node and then goes through all its neighbors, and calculates some weight value for the nearest vertices. Next, the algorithm is applied recursively for all neighbors with the highest weight. Weight is usually determined by a function that sets the distance from the node to the target. The algorithm stops when it finds the target node or determines that the path does not exist. This is only a summary, for a better understanding, go to the site of Amit .
With A * behind the belt, we can find the shortest paths on the graph, but so far we have not built it.
NavMesh, as you might have guessed, is an abbreviation for the term navigation mesh (grid) and, in simple terms, it’s just a set of polygons that describe the area in which the character can move. This mesh will be depicted against the background of the drawing using a specially designed tool.
In the top picture, the blue polygons represent the space that the player can move around. Pink dots are links between polygons that indicate where a player can move from one polygon to another. The graph will be created from test pink tie points and centers of all polygons. The start and end points of the graph can be set anywhere inside the blue polygon.
We will build the path from the position of the player, at the point of click of the mouse. This means that the given point (x, y) of the navigation mesh should be able to determine which polygon it is in.
The above code can do the trick of finding the polygon, but there still remains the question of how to check whether the point is inside the polygon or outside it. In this example, all the polygons in the navigation mesh are convex and this is rigidly set on the grid, which is built in the editor. Convex polygons help to make test intersections easier and it is much easier to work with created navmes.
The definition of a concave polygon is extremely simple. If one of the vertices is inside the polygon, then it is concave. In China and Japan, kanji are used to represent ideas - look at the next two kanji;
Try to determine which of the figures is convex and which is concave is cool, right?
The following is a program listing that determines whether a polygon is convex. In this case, the polygon is just a class (List _vertices) with a set of points.
We need the following listing to check for intersections.
At the moment, we can determine whether the point is inside the polygon and, as a result, we can check whether the mouse clicks fall into the zone accessible for moving the character. If there are no intersecting polygons on the way to reaching, then we will not be able to get to the selected point and the click will be ignored.
The last step at the stage is to take the character’s starting and ending positions, the centers of the polygons, connect the nodal points and build a graph on which you can run the A * algorithm.
The result of the algorithm will be a list of points along which the character can move. Below is the pseudocode of the algorithm for moving the character along the path.
The actual code I use is in the UpdatePath function.
The last step is to render the character’s sprite and conduct the animation in accordance with the direction of movement. The implemented code already ensures that the character moves in the direction of the selected vector, it remains only to compare this direction with the drawing of the animation.
This is an example of art that I found on kafkaskoffee.com (I removed the green border in the version used):
So, we have three positions at rest and three animation options. Movement in the direction of “left”, “right”, “up” and “down” can be implemented programmatically, by means of ordinary transformations.
To compare the motion vector of one of these animations, I made the following transformations. Four vectors were introduced for each of the directions: (-1, 0), (1, 0), (0, 1), (0, -1). Next, I calculated the scalar product and looked at which of the direction vectors closer to the motion vector, as a result, I selected the desired animation.
I'm sure you can find a better way, but this option is guaranteed to work. The algorithm finishes when the character reaches the click point and the sprite option based on the final guide vector is selected as the last state.
PS the author approved the translation and said that the figures are indeed both concave, but the translation of one of the kanji is convex, the second is concave
How to write adventure
This article will tell you how adventure development works. Most of the ideas presented are abstract, but in places where the code is presented or implementation details are discussed, the engine from my book “C # Game programming” is used . All code is available online, under the MIT license. The approaches discussed in this article are widely applicable not only to adventure games. For example, the idea of navigation meshes, once developed, is used in games such as Baulder's Gate, Planescape Torment, etc. With just a slight change, navigation meshes can also be used in 3D games. The system of interaction with the inventory and the dialogue system can be modified for most games with RPG elements.
What is adventure game?
Adventure games were a popular genre in the early nineties and have recently begun to gain popularity. The most famous quest is probably the Monkey Island series, where you play as an ambitious pirate.
The adventure user interface may vary from game to game, but in the picture above it shows the “Monkey Island” interface. A game scene is available to the player, and the character is somewhere on the screen. By default, when you click on a scene, the character will tend to get to the specified location. When you move the mouse around the game screen, things that can be contacted will be highlighted. For example, in the top picture, you can move courses along the castle on the dungeon cage. The character has several ways of interacting with objects and in the game “Monkey Island” they are listed on the lower half of the screen.
Choose “Look at”, press “Open” and Guybrush will whisper his impression of the castle (none of the characters in the game comment on the fact that Guybrush speaks with objects, well, I suppose they think he's crazy: D) .
The following is an inventory that shows what items the character currently has. Guybrush can interact with things in the inventory, as well as with objects in the game scene.
Now, I hope you got a basic presentation on the user interface and interaction with the game world. It really is not very difficult. Naturally, quests are determined not only by interfaces. Basically, this type of game has a strong plot, during which the player must overcome various problems and solve ingenious puzzles. Most quests allow the player to communicate with other game characters using a dialogue system. These characters are also known as NPCs (non-playing characters, non playing characters).
How can I break adventure into subsystems?
Adventure is a long-established genre, which means that the game can easily be divided into subsystems that will be programmed in the future.
The core of the system consists of a series of levels. If one of the levels is higher than the other, this means that the lower one is used as a sublevel of the system. This is a good solution for creating an isolated and clean architecture. The engine already does a lot for us: loading and drawing sprites, rendering and animation of objects, text can be drawn with alignment and various fonts - these parts for the game are already done!
The most difficult part of the program is the navigation system, and most of the article will be devoted to it.
Navigation
The navigation system moves the character from the current location to the point on which the click was made. There are many ways to implement such a mechanism, but there is no one true one. Some quests use a first-person view, and therefore shifting to the side is a problem (take a look at ShadowGate and Myst).
For the most part, quests display the character on the playing space and sometimes it is important where the hero is to solve a certain type of task.
Navigation in games generally consists of finding a path. If you want to search more information on this topic than in this article, then this is a suitable keyword. The path is the line that the game character must follow in order to reach the desired position without passing through walls, tables, small dogs, etc. A path is searched between the points of the current location and the position where the click just occurred. Best of all, if the constructed path is the shortest or most accurately approaches the shortest - you do not want the game character to wander around the screen when you ask him to walk five meters to the left.
Path search algorithms are built on graphs that describe the movement space of the game character. A graph is the term in their field of theory of algorithms (don’t worry, the definition is very simple), which is built from a set of vertices and the relationships between them.
The above graph shows only the path between “Roads from outside” to the store through the “Store door” node. This prevents the character from wandering around the screen crazy. You can notice several things in the system:
- Doesn't the character seem to have too little freedom, but what if he wants to stop in the middle of the store? The count will not allow him to do this.
This is an absolutely right question and we can solve it with the help of a navigation system that associates the zone of permissible movement with the nodes of the graph.
How is the graph constructed?
We will make it out of a dare, which we will consider a little later.
Finding the shortest path in a graph
The most common algorithm for finding the shortest path in a graph is the A * (A star) algorithm. This method searches the graph in an attempt to find the shortest path to the selected node. This algorithm is widely used in games. The best resource for A * is the A * Amit page . Essentially, I think he did a great job explaining this method, and I'm not going to even try to do better. Read this page! : D
This version of A * is available on my google code repository. Of course, it is very basic and simple, but it works and finds the shortest paths. Here is the linkfor implementation. (The program will crash if the path between the two vertices cannot be found - of course, I will eliminate this in the near future: D)
A * starts work from the start node and then goes through all its neighbors, and calculates some weight value for the nearest vertices. Next, the algorithm is applied recursively for all neighbors with the highest weight. Weight is usually determined by a function that sets the distance from the node to the target. The algorithm stops when it finds the target node or determines that the path does not exist. This is only a summary, for a better understanding, go to the site of Amit .
With A * behind the belt, we can find the shortest paths on the graph, but so far we have not built it.
Using the Navmesh Algorithm
NavMesh, as you might have guessed, is an abbreviation for the term navigation mesh (grid) and, in simple terms, it’s just a set of polygons that describe the area in which the character can move. This mesh will be depicted against the background of the drawing using a specially designed tool.
In the top picture, the blue polygons represent the space that the player can move around. Pink dots are links between polygons that indicate where a player can move from one polygon to another. The graph will be created from test pink tie points and centers of all polygons. The start and end points of the graph can be set anywhere inside the blue polygon.
We will build the path from the position of the player, at the point of click of the mouse. This means that the given point (x, y) of the navigation mesh should be able to determine which polygon it is in.
Polygon FindPolygonPointIsIn(Point point)
{
foreach(Polygon polygon in _polygons)
{
if ( polygon.IntersectsWith(p) )
{
return polygon;
}
}
return null;
}
The above code can do the trick of finding the polygon, but there still remains the question of how to check whether the point is inside the polygon or outside it. In this example, all the polygons in the navigation mesh are convex and this is rigidly set on the grid, which is built in the editor. Convex polygons help to make test intersections easier and it is much easier to work with created navmes.
The definition of a concave polygon is extremely simple. If one of the vertices is inside the polygon, then it is concave. In China and Japan, kanji are used to represent ideas - look at the next two kanji;
Try to determine which of the figures is convex and which is concave is cool, right?
The following is a program listing that determines whether a polygon is convex. In this case, the polygon is just a class (List _vertices) with a set 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);
}
We need the following listing to check for intersections.
///
/// Определяет, находится ли выбранная точка внутри полигона.
/// Взято с http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/
///
///
X координата точки
///
Y координата точки
/// Находится ли точка в полигоне?
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;
}
At the moment, we can determine whether the point is inside the polygon and, as a result, we can check whether the mouse clicks fall into the zone accessible for moving the character. If there are no intersecting polygons on the way to reaching, then we will not be able to get to the selected point and the click will be ignored.
The last step at the stage is to take the character’s starting and ending positions, the centers of the polygons, connect the nodal points and build a graph on which you can run the A * algorithm.
The result of the algorithm will be a list of points along which the character can move. Below is the pseudocode of the algorithm for moving the character along the path.
- Get character position -> pc_position
- Get the position of the current point on the path-> target
- Get pc_position direction to target -> direction
- Add * walkspeed direction to pc_postion
- Check if the PC is near the current position on the way
- If true, move the current point along the path
- If the current point on the path is final, then stop the character’s movement
The actual code I use is in the UpdatePath function.
Animation
The last step is to render the character’s sprite and conduct the animation in accordance with the direction of movement. The implemented code already ensures that the character moves in the direction of the selected vector, it remains only to compare this direction with the drawing of the animation.
This is an example of art that I found on kafkaskoffee.com (I removed the green border in the version used):
So, we have three positions at rest and three animation options. Movement in the direction of “left”, “right”, “up” and “down” can be implemented programmatically, by means of ordinary transformations.
To compare the motion vector of one of these animations, I made the following transformations. Four vectors were introduced for each of the directions: (-1, 0), (1, 0), (0, 1), (0, -1). Next, I calculated the scalar product and looked at which of the direction vectors closer to the motion vector, as a result, I selected the desired animation.
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 sure you can find a better way, but this option is guaranteed to work. The algorithm finishes when the character reaches the click point and the sprite option based on the final guide vector is selected as the last state.
Putting it all together
PS the author approved the translation and said that the figures are indeed both concave, but the translation of one of the kanji is convex, the second is concave