2019 Settlement Generation Competition

The 2019 Settlement Generation Competition was the second iteration of the Generative Design in Minecraft Settlement Generation Challenge. The results were presented at the Foundations of Digital Games conference in San Louis Obisbo, California, USA. There were 6 entries for this first iteration. Overall, judges were excited about the obvious improvement from the previous year's competition. Settlements across the board were very adaptable to the terrain, foliage, and water features. There were a wide variety of aesthetic types and significant improvement in external building variety. Judges expressed an interest in seeing more narrative design for all entries. The best generator received a score that amounted to a performance of 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.

winner.png


Year 2019
Location San Luis Obisbo, California, USA
Conference FDG 2019
Submission Count 6
Winning Entry Filip Skwarski
Maximum Score 5.50
Average Score 4.665

Entry Descriptions

All submission descriptions are taken from the user-input about box during submission!

Adrian

For diagrams see here:
http://www.brightmoore.net/what-s-happening-now/gdmc2019-proceduralsettlementgenerationinminecraftround2

Framework:
The approach I have taken to settlement generation involved identifying plots of existing landscape that can accept a building and then placing clusters of rooms on them. I populate the buildings with contents and then connect the buildings together with paths. The areas between the building plots are strung with low wall sections, and some farm land with various crop types are placed where possible. Building types include houses, towers, and a village square with a fountain.
Placement of generated schematics on the landscape requires some minor adjustments to parts of the landscape. Sometimes it is necessary to create sections of building foundations to prevent parts of the flooring floating over air.

Buildings:
Buildings are a collection of rooms packed close to each other using a simple packing algorithm. The contents of the rooms are determined from a simple blueprint that associates the room type with a generation procedure. Orientation of blocks to line up with walls and avoid windows is done through the generator inspecting the area and making appropriate layout decisions.
Windows, lighting, and doors are punched through the assembly at intervals to provide passage for the inhabitants.

Room Contents:
Carpet, crafting tables, furnaces, chests, beds and chairs are placed according to the room type to provide simple functional capabilities that an inhabitant might require.

Building placement:
The algorithm profiles the landscape using a heightmapping approach. It then attempts to isolate areas of severe terrain height change, and then searches the remaining gently sloping areas for square sections that can be used to place buildings.

Each settlement is defined by a blueprint which is a collection of feature generator names. The generators are delegated the responsibility to populate the region of the landscape with features. This framework is extended by adding a generator to the blueprint for a village.

Towers:
The tower variant of building has been introduced to provide a watchtower to the settlement. It was primarily created to show how generators can be created using python and the features of the pymclevel library. A worked example is in this thread: https://twitter.com/TheWorldFoundry/status/1087616035992170496
The structure of a tower shows some of the procedural methods used to create it.

Paths between plots:
Each building plot centre is an anchor point that can be used to mark paths between the plots. By adjusting the number and weights of path plotting the settlement can get a ‘lived in’ feel.

Walls:
Establishing a voronoi graph for the plots in the settlement creates sections of landscape where walls can be placed.

Farmland:
Adding a farmland generator was then as simple as creating a blueprint entry and writing the corresponding generator to create farmland, water source, fences and crops.

ArtCodeOutdoors

Our algorithm is a conceptual exploration of the idea "What if one were to design a Minecraft settlement by explicitly following a traditional city planning approach?"

Berlier

A settlement generator that builds houses, large wheat fields, and windmills!
The zip file contains a Forge mod, a README with instructions for running the generator and a pdf describing how the generator works.

ehauckdo

UrbanSettlementGenerator aims at generating modern cities given a Minecraft map. It generates houses and apartment buildings, connecting all of them with roads. The buildings are generated according to a downtown/outskirts division, with apartment buildings placed towards the center and houses placed towards the edges of the map.

