Shulou(Shulou.com)11/24 Report--

Random maps are a very core element for Roguelike games, and random maps are still very active in many Diablolike games. We may have seen a lot of random map generation algorithms, including but not limited to the sharing of well-known game communication media such as GDC and GMTK. However, most random algorithms require manual preset of most of the levels, including famous games such as Diablo, which assemble some maps in advance, and then just randomly select a few of these maps at random locations. After all, the advantage of this is that the map looks beautiful, and there will be no dead pictures (that is, the entrance can not lead to the exit), and the location of the brush is relatively reasonable.

(random map generation algorithm is an important topic in Roguelike games) so is there a random algorithm that does not need to manually preset content, only needs to adjust some parameters, it can generate a beautiful look, will not produce a dead picture, but also can ensure that the generated bizarre point location is reasonable? Today we will deeply explore a pathfinding algorithm-Dijkstra algorithm. As long as we slightly adjust the "technique" used, this wonderful algorithm used to find the shortest path will become an extremely powerful random map generation algorithm, and for numerical planners who are proficient in designing mathematical functions, we can easily play with this "Dijkstra random map generation method" with a few parameters.

01. In-depth interpretation of Dijkstra algorithm We usually know that Dijkstra is an algorithm for finding the shortest path between two points, which is often on a par with his two special shape Floyd algorithm and AStar algorithm.

The Dijkstra algorithm itself is very easy to understand, that is, take a certain point in the map as the starting point, then look in all directions, add a Cost value to each grid, and then calculate the shortest path into the grid for each grid on the map, that is, the one with the lowest Cost value leads to the grid from the starting point to the grid, and finally gets the shortest route after traversing all the grids. As shown in the figure:

(the pentagram is the starting point, the fork is the end point, and the number in the grid is the Cost of the shortest path into the grid.) in most cases, Dijkstra is very expensive, so the combination of Greedy Best-First ideas leads to AStar pathfinding. But Dijkstra did not quit the game development stage because of the emergence of AStar, he is still active in the board game SLG:

(the picture shows the range of movement of the character in the "Fire pattern") in the chess SLG, the range of movement of the character can be obtained by the Dijkstra algorithm, after all, the action force of each character is limited, and the terrain in the map will affect the action power, at the same time, the action force consumption of the enemy character's adjacent grid will be further increased, so the Dijkstra algorithm is cleverly used to "not look for the target point, but find the point where the action force is sufficient to reach".

Here is the introduction of the most basic Dijkstra algorithm, and then we need to think about some questions further. When we usually use the Dijkstra algorithm, the rule of checking the cell is "surrounding grid", but if some cells are a portal entrance, you can choose one of the n exits after entering, what changes do the pathfinding algorithm need to make? As shown in the figure:

If green is the starting point and red is the end point, our pathfinding usually produces a black line, but when we add a portal entrance (blue circle) to the map and walk into the portal, the problem arises when you can choose any one of the three orange circles as the exit, because the blue grid represents three other squares at once. So we can find that, in fact, when we only use the Dijkstra algorithm for pathfinding in Tilebased games, we take it for granted that the "surrounding grid" as the "next grid" is a part of this algorithm, but in fact, for the Dijkstra algorithm, how to select the "next grid" is a part of the design.

As shown in the figure above, the "next grid" of the Dijkstra algorithm is actually "the next node", which is added to the decision list according to a rule. If it is a portal, it should be like this:

Since walking into B is equivalent to walking into B1 or B2 or B3, we interrupt the "non-existent grid" of B and link B1\ B2\ B3. This is one of the cores of Dijkstra algorithm-"Node rules of paths".

02. Preparation of random maps after understanding the nature of the Dijkstra algorithm, we will begin to prepare to use it skillfully to generate random maps. But before that, we still need some steps, these random map generation steps do not need the Dijkstra algorithm.

Here, the first thing we need for numerical planning and design is: map information = f (maze, number of layers). The original intention of this function is to calculate some information of the current map according to the difficulty coefficient of the map. This information should at least include:

