I am participating in the nuggets Community game creative submission Contest. For details, please see: Game Creative Submission Contest
This paper introduces an algorithm for generating balanced and fair game maps for civ, Isle of Catan and other strategic multiplayer games by using programmatic modeling (PCG).
Symmetry versus Game introduction
Symmetry versus game refers to a fair and symmetrical zero-sum game in which players have the same or similar resources, interaction modes, restricted rules and ultimate goals. Such as heroes, Civilization, Catan and other games.
We built a multiplayer turn-based strategy game with reference to the 4X element of civilization [1], as shown below: the map began to be covered by the “Fog of War”. The player must send explorers into the fog to reveal land to expand, resources to exploit, and opponents to destroy.
A measure of map balance
We draw on two references [2] and [3] to develop two metrics for evaluating symmetry versus game map balance.
1. Strategic Features
Strategic features are the strategic resources available to the player in the game. Balance of strategic characteristics is when each player gets roughly the same amount of resources (both type and quantity) for a given amount of time.
The two graphs below show the imbalance between the strategic characteristics of the two players. The blue player has more mineral resources to start with, while the yellow player has almost no mineral resources near his birth point, which limits the yellow player’s development in the early game.
 |
 |
|---|
2. Player placeholder
The distribution of the player’s initial birth slots also affects the balance of the game.
The following two graphs show how the player’s initial placeholder distribution density can lead to gameplay imbalances. On the left, the initial distribution of players is dense, which causes players in this area to crush each other in the early stages of the game and become limited; The yellow player on the right has less competition early in the game and is better able to develop.
 |
 |
|---|
In addition to the above two effects on game balance, random maps in strategy game maps also need to be considered: beautiful maps, customized parameters based on player preferences, efficient map generation, etc.
Map generation process
1. Customize map metrics based on player preferences
Before creating a new game, we allow players to customize the map parameters according to their preferences, including map size, total number of players, map type (Pangea, continent, island group), water ratio, vegetation ratio, rock ratio to resource ratio, etc.
2. Generate map outline: Berlin noise
Perlin Noise refers to the natural noise generation algorithm invented by Ken Perlin [4]. In game development, Perlin noise can be used to generate wavy, undulating textures or textures. As shown below:
Compared with salt and pepper noise, Berlin noise has better continuous distribution, which can better simulate the distribution of terrain and surface decoration in nature. Natural generated by Berlin noise map can refer to: www.bilibili.com/video/BV1sJ…
Unity’s official function to generate Berlin functions. We use the Berlin Noise JS library for terrain implementation. We use the sampling scale of Berlin noise to determine whether the map type is continuous continental map or discrete continental map. The continuous noise equalization randomly selected was used as the height map of the map, and the sea level height was determined according to the water body proportion set by the user. The final terrain result was shown as the figure below:
3. Player birth point selection: Mitchell’s best candidate algorithm
To ensure that the initial distribution of each player pair is not too close together, we sampled the player’s initial placeholders evenly on land after generating the game’s terrain. In order to balance effect and efficiency, we finally choose Mitchell’s best candidate algorithm.
Mitchell’s best candidate algorithm is an incremental and incremental uniform sampling method. In each round of sampling, the point with the smallest distance and the largest distance from all sampling points of the previous round is reserved as the sampling result of this round. As shown in the figure below: The black point is the sampling point that has been determined in the previous round, and the gray point is the candidate point for random sampling in this round. Each candidate point is selected with the nearest distance to the sampling point in the previous round, and then the red point with the smallest distance and the largest distance is selected as the sampling result of this round.
By sampling the player’s initial placeholder in this way, the game balance can be avoided if any two players are too close to each other, as shown below:
4. Distribution of strategic resources
After sampling the distribution of players, we divided the map cells into two types: Player Zones for cells within N of each Player placeholder, and isolated or Natural Zones for cells that were not part of any Player zone.
In order for each player to have a fair strategic character at the start of the game, we assigned a quota of vegetation, rocks, and minerals to each player’s player area. Calculate the amount of vegetation, rocks, and resources that should be allocated to each player area based on the proportion of vegetation, rocks, and resources that the user has set, and then sample the same number of vegetation, rocks, and resources cells in each player area without leakage.
For natural areas, we sampled each resource evenly using the Mitchell candidate algorithm based on player-set parameters. This ensures that every player gets the same number of strategic features at the start of the game. As shown below:
 |
 |
 |
|---|
5. Boundary situation processing
In some cases, the map generated in the above way will produce bad results. For example, when the proportion of water body is too low, island terrain will be generated, which will lead to insufficient water body to divide island terrain. When the proportion of water is too high, the strategic resources available to players born on islands of different sizes are again unbalanced due to uneven distribution of land cells. For these boundary cases, we use heuristic generation methods such as seed growth and flood filling to generate maps. We give priority to ensure that the map types can meet the needs of users, and ensure that water bodies and resources with various strategic features are as close as possible to the user’s Settings. The following is the map generated when the water body proportion is too low or too high. It can be seen that the balance of the generated map can still be guaranteed under these two conditions:
 |
 |
|---|
Quantitative assessment of the quality of generated maps
In order to determine whether our random map generation algorithm has good balance indicators, we designed a set of automatic map expansion algorithm: each player expands one cell in turn with birth point placeholder as the seed, until all the cells in the map are occupied by one and only one player. Then we counted the number of resources each player captured, the distance to the nearest enemy, and how many player territories each player was adjacent to. As shown below:
The experimental group is the map generated by our algorithm, while the control group is the map obtained by randomly sampling terrain and randomly sampling player distribution according to the ratio of water body to various resources. On the left is the map generated by the experimental group, and on the right is the map generated by the control group:
| The experimental group | The control group |
|---|---|
 |
 |
The experimental group and the control group each generated 100 times of maps, and counted the mean and variance of the minimum distance between each player and other forces, the mean and variance of the possession of each resource after expansion, and the mean and variance of the potential conflict forces of each player. The statistical results are as follows:
According to the quantitative statistical results, the map generated by our method has a larger average minimum distance between players, which indicates that the placeholders for each player’s birth point are more balanced. The distribution variances of all resources are smaller than those of the control group, indicating that our distribution of strategic features is more balanced compared with the naive randomly generated map.
To sum up, our map generation results ensure the balance of a symmetric multiplayer strategy game.
Online Experience Address:huanggaole.itch.io/cition
reference
[1] Ford, Dom. “eXplore, eXpand, eXploit, eXterminate “: Affective Writing of Postcolonial History and education in Civilization V.” Game Studies 16.2 (2016)
[2] Jakub Kowalski, Radoslaw Miernik, Piotr Pytlik, Maciej Pawlikowski (2018). Strategic Features and Terrain Generation for Balanced Heroes of Might and Magic III Maps. 2018 IEEE Conference on Computational Intelligence and Games
[3] Pereira, Prada, Rui. (2009). Self-adapting dynamically generated maps for turn-based strategic multiplayer browser games. Proceedings of the International Conference on Advances in Computer Entertainment Technology, ACE 2009, Athens, Greece, October 29-31, 2009
[4]Ken Perlin. An image synthesizer. SIGGRAPH Comput. Graph, 1985, 19: 287 — 296.