Houses have walls made of double stone slab and pitched roofs made of wood. They have one oak door as the entrance on one random side, and glass windows on the walls perpendicular to the door wall. Houses are furnished with carpets, a table in the center of the room, a chandelier on the ceiling, and a bed, bookshelf and couch in the corners.
Apartment buildings have clay walls, 4 to 10 floors, with one apartment on each floor. The entrance to each building leads to a small corridor with a door to the ground floor apartment and a stairwell for reaching other floors. The apartments' furniture follows a similar fashion as in the houses, and windows are on the opposite wall to the building entrance.

The generator takes a number of steps in order to generate the city. First, it takes the space received in the perform function and generates a height map, a 2D matrix containing the height of the first valid ground block for all coordinates x, z of the map. It then gets the width and depth of the space, and selects a percentage of the central area to become the city center. The remaining areas are divided into 4 sections to become neighborhoods.

The center and the 4 neighborhoods go through binary or quadtree (chosen randomly each time) space partitioning 100 times and the generated partitions are added to a list. Each partition becomes a building lot, and the ones that have water, lava, etc in their perimeter or do not reach the set minimum size are eliminated as invalid. The list is then ordered according to the steepness of the lots. The steepness is calculated as the sum of differences between the most occurred height (according to the height map), and the height of every other block in the lot. Therefore, a steepness of 0 means a building lot with a flat surface.

The construction starts by pulling a building lot from the list, checking if it does not intersect with any previously pulled lot, and building a house or apartment building on it. This procedure is repeated until reaching a certain minimum number of lots for the center and for the neighborhoods.
To generate a building, the first thing to be done is to check whether the lot terrain is flat. If not, earthworks are carried out to ensure that the perimeter is at the same height level. This is done by finding the most occurred height, and then flattening the entire lot to match that. Grass blocks are used as the base block for flattening.

Once a lot is flattened, generation proceeds at that height. The generation of buildings and houses are mostly hardcoded. For the houses, it is as follows: first, the land is cleared changing trees etc to air blocks. Then a random width and depth between a certain range, and the maximum height of the house are set. From that, floor and walls are generated, an orientation (N/S/E/W) is decided based on the position of the house, always facing the center of the map. The orientation will dictate the location of the entrance door, the entrance to the lot at the edge of it where roads will \"connect\", as well as the position of the windows. The orientation also sets the direction of the pitched roofs. Once the house is completed, the interior is furnished. For apartment buildings, generation happens in a similar way.

Once all the buildings have been placed, the last step is connecting them with roads. To perform this, we consider each lot as a node in a graph, and we create a minimum spanning tree to connect them. Distances between nodes are calculated with Manhattan distance. Once we have the minimum spanning tree, we use A* to actually find the path to generate the road. The heuristic function that gives the cost between the current and the target point is the Manhattan distance. The cost function between each node is 1+n², where n is the difference of height between the current block and the next. We employed this function to try and find a path that is not too steep between two points (e.g. going around a mountain instead of climbing it).

The A* returns a sequence of coordinates 1 block wide where the pavement is to be generated. We complete the road on both sides of this path to make it 3 blocks wide. When doing that, we verify if the neighbouring block is not an invalid block (e.g. water), and if it is on top of air, we fill the blocks below recursively until getting to a valid ground block.
Some of the things the we attempted include employing A* for generating the MSP, which proved to be computationally expensive for a big number of nodes. We also tried using the most occurred block of a building lot as the base block of the lot when flattening (as opposed to defaulting to grass blocks), which created some unexpected and/or visually unappealing results, like houses built on top of sand.
Contact: moc.liamg|kcuahodraude#moc.liamg|kcuahodraude
GitHub repository: https://github.com/ehauckdo/UrbanSettlementGenerator

Julos14

Team members:
Daniel Lundin
Lasse Johan Lundin
Jungne Losang

The main filter file is SettlementGenerator.py. When selecting an area in MCEdit, the Y-axis is not important, only the X- and Z-axis of the selection is used. During our tests the runtime has been about 1 minute for a 256x256 area, except for when there is a jungle biome, since it cuts down trees very aggressively.

