|
The 2018 Settlement Generation Competition was the first iteration of the Generative Design in Minecraft Settlement Generation Challenge. The results were presented at the Foundations of Digital Games conference in Malmö, Sweden. There were 4 entries for this first iteration. Overall, judges were excited about the adaptability of several of the settlements, and the wide variety of aesthetic types. However, none of the settlement generators produced cities with much variety or narrative. The best generator received a score that amounted to a performance just under what would be expected from a human being who is new to Minecraft and building cities within the game. Please see each of the contestant's own pages for a detailed description of their generator. |
|
Entry Descriptions
All submission descriptions are taken from the user-input about box during submission!
Filip Skwarski
The algorithm generates settlements in a bottom-up fashion by continuously filling the map with new structures. It is loosely inspired by the way human players build settlements: rather than following a fixed plan, they may construct and expand settlements in different ways depending on practical and aesthetic considerations, such as available resources and the shape of terrain. The algorithm models this process by scoring a large number of possible structures with regard to specific features in order to select the optimal candidate to generate next, given all previously generated structures and the shape of surrounding terrain.
The process works as follows:
Generation starts with a fixed list of structures to be generated. In the submitted version, the structures alternate between houses of two types, plazas, and farms. All structures are currently symmetrical, but their sizes are randomized.
The algorithm then progressively adds requested structures to the map. Every step involves selecting an optimal position and direction for a new structure out of a number of candidates. Ideally, every position on the map should be evaluated, but this is only possible in reasonable time for small maps. In the submitted version, 5,000 placements closest to a randomly selected structure (or centre of map, if there are none) are considered.
Every candidate is assigned scores corresponding to a number of features. Features include the discrepancy of terrain elevation around its location, distance to other structures (both negatively correlated with higher score), and the degree to which new structures match a realistic layout of a town. In order to measure this, every generated structure is assigned a number of “templates” for possible expansions (e.g. a plaza should have buildings surrounding it, a house should have neighbours, etc.). The layout score is calculated based on how much new structures overlap with these templates, thus imposing ‘soft’ constraints on the way the town can expand. Farms use their own set of features, including symmetrical alignment with existing structures.
The scoring function is currently a simple Python sort of the lists of individual feature scores. Scores follow a fixed order (elevation score > layout score > distance score), meaning that e.g. a structure with a high elevation score will take precedence over a structure with a high layout score, but lower elevation score. Other scoring criteria may be used (my original intention was to use a multiplicative score where every feature as well as the final score is a value between 0 and 1, but while this produced better-looking results for flat terrain, I could not resolve certain problems resulting from the interactions with roads and elevation in time before the submission deadline).
The top candidate is generated and stored and its basic shape is added to the map. Since it is not feasible to run a pathfinding algorithm for every candidate, a new road is only added after a new building is generated by connecting it with its closest neighbour. Roads are generated using the A* pathfinding algorithm. In order to prevent them from ascending and descending hills diagonally, areas around 'corners' of hills are marked as impassable by default. This also means that in some cases, a road may end up not generated.
The process is repeated until all requested structures are generated, for as long as there’s enough space to generate them. The final step is to clear trees, optionally add fences, and generate the final shape of all structures. While the variety of buildings in the submitted version is very limited and the buildings are empty, the percentage of wooden buildings in a settlement and the material from which wooden structures are generated is determined based on the frequency and type of trees in the area, adapting the look of settlements to the environment to some degree.
The submitted algorithm is limited, but demonstrates the feasibility of terrain-adaptive, bottom-up settlement generation by ranking candidate structures. Certain elements (like road generation or scoring) may be reworked and new features (such as non-symmetrical buildings, districts, bridges, etc.) may easily be added without changing any of the core principle or disrupting existing features. It is also possible, in theory, to make the scoring algorithm data-driven, or to use backtracking to optimize placements with regard to future steps.
Adrian Brightmoore
Run this with a selection box around chunks that are present, and the Seed set to 0.
The selection box is scanned to generate a height map (ignoring trees and vegetation).
The heights are then examined to identify cliffs and steep banks and these are marked on an image corresponding to the landscape. Then flat sections are selected from this image and buildings are generated on them. To cater for height variance the buildings are flood-filled underneath with blocks to replace air/water/lava/grass. The location of points corresponding to the building are removed from the possible set of locations, and the process is repeated.
This creates houses in the landscape placed on the landscape where it is flat or gently sloping.
TODO: This entry is testing the water to see what would be required to participate.
Changxing and Shaofang
PartA : build different type of house depends on the size of BOX
PartB : build Road through houses with A star algorithm.
Rafael Fritsch
First, the building site is repeatedly bisected with roads to generate individual plots. The contents of each plot are chosen based on criteria such as size and distance to centre. Building materials are chosen based on the blocks occurring in and around the filter box.
Different crops are planted, depending on biomes and availability of fertile ground, A season is randomly selected to determine the growth progression of crops.
Results
| Entry # | Author | Adaptability | Functionality | Narrative | Aesthetic | Overall Score | Files | |
|---|---|---|---|---|---|---|---|---|
| 1 | Filip Skwarski | n/a | 5.42 | 4.71 | 3.17 | 4.21 | 4.38 | code |
| 2 | Adrian Brightmoore | @TheWorldFoundry | 2.33 | 2.21 | 2.13 | 3.54 | 2.55 | code |
| 3 | Changxing and Shaofang | n/a | 0.96 | 2.96 | 2.13 | 2.75 | 2.20 | code |
| 4 | Rafael Fritsch | @UrsaMinorDev | 2.81 | 3.25 | 2.46 | 3.79 | 3.08 | code |