How to write adventure?
As part of writing my quest, I stumbled upon a wonderful article on game mechanics in adventure, and I bring it to your attention.
This article will tell you about how the development of adventure games. 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 MIT licenses. The approaches discussed in this article are widely applicable not only for adventure games. For example, the idea of ​​navigation meshes, developed once, is used in games such as Baulder's Gate, Planescape Torment, etc. With only a small change, navigation meshes can also be used in 3D games. The system of interaction with the inventory and the system of dialogues can be modified for most games with RPG elements.
Advocates were a popular genre in the early nineties, and more recently began to gain popularity. The most famous quest is probably the “Monkey Island” series, where you play as an ambitious pirate.
The user interface of adventure can vary from game to game, but the picture above shows the Monkey Island interface. The player is available to play the scene, and the character is somewhere within the screen. By default, when you click on the 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 upper picture, you can move courses along the castle on the dungeon cell. The character has several ways to interact with objects and in the game “Monkey Island” they are listed on the lower half of the screen.
Select “Look at”, click “Open” and Guybrush will tell his impression about the castle in a whisper (none of the characters in the game comment on what Guybrush is talking to objects, well, I guess they think he's crazy: D) .
')
The following is an inventory that shows what items the character currently has. Guibrash can interact with things in the inventory, as well as with objects on the game scene.
Now, I hope you got a basic presentation about 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 games 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 dialog system. These characters are also known as NPCs (non playing characters).
Adventure is a long-established genre, which means that the game can be easily 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 above the other, then this means that the lower one is used as a sublayer of the system. This is a good solution for creating isolated and pure architecture. The engine already does a lot for us: loading and drawing sprites, rendering and animating objects, text can be drawn with alignment and various fonts - these parts for the game have already been 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 a character on the game space and sometimes it is important where the hero is located to solve a certain type of task.
Navigation in games in general consists of finding the way. If you want to search for more information on this topic than in this article, then this is the appropriate keyword. The path is a line along which the game character must follow to reach the desired position without passing through walls, tables, small dogs, etc. The 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 path - 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 based on graphs that describe the space of movement of the game character. A graph is a term in their domain of the theory of algorithms (do not worry, the definition is very simple), which is built from a set of vertices and links between them.
The above graph shows only the path between the “Roads from the outside” to the store through the “Door of the store” node. This prevents the character from going crazy around the screen. You may notice several things in the system:
- Does 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 that.
This is an absolutely correct question and we can solve it with the help of a navigation system that associates a zone of permissible movement with the nodes of the graph.
How is the graph built?
We will make it from the mix, which we will look at later.
Finding the shortest path in the graph
The most common algorithm for finding the shortest path in a graph is the algorithm A * (A star). 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 on A * is A * Amit page . Essentially, I think he did an excellent job explaining this method, and I'm not even going to try to do better. Read this page! : D
This version of A * is available on my google code repository. Of course, very basic and simple, but it works and finds the shortest paths. Here is a link to the implementation. (The program will crash if the path between the two peaks cannot be found - of course, I will eliminate it in the near future: D)
A * starts work from the starting node and then goes through all its neighbors, and calculates a certain weight value for the nearest vertices. Further, the algorithm is applied recursively for all neighbors with the greatest 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 Amita website .
With A * under 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, if simple, it is just a set of polygons that describe the area in which a character can move. This mesh will be depicted in the background of a pattern using a specially designed tool.
In the upper picture, the blue polygons represent the space through which the player can move. Pink dots are connections between polygons that show where a player can move from one polygon to another. The graph will be created from test pink tie points and the centers of all polygons. The starting and ending points of the graph can be set anywhere inside the blue polygon.
We will build the path from the player's position, to the point of the mouse click. This means that a given point (x, y) of the navigation mesh must be able to determine in which polygon it is located.
The above code can do the trick with finding the polygon, but there is still the question of how to check whether the point is inside or outside the polygon. In this example, all polygons in the navigation mesh are convex and this is rigidly set on the grids, which is built in the editor. Convex polygons help to make test intersections easier, and it is much easier to work with created mixes.
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 an idea — look at the next two canzhi;
Try to determine which of the figures is convex and which is concave - 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 a point is inside the polygon and, as a result, we can check whether mouse clicks fall into the area available for moving the character. If there are no intersecting polygons on the way, then we will not be able to get to the selected point and the click will be ignored.
The last step on the stage is to take the initial and final positions of the character, the centers of the polygons, connect the nodal points and build a graph on which you can run the algorithm A *.
The result of the algorithm will be a list of points along which the character can move. Below is the pseudocode of the movement of the character along the way.
The actual code I use is in the UpdatePath function.
The last step is to render the character's sprite and animate according to the direction of movement. The implemented code already provides movement of the character in the direction of the chosen 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 in a state of rest and three variants of animation. Movement in the direction of "left", "right", "up" and "down" can be implemented programmatically, by means of ordinary transformations.
To map 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, selected the desired animation.
I am sure that you can find a better way, but this option is guaranteed to work. The algorithm finishes work when the character reaches the point of the click and the sprite variant based on the final guide vector will be selected as the last state.
PS The author approved the translation and said that the figures are really both concave, but the translation of one of the canji is convex, the second is concave
How to write adventure
This article will tell you about how the development of adventure games. 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 MIT licenses. The approaches discussed in this article are widely applicable not only for adventure games. For example, the idea of ​​navigation meshes, developed once, is used in games such as Baulder's Gate, Planescape Torment, etc. With only a small change, navigation meshes can also be used in 3D games. The system of interaction with the inventory and the system of dialogues can be modified for most games with RPG elements.
What are adventure games?
Advocates were a popular genre in the early nineties, and more recently began to gain popularity. The most famous quest is probably the “Monkey Island” series, where you play as an ambitious pirate.
The user interface of adventure can vary from game to game, but the picture above shows the Monkey Island interface. The player is available to play the scene, and the character is somewhere within the screen. By default, when you click on the 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 upper picture, you can move courses along the castle on the dungeon cell. The character has several ways to interact with objects and in the game “Monkey Island” they are listed on the lower half of the screen.
Select “Look at”, click “Open” and Guybrush will tell his impression about the castle in a whisper (none of the characters in the game comment on what Guybrush is talking to objects, well, I guess they think he's crazy: D) .
')
The following is an inventory that shows what items the character currently has. Guibrash can interact with things in the inventory, as well as with objects on the game scene.
Now, I hope you got a basic presentation about 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 games 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 dialog system. These characters are also known as NPCs (non playing characters).
How can you break the adventure into subsystems?
Adventure is a long-established genre, which means that the game can be easily 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 above the other, then this means that the lower one is used as a sublayer of the system. This is a good solution for creating isolated and pure architecture. The engine already does a lot for us: loading and drawing sprites, rendering and animating objects, text can be drawn with alignment and various fonts - these parts for the game have already been 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 a character on the game space and sometimes it is important where the hero is located to solve a certain type of task.
Navigation in games in general consists of finding the way. If you want to search for more information on this topic than in this article, then this is the appropriate keyword. The path is a line along which the game character must follow to reach the desired position without passing through walls, tables, small dogs, etc. The 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 path - 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 based on graphs that describe the space of movement of the game character. A graph is a term in their domain of the theory of algorithms (do not worry, the definition is very simple), which is built from a set of vertices and links between them.
The above graph shows only the path between the “Roads from the outside” to the store through the “Door of the store” node. This prevents the character from going crazy around the screen. You may notice several things in the system:
- Does 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 that.
This is an absolutely correct question and we can solve it with the help of a navigation system that associates a zone of permissible movement with the nodes of the graph.
How is the graph built?
We will make it from the mix, which we will look at later.
Finding the shortest path in the graph
The most common algorithm for finding the shortest path in a graph is the algorithm A * (A star). 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 on A * is A * Amit page . Essentially, I think he did an excellent job explaining this method, and I'm not even going to try to do better. Read this page! : D
This version of A * is available on my google code repository. Of course, very basic and simple, but it works and finds the shortest paths. Here is a link to the implementation. (The program will crash if the path between the two peaks cannot be found - of course, I will eliminate it in the near future: D)
A * starts work from the starting node and then goes through all its neighbors, and calculates a certain weight value for the nearest vertices. Further, the algorithm is applied recursively for all neighbors with the greatest 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 Amita website .
With A * under the belt, we can find the shortest paths on the graph, but so far we have not built it.
Using the algorithm navmesh
NavMesh, as you might have guessed, is an abbreviation for the term navigation mesh (grid) and, if simple, it is just a set of polygons that describe the area in which a character can move. This mesh will be depicted in the background of a pattern using a specially designed tool.
In the upper picture, the blue polygons represent the space through which the player can move. Pink dots are connections between polygons that show where a player can move from one polygon to another. The graph will be created from test pink tie points and the centers of all polygons. The starting and ending points of the graph can be set anywhere inside the blue polygon.
We will build the path from the player's position, to the point of the mouse click. This means that a given point (x, y) of the navigation mesh must be able to determine in which polygon it is located.
Polygon FindPolygonPointIsIn(Point point) { foreach(Polygon polygon in _polygons) { if ( polygon.IntersectsWith(p) ) { return polygon; } } return null; } The above code can do the trick with finding the polygon, but there is still the question of how to check whether the point is inside or outside the polygon. In this example, all polygons in the navigation mesh are convex and this is rigidly set on the grids, which is built in the editor. Convex polygons help to make test intersections easier, and it is much easier to work with created mixes.
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 an idea — look at the next two canzhi;
Try to determine which of the figures is convex and which is concave - 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.
/// /// , . /// <a href="http://local.wasp.uwa.edu.au/%7Epbourke/geometry/insidepoly/">http://local.wasp.uwa.edu.au/~pbourke/geometry/insidepoly/</a> /// /// 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 a point is inside the polygon and, as a result, we can check whether mouse clicks fall into the area available for moving the character. If there are no intersecting polygons on the way, then we will not be able to get to the selected point and the click will be ignored.
The last step on the stage is to take the initial and final positions of the character, the centers of the polygons, connect the nodal points and build a graph on which you can run the algorithm A *.
The result of the algorithm will be a list of points along which the character can move. Below is the pseudocode of the movement of the character along the way.
- Get character position -> pc_position
- Get the position of the current point on the path-> target
- Get the direction pc_position to target -> direction
- Add direction * walkspeed to pc_postion
- Check whether 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 animate according to the direction of movement. The implemented code already provides movement of the character in the direction of the chosen 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 in a state of rest and three variants of animation. Movement in the direction of "left", "right", "up" and "down" can be implemented programmatically, by means of ordinary transformations.
To map 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, 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 am sure that you can find a better way, but this option is guaranteed to work. The algorithm finishes work when the character reaches the point of the click and the sprite variant based on the final guide vector will be selected as the last state.
Let's put it all together
PS The author approved the translation and said that the figures are really both concave, but the translation of one of the canji is convex, the second is concave
Source: https://habr.com/ru/post/148632/
All Articles