First、roguelike Map introduction
Roguelike is an RPG game with a random map. The randomly generated map, props and other elements on each layer are the characteristics of this type of game. I won’t go into details about its specific introduction.
The following will introduce the use of hill algorithm (Hill Algorithm) to achieve random map generation.
Before that, let’s briefly explain the basic information of the map:
- The size of the map: 30×30 grids;
- Grid of the map: wall or open space, use IsFloor to indicate whether the grid is open space, see below for details.
Second, the general steps of the hill algorithm
The hill algorithm is an algorithm borrowed from random walking (a model implemented with Berlin noise). This algorithm assigns a “weight” to each element as a basis for generating random terrain.
The general steps are as follows:
- Randomly assign weights to the elements on the two-dimensional array (the weights start with 0, and a total of 5 weights from 0 to 4 are used in this article);
- Smooth weight;
- Hole (ie floor) repair;
- Eliminate isolated holes (ie walls);
- Detection and penetration of the cavity area;
- Tortuous supplement of full acupoints.
See the specific steps below.
Third, initialize the map
In VB6, first define the grid of the map as follows:
Whether the grid is empty;
Weights;
Whether it is marked, the marking is used for regional and other processing;
Area number.
Code：
Private Type tMap
IsFloor As Boolean
Weight As Integer
Marked As Boolean
Area As Integer
End TypeThe map array Map is a two-dimensional array whose type is tMap.
In addition, it is stipulated that the outermost circle of the map must be a wall, so in fact, the randomly generated part of the map is a grid between 1-28.
Private Sub InitMap()
For M = 0 To 29
Map(M, 0).IsFloor = False
Map(M, 0).Weight = 4
Map(M, 0).Marked = False
Map(M, 0).Area = -1
Map(M, 29).IsFloor = False
Map(M, 29).Weight = 4
Map(M, 29).Marked = False
Map(M, 29).Area = -1
Map(0, M).IsFloor = False
Map(0, M).Weight = 4
Map(0, M).Marked = False
Map(0, M).Area = -1
Map(29, M).IsFloor = False
Map(29, M).Weight = 4
Map(29, M).Marked = False
Map(29, M).Area = -1
Next M
For N = 1 To 28
For M = 1 To 28
Map(M, N).IsFloor = False
Next M
Next N
End SubFourth, random weighting
Perform a random weighting on the grids on the map (excluding the four sides), that is, assign random numbers generated from 0 to 4 to 28×28 grids on the map.
Private Sub GenerateRandomMap()
Randomize
For N = 1 To 28
For M = 1 To 28
Map(M, N).Weight = Int(Rnd * 5)
Next M
Next N
End SubFifth, smooth weight
There are generally several ways of smoothing weight:
1.The mean value sampling is smooth. The average of 9 grids including one week of the grid and itself is smoothed. This smoothing mode is relatively simple, but the smoothing effect is the most unsatisfactory.
2. Manhattan distance sampling is smooth. Take the average of the sample sum of the grid itself and the grid within the specified Manhattan distance. This smoothing mode takes into account the influence of the Manhattan distance on the target grid and is a better smoothing method. In this article, the smoothing method is adopted, and the Manhattan distance is 1.
3.The two-dimensional normal distribution is sampled and smoothed once (also called “one-time Gaussian smoothing”). This kind of smoothing is based on the Manhattan distance, using the normal distribution function for smoothing. The smoothing effect is better than the Manhattan distance sampling smoothing. However, because the function is too complex, this article does not use this method. If you are interested, you can use it. This way.
Code：
Dim rMap(1 To 28, 1 To 28) As Integer
For N = 1 To 28
For M = 1 To 28
rMap(M, N) = GetSum(M, N)
Next M
Next N
For N = 1 To 28
For M = 1 To 28
Map(M, N).Weight = rMap(M, N) / 5
Next M
Next NAfter smoothing the weights, these data should be binarized to realize the separation of walls and floors. Because the weight range is 0-4, the weight of (4-0)÷2=2 can be used as the critical point to convert the weight into terrain data.
Set the grid with a weight of 2 as an empty space, and set the other grids with a weight of not 2 as walls, and you can get the following code:
For N = 1 To 28
For M = 1 To 28
If Map(M, N).Weight <> 2 Then
Map(M, N).Weight = 4
Map(M, N).IsFloor = False
Else
Map(M, N).Weight = 0
Map(M, N).IsFloor = True
End If
Next M
Next NThe following are the renderings before and after smoothing:
before：
after：
Sixth, hole repair
For an open space grid, when the surrounding grids are all walls, convert this grid to a wall to achieve the following effects:
□■□ □■□
■□■ → ■■■
□■□ □■□
Code:
For N = 1 To 28
For M = 1 To 28
If Map(M, N).IsFloor And Map(M - 1, N).IsFloor = False And Map(M + 1, N).IsFloor = False And Map(M, N - 1).IsFloor = False And Map(M, N + 1).IsFloor = False Then Map(M, N).IsFloor = False: Map(M, N).Weight = 4
Next M
Next NThe results are as follows：
Seventh, isolation and elimination
Elimination of isolated holes refers to the elimination of walls that are not closely related to walls in other locations on the map. It is stipulated in this article that when the number of wall grids around a wall grid is less than 2, the grid will be regarded as “isolated and full of holes”.
In order to ensure that there are no isolated full holes on the map, multiple iterations of elimination processing are required until the map shows a “stable” situation, that is, when all the grids on the map no longer change, then the next step can be entered.
The following is part of the code to eliminate the full hole in a single isolation:
Dim rMap(1 To 28, 1 To 28) As Integer
For N = 1 To 28
For M = 1 To 28
If Map(M, N).IsFloor = False And GetWallCount(M, N) < 2 Then
mCheck = True
rMap(M, N) = 0
Else
rMap(M, N) = Map(M, N).Weight
End If
Next M
Next N
For N = 1 To 28
For M = 1 To 28
Map(M, N).Weight = rMap(M, N)
Map(M, N).IsFloor = Map(M, N).Weight = 0
Next M
Next NThe following is the first time the effect of isolation and elimination of acupuncture points:
The following is the effect of eliminating full cavities in a stable state：
8.Cavity area detection and penetration
In order to ensure that the player character can act in all open spaces on the map, it is necessary to ensure that all open spaces on the map are connected.
It is stipulated that each open space enclosed by walls on the map constitutes a set, which is called “Area”. There may be several areas on a map. The next thing to do is to ensure that only one area exists on the map. .
Get all the areas on the map by traversing the open space. As shown in the icon below, there are two areas on the map, one is a very large area made of green area 1, and the other is a smaller area 2 in the lower right corner of the map.：
In order to make the number of areas to 1, it is necessary to penetrate a smaller area. This article adopts the method of “random spreading corrosion”, that is, for each grid in a small area, the surrounding walls have a 75% probability of becoming empty and spreading. When an open space grid with a different number from the current area is detected, it stops spreading, so that the hole can be penetrated.
If there are more than 2 areas on the map, it is necessary to perform repeated operations to penetrate and check the number of areas until the number of areas is 1.
Part of the code for this step is as follows:
Private Sub ExpandArea(ByVal X As Integer, Y As Integer, AreaID As Integer)
If Map(X, Y).Marked Or X = 0 Or X = 29 Or Y = 0 Or Y = 29 Or Map(X, Y).Area = AreaID Then Exit Sub
Map(X, Y).Marked = True
Randomize
Dim i As Integer, j As Integer
For j = -1 To 1
For i = -1 To 1
If (i = 0 Or j = 0) Then
If (Rnd * 100 <= 75) And Map(X + i, Y + j).IsFloor = False And _
X + i > 0 And X + i < 29 And Y + j > 0 And Y + j < 29 Then
Map(X + i, Y + j).IsFloor = True
Map(X + i, Y + j).Weight = 0
Map(X + i, Y + j).Area = Map(X, Y).Area
ExpandArea X + i, Y + j, AreaID
End If
End If
Next i
Next j
End SubNine, full point tortuous supplement
The function of this step is to increase the tortuosity of the map and avoid the appearance of a large area of open space. In this paper, the method of calculating the Manhattan distance is used to generate the wall (full hole), that is, when the number of walls in the grid within the specified Manhattan distance (2 in this article) is 0, this grid is set as the wall.
The following is the relevant code:
Dim rMap(3 To 26, 3 To 26) As Boolean
For N = 3 To 26
For M = 3 To 26
If Map(M, N).IsFloor Then
If GetFloorCount(M, N) = 13 Then '曼哈顿距离计算该距离该位置2格的格子为空地的计数
rMap(M, N) = False
Else
rMap(M, N) = Map(M, N).IsFloor
End If
End If
Next M
Next N
For N = 3 To 26
For M = 3 To 26
Map(M, N).IsFloor = rMap(M, N)
Map(M, N).Weight = IIf(rMap(M, N), 0, 4)
Next M
Next NThe following is the rendering：
At this point, a decent Roguelike map is ready.