Number of rooms: we know that most roguelike maps require rooms, and the more rooms there are, the more difficult the maze is for players. Therefore, for us to generate a map, the number of rooms is also a core data, do not know the number of rooms can not generate a random map with appropriate difficulty.

Maximum and minimum size of each room: the width and height of this size can be different, but we'd better think that they are equal, so as to make the position of the room relatively more uniform. The minimum size should be less than the maximum size, if equal will also affect some random effects.

The minimum number of cells for the connection between rooms: there still needs to be a route connection between rooms, and the minimum length of the route can be required, which should be a natural number. If it is 0, it may generate 2 rooms next to the wall, which will affect the appearance. Of course, this can also be corrected after generation, such as eliminating a wall.

The maximum number of cells connected between rooms: this should be an existence greater than the minimum tile number, so that there is room for random.

Room Monster count Information: this information will be used to generate refresh points for monsters.

Minimum number of passing rooms: we know that there may be a demand for Roguelike maps, that is, at least how many rooms I have to walk through before I can meet the entrance to the lower floor after I reach this floor. If this value is 0, it is possible to go downstairs in the first room on this floor; of course, this number must not be greater than or equal to the number of rooms, otherwise you will not be able to get through. It is recommended to take half of the number of rooms.

When the above map data is obtained, we can determine the number of "blocks" needed for the horizontal and vertical direction of the map on this floor, the so-called "blocks" is the range of each random room. To ensure that the map is as close to the square range as possible (this is just for "beauty"), you can do this: the number of horizontal blocks = (the square root of "number of rooms") is rounded up, and the number of vertical blocks = (total number of rooms / number of horizontal blocks) is rounded up. In other words, for example, a map of seven rooms is divided into 3x3 blocks, as shown in the figure:

We can simply calculate the cell number of a "block": horizontal grid number = room maximum horizontal grid number + horizontal line maximum tile number; longitudinal grid number = room maximum longitudinal grid number + longitudinal line maximum tile number. When the number of cells in each block is multiplied by the number of blocks, the total number of horizontal and vertical cells of the map can be calculated.

When the cell is determined, we need to solve a problem, that is, the number of blocks > the number of rooms. If it is equal to, there is no problem, but if it is greater than, we have to randomly take out (total number of blocks-number of rooms) rows (or columns), and then delete a "block" from these rows (or columns), as shown in the figure.

We randomly selected lines 1 and 3, each with a "block" removed. In this way, the number of rooms is exactly 2-3-2-7. Then we randomly divide each row into blocks, and this process determines the number of horizontal and vertical cells each "block" has. This minimum number of cells should not be less than the minimum width (height) of the room + the shortest number of horizontal (vertical) connected cells. The block after sharing is likely to look like this:

From the above picture, we can see that after the block is cut, the connection diagram between "block" and "block" is also produced (the connection relationship between "block" and "block" is only listed in the figure above), and there is only one room in each "block". So the connection of the "block" is also the "preliminary connection" of the room, because we will break some connections later.

After determining the connection, we have to randomly find a random point in each "block" as the "central point" of the "block" room, and the scope of this central point must at least meet the requirements of the longest and shortest link cell in the room. At this point, the attribute of each "block", that is, the basic data for each room, is generated, which contains:

Room id: the id of this room

Center point coordinates: this is the core data used to generate the room.

Linked room array: the id array of rooms to which this room can be connected.

At this point, our preparatory work is complete, and then we will begin to generate important algorithms for the room. First of all, let's review, what kind of work should a numerical planner do here?

1. Calculate the map information according to the maze and the number of layers: this is the most basic data for random map generation.

2. Slicing algorithm: although an example is given in this article, this is not the only example. Of course, we can use other mathematical methods to determine the way of slicing and room connection. In short, you can finally get the data of each "block".

03. Clever use of Dijkstra to generate "rooms" when we have finished the data of each "block", we can traverse each "block" and generate the room for each block. First of all, we have to come up with:

The center of the room, which is the "pathfinding starting point" of our Dijkstra algorithm.

The size of the room: take the larger one of the width and height, then divide it by 2 and round it down, as a Cost value, assigned to the starting point.

