Procedural World Map Generation (Revised #1)
Welcome back to another blog post for the development of Littlecube Valley. This post will be the first part for the new procedural world map generation series.
The world map generation solution is now able to bring out some of the root level details such as continent and coastlines, oceans and seawater, river networks and lakes, meandering rivers, biome colours and jagged transitions, river deltas and estuaries.
Firstly, we have upgraded the voronoi solution to use precomputed Centroidal Voronoi Tessellation, so that each voronoi cell has its centroid location close to its center of mass. The image below summaries our objective.
We have to do this for each size of the internal map, so a 256x256 map will require about 3K voronoi cells. To do this, we use a numerical integration solution to recompute the centroids of the voronoi cells by simple averages of their neighbouring centroid locations . Eventually, the solution becomes optimal after a number of iterations, leaving the borders unclamped. We also have to stretch the voronoi cells at the borders and clamp their vertices to the borders of the map.
Additionally, we can examine how to minimize the average squared Euclidean distance between each voronoi vertex from Lloyd's algorithm, in order to improve the automation of the voronoi generation solution. But since this is just pre-computation step, we can do it with the above solution for now.
The initial creation of the world shape is now to be determined by a simple simulation of tectonic plates and accretion. We start off with a small number of tectonic plates and assign them with a numeric identifier for each plate. After that, we use a series of iterations for propagating the accretion values across the voronoi cells representing their tectonic plates. We start from the borders of each tectonic plate and only the tectonic plate with a higher numeric identifier will accumulate accretion values.
After that, we form the continental crust by separating them using K-means clustering. We erode the borders of the continents to have a sea between them and also simulated long-term erosion and deposition at certain parts of the continent's coastline. We have also added islands of various sizes, which are randomly located away from the continents. There is a distance comparison to ensure that the islands do not clash with each other.
After that, we establish the seawater regions and determine the shallow and deep regions. Shallow seawater regions are represented by the light-blue regions, around islands and certain parts of the continents.
Next, we determine the voronoi regions for representing mountains. We use the accretion values for double thresholding to determine the type of mountain the voronoi cells represent, such as dome, plateau, fault-block, folded mountains. This simulates the regions where tectonic plate movements would accumulate the most land mass above the sea level. There is also a volcanic mountain at the south-eastern region of the map.
After that, we repeat the process for determining the badlands region, so that we have canyons, gorges, buttes, hoodoos, mesas and plateaus. They are represented by the light-brown, beige and yellow regions. Most of the badlands regions will lie next to the mountains, as the accretion values are below the mountains but above the lowlands.
Next, we have the lowlands, represented by the green, light-green and yellow regions.
We then mark out the remaining surface regions as coastal land, represented by the light-brown regions.
Next, we prepare the lakes, represented by the light-blue regions within the continent regions. Lakes have to be land-locked.
Next, we compute the latitude that is range-bound with respect to the top and bottom of the map and assign them to each voronoi cell. For this world map, we have set the latitude to be within the northern temperate region (+30N to +60N).
After that, we determine the drainage. All regions dominated by seawater and lakes will have the poorest drainage, while regions with more landmass such as mountains and badlands tend to have rapid or excessive drainage, represented by the dark-blue regions. For voronoi cells with neighbouring water-bodies, their drainage will be weakened.
Next, we have an updated solution for establishing the wind forces. Previously, we were using a numerical solution, the present solution now uses simple state changes, which is more stable. Wind forces are propagated from the borders of the map. The wind direction is similar to global trade winds in which they are also latitude dependent.
The landmass is resisting the flow of the wind, so the mountainous regions will occlude and reduce the strength of the wind force as it propagates around the map. The islands and coastal regions have little resistance, so they tend to have stronger wind force.
After that, we determine the temperature, which is dependent on the latitude and altitude of the landmass. The lowlands near the equatorial region tend to be warm but as the latitude increases north, the temperature is cooler. Mountainous regions are also cooler compared to low lying regions.
Next, we determine the moisture using the temperature and wind force conditions. The stronger the wind force, the higher the moisture content. Moisture also tends to be drier for the extreme ends of the temperature range. Mountainous and badlands regions tend have dry moisture as the wind force strength is drastically reduced.
Lastly, we determine the rainfall based on the moisture and the terrain type. Rainfall is heavy in seawater regions if the moisture is severely wet, while mountainous regions get light rain and low lying regions tend to have heavy rainfall. If the moisture is moderately dry, then there will be little to no rainfall for those regions.
Next, we prepare the voronoi clusters for coastlands, lakes and mountains using K-means clustering solution. These are to be used for the river generation system for determining the origin and possible destination of major rivers. We also use cluster pairing such as between coastlands and lakes or between lakes and mountains.
The river generation system has also been simplified and updated for better robustness. It still uses a modified A*search solution and does its pathfinding across each voronoi cell, until it reaches the waterfall or gets combined with another river or reaches the sea. Rivers whose paths are too short are abandoned.
The river generation system also keeps track of the flow direction and elevation. We will need to verify their correctness in subsequent development iterations.
Next, we prepare the biomes for land, wetland and water. We also finalise the salinities for the lakes. Then we shade the biomes into the world map using a polygon scan-line algorithm. We also shade rivers into a separate world map using a Bresenham line drawing algorithm, which results in the image above.
Here is the coloured result for the land biomes.
We can now begin to prepare the voxels for the world map. We first prepare a full list of 4x4 voxel tiles that represent the various combinations on how rivers could flow within the small space. The image below shows a few samples on how rivers may meander within a small 4x4 tile. The light-blue pixels represent the river water while the green and brown pixels represents the surface land. Sometimes rivers may have more than two points connecting the border.
We use a machine learning solution that is based on decision trees to determine how the meandering river is meant to be formed. The decision tree helps to classify the river tile based on the state of its connecting neighbours, so this solution requires a series of iterative steps in order to fill up the entire river line. Furthermore, each 4x4 river tile serves to represent one river pixel on the world map.
The image below shows what the rivers look like when their lines are fully connected with river tiles. The solution ensures that there is a valid connection to the sea or lake. Sometimes there will be a few pieces of land that is surrounded by lake water or the rivers may combine and form a braided river. Lakes may also have multiple channels for river inflows and outflows.
The image above also shows that there is a colour shift for the seawater from light-blue to darker blue. The same situation also happens for the lake.
We also prepare a full list of 4x4 voxel tiles that represent the various combinations on how shorelines could be mixed with water and how the shoreline for lakes and coastal regions can have jaggedness. The image below shows some samples on how the shoreline and water can be mixed.
For voxel tiles where all its 4x4 neighbours are also water, we use another list that does not have any surface land. The image below shows some samples of voxel tiles that are used to fill the lakes and shallow regions of seawater.
The salinity of the lakes are determined by temperature, rainfall and the connectivity to rivers. Warm temperatures simulate more evaporation and if there is only light rainfall, the water volume of the lake may diminish, resulting in a higher concentration of salt. Lower temperatures and more rainfall helps to lower the salinity of the lake water. The connectivity of the lakes to coastlands or mountains is only used to determine the initial salinity of the lake water.
The image below shows a brackish-water lake (light-brown) and two fresh-water ones near it. Some of the rivers that seemed to end up nowhere are actually waterfalls in the mountains. Once the models for the waterfall mountains are done, they will eventually be added to give a clearer understanding on the source of the water flow.
There are also jagged colours along the borders of the biomes. This is done because voronoi cells can have straight edges which will give a straight line of voxels if no solution to mark out the borders of differing biomes. Thus, we used a list of voxel tiles similar to that used for marking the boundaries between the shoreline and seawater.
The image below shows the seawater between two continent landmasses. It will now be possible to establish civilisations similar to the Phoenician Empire that spans across two continents with a sea in between.
There are also braided river lines breaking up the coastal region into a mix of small and large portions of the landmass. Further below also shows a river line flowing through a region that seems to be arid, possibly a desert region.
The image below shows numerous waterfalls in the mountains have produced river lines that flow across the badlands. Some of the rivers have ended their flow into freshwater lakes. A freshwater lake has been found to be land-locked, which may indicate cooler temperatures and more rainfall.
More waterfalls in the mountain regions can be seen in the below image, producing river lines which some have flowed into the sea. The mountains are coloured green because the biomes have classified them as having forests.
The image below shows a land-locked brackish-water lake and a river delta. Some forested mountains are located near the coastal regions.
Another river delta as shown in the following image below, with a small estuary before reaching the seawater.
The image below shows some of the deepest portions of the ocean, represented by the dark-blue regions. The transition between the different coloured portions of the sea is similar to that of lakes. We first mark out the borders between the water biomes and fill them up with voxel tiles, with the correct transitioning. After that, we fill up the regions that are within each water biome with wave-looking tiles.
The image below shows waterfalls producing river lines that flow into a lake that has no outflow into the sea.
In contrast, the image below shows a river line splitting into a Y-junction and both lines ended at the same lake at different locations. One of the river lines went on to form another Y-junction and reached the coastline.
The image below shows river lines outflowing from one lake and rejoining another lake, before outflowing to the sea.
A large island with forests is shown below. The water colour around all islands are turquoise, representing very shallow regions. No beaches have been marked out and we will presume that they are too small to be seen for now. We will add them in subsequent development iterations that allows for world map zooming-in.
Lastly, a volcanic mountain region (brown) can be seen in the image below.
In conclusion, we have made a drastic overhaul of the procedural world map generation system. The next focus is on add the models representing the various land-forms such as mountains, badlands, hills, waterfalls, forests and wetlands. Eventually, we will be able to add settlements and names for the various locations, similar to medieval fantasy world maps. This will be our 'Generative Art' solution for the NFT-art space.
Thank you for reading!