This settlement algorithm has been made by three software engineering students at the University of Southern Denmark. The algorithm is being made as a bachelor’s project and is still a work in progress.

The algorithm starts off with an initial analysis of the terrain. The results of the analysis is saved to a Surface class, that contains data to be used for the other steps.
First the height is calculated at each point in the selected area. Each point in the selected area is then given a steepness value. This value is simply the height difference between the highest and lowest point among the point and its four neighbor points. Biome data is also saved for each point, to be used later, when choosing materials for construction. Water placement is also saved for each point, to be used for the next step.

Sections are created using the steepness map. I.e. sections are connected by points that has a steepness value of 0 or 1 and is not a water point. So sections are basically separated by hills and rivers. To decide what is the section middle is not obvious. We have chosen to find the middle by converging inwards from the edge, layer by layer. The last layer contains the points that are the furthest away from the edge. One of those points becomes the section middle point.

After the section mids have been found, a road network is created in each section by choosing points in that section semi randomly as nodes and then connecting them using Kruskal’s algorithm, creating a minimum spanning tree for the specific section. After each section have their own spanning tree, all section are then connected using Kruskal’s algorithm again to generate a minimum spanning tree connecting all the section. The nodes are then connected with roads using the A* algorithm. The A* algorithm takes the difficulty of crossing steep terrain and water into account when calculating the cost of placing the road. Roads across water are built as bridges and very long roads across water are instead built as docks with a few boats.
When the roads have been built, suitable build sites for houses and farms are found by expanding rectangles with a small height difference tolerance along the roads. Build sites for houses are prioritized and are reserved before finding build sites for farms. Structures are built using materials that are defined by the biome they are built in.
The final step of our algorithm is to place some towers. The towers are placed in small sections that have an average height above the average height of the whole area. The towers also have a minimum required distance between other towers

Filip Skwarski

Given a heightmap (as well as previously placed structures and roads), the generator attempts to find the best spot for adding new structures from a list of features to be generated (temple, town square, house, etc.). This involves scoring a large number of possible placements according to local criteria. The criteria for buildings are elevation (how flat is the terrain?), accessibility (can it be easily reached with a road?), layout (does it fit in with nearby buildings?) and distance (how far away is it from other buildings?). Layout is expressed by having every building come with 'suggestions' of other buildings, for example, a town square 'suggesting' adding houses around it (matching these suggestions means higher layout score). Then the candidates are sorted and the winning placement is picked according to a simple decision tree to generate the 'optimal' town (elevation is always more important than accessibility, accessibility is always more important than layout, layout is always more important than distance).

Whenever a building is generated, the script also adds roads between the new building and existing buildings. Roads are picked using the A* algorithm, but there are some restrictions when actually generating them to make the road network more coherent. Depending on terrain, certain points on the grid are marked as impassable, so roads won't always be generated. Bridges are generated in the same way as buildings, except over water. This allows them to be more interesting, like a bridge connecting two cliffs at an arbitrary altitude over a river.

Before generation starts, the entire heightmap is modified to expand flat space and remove obstacles so that roads have an easier time crossing elevation levels. Buildings and road generation uses this modified heightmap for reference. At the end, the modified map and the original map are combined (the terrain near settlement is from the modified map, the wilderness is from the original map, and the space in between is a gradient between the two).

Results

Entry Author Twitter Adaptability Functionality Narrative Aesthetic Overall Score Files
1 Adrian @TheWorldFoundry 2.82 3.36 3.91 3.91 3.50 code
2 ArtCodeOutdoors n/a 5.09 4.45 4.73 5.73 4.95 code
3 Berlier @fzy81 4.36 4.18 4.27 5.55 4.70 code
4 ehauckdo @ehauckdo 3.09 4.27 3.73 4.45 3.95 code
5 Julos14 n/a 5.45 5.00 5.00 5.91 5.39 code
6 Filip Skwarski n/a 5.82 5.18 4.91 5.73 5.50 code
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License