With these two messages, we begin the rule of "taking eight surrounding squares as the next grid" as the "next grid" rule of the Dijkstra algorithm. The moving range of the SLG search is similar to that of the war chess game, but the only difference is that the Cost consumption of this cell is random, and this random is not brainless random 1-2. It should have an algorithm, such as the closer to the starting point, the less easy it is to be 2. This is the most basic rule, as shown in the figure, is to "find the way":

Cost=f (...) It is this random algorithm, based on the information of this room ("block"), of course, you can also pass in more needed information, depending on the design of the game.

There are two basic reasons for using Dijkstra algorithm to generate rooms:

One is that the room is not necessarily rectangular in the end. Of course, if the cost is all 1, then it is a square at last. This is a special case. Usually, we still want the room to be non-rectangular, so we need to use Cost's algorithm and Dijkstra algorithm to generate a "non-rectangular" room, as shown in the figure:

The cost=0 (red) grid is used as a wall, and the room is generated. Of course, we just need to adjust the Cost=f (...) An interesting change can take place:

For example, it is easier to draw a high cost in the y direction, which makes the map closer to the flat one:

For example, when the y value of the lattice is greater than the starting point y value (lower lattice), then cost = initial cost:

It can be seen that as long as you adjust the Cost=f (...), you can make the shape of the map close to the desired effect of the design, and here will add a question of how the blocking and brushing strange points in the room are produced. As a matter of fact, we already have the rule of expanding from the center, so the bizarre point and blocking can be completely consistent with: IsPoint = f (XQuery y, cost) is a mathematical function, that is, whether this point brushes or blocks is determined by the parameter XQuery y and the remaining cost value of the lattice. For example, "three random points from all Cost=3 squares are selected as bizarre points", and these bizarre points will be close to the middle, so that players who enter the room, no matter which direction they come from, will not encounter the situation of being "strangely pasted to the face" (of course, not all games need to be bizarre in the first place).

At this point, the generation of a room is complete, and we draw a conclusion from this generation process:

The shape of the room: the whole room occupies those squares, which of which are blocking cells.

Brush strange point: the strange brush cell in the room, as for what is strange to brush above, it is not decided by the room, it is calculated by the floor information, difficulty, etc., here is just to provide the monster with their birth location.

At this step, the core work of numerical planning is:

The Cost algorithm for each lattice, that is, Cost=f (...) , including its parameters and the calculation process

Brush strange points, blocking algorithm, according to the situation of each grid, calculate whether the current grid is blocking or brushing strange points.

As long as the algorithm is well designed, it can be used to generate maps for any Roguelike game, even for horizontal action games.

04. Clever use of Dijkstra to generate "Route" when the room is generated, we can use AStar to generate the connection cells between the two rooms, which is a very simple thing, but before that, we still have a job. Do you remember the "minimum number of passing rooms" at the beginning? The way to meet this demand is to break some of the connections between the rooms to ensure that the route is up to standard.

First of all, we need to determine the connection between the rooms (or the original "blocks") and make a "map":

Then we get the random starting point and end point through this map. If the "minimum number of passing rooms is more than 0", then the starting point and the end point must be two different grids, assuming that the "minimum number of passing rooms" = 3, the starting point is 3, and the end point is 6. Then we have to break some connections:

What we need to break is the key link where the distance from the start to the end will be less than 3. After breaking the key links, we can also break several of them in non-critical places, which can still be based on an algorithm designed by numerical planning.

To sum up, even if the random map of the first floor is produced, the room, monster, block, treasure chest and so on can be calculated by the clever use of the Dijkstra algorithm, and the key of all this lies in the numerical planning for the design of some mathematical functions.

When in-depth understanding of the actual working principle of an algorithm, think about and modify its usage, so as to achieve some "non-popular" uses, which can often play a wonderful effect in game design. The key depends on the designer's ability to use it well-"there are no inferior spells, only low-level wizards."

This article comes from the official account of Wechat: game Design of Thousand Monkeys and horses (ID:baima21th), author: monkey and Huaguo Mountain

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.