Sunday, July 3, 2016

Starting Culture Generation

This post is going to be a short one, but it is also exciting. I have finished the bulk of the initial map generating and have gotten my map to render in 3D! Thank you Three js and WebGL. I can use the optimized triangle rendering of WebGL to also create smoother terrain maps through vertex shading. So I now have a rendered 3D model of my map. This let me see many things that I could not see in the 2D view. It makes terrain veriations immediately visible which is great for mountains, but it is not so great for lakes. Seeing this allowed me to fix that problem.

3D Rendered Map
I also have the start of town generation finished. To do this I considered what favorable living conditions would be for starting civilizations. Firstly, you want to live near water. This is the obvious one. Secondly you want to be on a relatively even terrain so you have space for farms. This would mean low elevation. Thirdly I thought that it would be more beneficial to be at a moderate temperature. Now I currently give all three parameters equal weight when considering where to place the towns. So I pick random locations for towns (many of them land in the ocean so this number needs to be larger than you think) and if they are land tiles, roll against the living conditions to see if a town springs up. Giving this randomness helps to clump cities in more favorable conditions but this still allows towns to pop to the top of mountains trying to live off of tree bark and rocks. This makes for a more interesting map and for me I immediately try to put a story to those towns trying to live in the harsher conditions. That's free back story right there.

So we start with the elevation, moisture and temperature maps and average them together as mentioned above to give up how favorable the living conditions are.
Living Conditions
Then going a step further, we do our roll for generating towns (this was of 200 points to generate 11 towns just to give an idea of how many towns didn't make it, especially because of the many that drowned).

Living Conditions with Towns
This is an exciting first step, because now I cam move on to create a history for the towns through the process of expanding borders, which could be a history of conquests and battles, ect. This project is giving much better and quicker results than I anticipated, I just hope that the progress can continue as fast as it currently 

Thursday, June 30, 2016

Breathing Life into the Map

In my last post I went over how I created tectonic plates in the map and used them to create geological provinces. With this basis we can move onto adding more life and character into the map. In this post I will go over adding elevation, rivers, moisture, and temperature. With all this new information we can then determine what type of biome is on each tile. Elevation, rivers, and biomes are the three big pieces of information that give character to a map and environment. These features help to break apart the map into more logical provinces. Often biomes, rives, and mountain ranges provide safe places or barriers from other peoples and can create divides for different peoples and cultures. However I am getting ahead of my self, political provinces are something that will hopefully be implemented further on. First I must disclose that many of the concepts here are taken from Amit's Island Generator Tutorial, and I am just adding my own twist in some areas to fit my own needs. I will go over the parts that I added in detail but am going to skip over many of the features that are taken from his tutorial. If you are interested in how those portions are done, I highly recommend you take a look if you haven't already.

Geological Provinces - Green: Orogen, Blue:Basin, Pink: Craton
Elevation Map - Black: Low, White: High
To get started we can take a look at elevation. We start with the geological provinces map that we created from the previous post and use it as the basis for generating the elevations. I did make two changes to the geological provinces generation since the last post. I made divergent land boundaries into basins, and I added a bit more noise to the shape of orogen boundaries. This helped to add a little more variety to the map . The goal for the elevations is to have the mountains to have the highest elevations and the basins to have the lowest elevations. As described in Amit's demo, the elevation is determined by the distance from the coast, with a slight twist however. We can use two different step values. A large step value was used for mountains (green tiles) and a medium step value was used for the craton tiles (pink tiles). Another thing to note is that lakes were pre-placed prior to the generation of the geological provinces so we have two options for dealing with this. We could either change the elevation and recalculate the lakes later, or take lake into account for the elevation. I did the latter for several reasons. I thought is was an easier approach because it didn't backtrack to things that we already calculated and that lake features could help to add variety in mountain regions. That being said, lakes were also treated like basins (blue regions), so they did not factor into increasing the elevation. Taking this approach goes along with Amit's implementation of elevations, in that there are no local minima where rivers could get stuck. This is highly beneficial for the next section. In the end, the elevation map looks quite similar to the geological provinces map, which was the goal.

Generic Map With Rivers - Lighter regions indicate elevation
Moisture Map - Green: High, Tan: Low
Now, I didn't do anything fun and cool with river and moisture calculations, so if you are interested in how the following was done check it out. I completely used Amit's implementation. I think it is sufficient for an interesting looking map, but it definitely has its drawbacks. It is very obviously one of those ontogenetic (top down) approaches to map generation. Where he does not follow actual geologic processes and is just interested in a way to achieve rivers. One approach to a more realistic moisture pattern would be to add weather or wind patterns and calculate the moisture from lakes and oceans, and the determine where rivers would flow given that information. Quite frankly every approach I have seen that does this gets nitty and gritty quickly. It might be something to add in the future. But the current approach is good enough to use for now and allows me to move on to more interesting things in much less time. A quick explanation is that random points are picked for the river starting locations, and rivers flow from there until they reach the ocean. From that, the moisture is calculated as the distance from a fresh water source (river or lake). Rivers tend to flow through basin regions and at the base of mountains due to the basins being the lowest elevations. The rivers might be hard to see as these small picture, but if you click on them you can enlarge them to see the rivers better.

Next we move onto temperature. Looking at an average temperature map you can see what you would expect. It is hot at the equator and cold at the poles. Now this is not hard to replicate. With a little math we can get there. With each point on the map we have an x and y position (which we will normalize to a range from 0 - 1 for better looking math). If we want a curve with a warm patch in the middle we can just use the function,
\(T(x, y) = 1 - |cos(2π*y)|\)
Temperature Map - Orange: High, Blue: Low
We want the cosine like function in the y direction for one period.First we take the absolute value to give us a nice hard streak in the middle, but we also need to get the inverse of this value to have 1 (warm) in the middle and 0 (cold) on the outside. Now this is great if we are creating the whole world, but we just want portion of the map where our island / continent lies. To do this we must have the ability to tune our equation for a more random temperature outcome. To do this we can add two parameters, a and b, which can adjust the period (transformation), and the starting position (translation). This leaves us with the following,
\(T(x, y) = 1 - |cos(2π * y * a + b)|\)
This gives us a nice looking band of warm/cool weather somewhere on the map. One thing to note is that I skewed the b value towards the center because we took the absolute value of the cosine function. This gives a better distribution of warm and cold temperature zones. This is a good start for general temperatures, however the results are rather bland and predictable results. Nature does not behave so perfectly, it has twists and turns depending on many local factors and weather patterns. Now we can use procedural texture generation techniques here to help fudge those weather patterns for us. By adding turbulence to our function we can add more organic looking features to our temperature map. Turbulence is just slight alterations in the temperature function according to another noise function. This allows the alterations to look like they are behaving according to a pattern. Therefore it adds coherent randomness to our temperature map. Adding in our turbulence (or noise) function we get the resulting equation,
\(T(x, y) = 1 - |cos( 2π * y * a + b + turbulence(x, y) )|\)
One last touch we can add for temperature is that at higher elevations, we want a colder temperature. We can just have a bias so that at higher elevations, temperature has less effect. Then we are left with a much more organic looking temperature map. Now I did add one bit more to the temperature function. I added an x period. I made it random and extremely small, just to add a bit more randomness to the function.

Modified Whittaker Diagram
Biome Map: Biome Labels from Whittaker Diagram
Now we have all the information to fully breath life into our map. We have our elevation, temperature, and moisture all set up. From here we can start to create biomes on the map. We can do this using Whittaker's diagram. Whittager's diagram is a relationship of the moisture and temperatures on biomes in the real world. On our map we create temperatures and moistures from 0 to 1. When compared to Whittaker's diagram which seems to be missing half of those measurements (because those conditions can't exist because of how much moisture air can carry at different temperatures). In typical procedural generation fashion we fudge the numbers. We use Whittaker's diagram as a guide for where biomes should appear, and then go from there to create a diagram that fits our needs. Using the new table, we can go through our map and place biomes. I also have a couple of special cases that do not adhere to Whittaker's diagram. Ocean, coast, and lake tiles are all exempt. Ocean is ocean, coast is a beach, and like tiles can be one of three things. If a lake is extremely hot, it is a marsh, if it is extremely cold, it is ice, otherwise it is just an ordinary lake. After adding biomes, the map is starting to look like something that can actually be inhabited.

From here my next step is to render the map in 3D. Right now the map looks flat as all hell, because you can either look at a map that shows the elevations and basic information, or the biome map. The rendered map will be a good first step to creating a map that conveys a large amount of information, and is legible. I also want to look into better ways to generate land. Currently, the perlin island generator is not horrible, but I want more variety out of islands. My continent generation function is simple and abysmal, and I need to find a better way of generating more than one island, and not have them just be small clusters of islands.

Monday, June 20, 2016

Plate Tectonics

I have made progress on my project. I used the same basic scaffolding that I had from my last post to get my project started. The first thing I tackled was the plate tectonics. My map shape is made by a simple thresholded perlin noise. The map shape is bland, but that is a problem for a later date. I am interested on how to place the large scale geographic features, such as mountains, basins, and to some extent, lakes. The biggest feature I was trying to come up with was the placement of the mountains. On earth mountains ranges are generally placed near the coast, and sometimes are more inland. This is due to plate tectonics, and I wanted to simulate this process to get the same effect. To help explain how I did this, first I am going to go over the basic concepts of plate tectonics that I used to get there.

First off there are two types of plates. There are oceanic plates and continental plates. The oceanic plates are more dense that the continental plates and sink bellow the continental plates. All the plates on earth are moving at some velocity with relation to each other, causing them to move to and away from other plates. This creates three different types of boundaries, convergent  (colliding), divergent (spreading apart), and transform (sliding plates) boundaries.

Divergent boundaries happen in the ocean (except for through Iceland) and are responsible for the oceanic ridges. Transform boundaries usually accompany divergent boundaries and often result in fractures cretingmany smaller divergent boundaries in a zig-zag pattern. Convergent boundaries are the most interesting and come in three flavors. Ocean-ocean boundaries, ocean-continental, and continental-continental boundaries. Each of these boundaries creates a buckling in the crust and is the main component of orogeny, which is the process of creating mountain regions. Most of the convergent boundaries are ocean-continental which is why most mountains are on the coast. The ocean-ocean boundaries create  pockets of volcanic activity resulting in island chains. Then there are continental-continental boundaries which is responsible for creating the larges mountain ranges, such as the Himalayas because neither continental plate wants to sink bellow the other. I am taking a naive approach to plate tectonics in this generator and many of the topics are greatly simplified and fudged. If you are interested there are links on how it actually works here and on wikipedia.

So first, I started with the basic map generated with the noise function and then added the plates to the map. The plates were created with a relaxed voronoi diagram. The each plate is checked if it is an oceanic or continental plate depending on what kind of tile makes up the majority of the plate. The plate is then given a direction. From looking at maps of the movements of the plates, I saw that plates tend to move away from oceanic plates and try to move towards continental plates. This helps to orient oceanic plates to create convergent boundaries near the continents borders. Then you just need to calculate the boundary type based on the direction of the neighboring plates. This is shown bellow. The plate types are slightly colored green and blue respectively. The border types are calculated on the ratio from convergent to divergent. So the red lines are convergent boundaries and the divergent boundaries are the blue lines. Transform boundaries are green, and any boundary that is somewhat green is also partly a transform boundary.

Plate Boundaries - Convergent: Red, Divergent: Blue, Transform: Green
Excellent, now that we have the plate boundaries we can figure out how to use them. The location of these plate boundaries is responsible for where the geologic provinces are. There are several types of geological provinces. The craton (which is a combination of the shield and platform provences) is a stable protions of the continent. The orogen is the location where orogenensis, or mountain building happens. Basins are flattened and depressed areas which are formed by erosion. Then there are the two oceanic provinces, the oceanic crust and the extended crust (continental shelf).

I currently only use the convergent boundaries for calculating provinces and I have not yet implemented the continental shelf, because I did not think it was important yet. All tiles that are ocean tiles are assigned to be oceanic crust and all land tiles are part of the craton unless otherwise specified. I wanted the mountains to be at the fault lines so I just said that a tile was a part of the orogen if it was a certain distance from a convergent fault. If you look at a map of the different provinces like this one, you can see that basins are generally inland and on the opposite side of the orogens. So that's what I did. A tile was a basin if it was a certain distance (slightly larger than the orogens) away from a convergent boundary and is not a coastal tile.

Blie: Ocean Crust, Pink: Craton, Green: Orogen, Merky Green-Blue: Basin
And when we take away the plate borders we are left with the image at the bottom. I was happy with how it turned out so far. I think there is still some number tweaking that needs to be done. but the mountains are making long chains at the borders, and basins are where they should be. The next step is to add elevations to the land.

Thursday, June 16, 2016

Procedural Island Generator

So I have been following Amit Patel's tutorial on procedural generation on procedural island generation. Amit's tutorial seems to be the best described process for procedural generation I have come across so far. He also has an incredible wealth of knowledge linked within his posts about helpful procedural generation techniques in many different areas. For his island generation, Amit uses a completely ontogenetic (top down) approach to island generation, so this approach does not work for many of the 'infinite' terrain generators some people are currently trying to make. A top down approach means that he starts with his goal in mind and works towards his goal. His goal was to create an island that has good coasts, rivers, and a constant slope. Therefore, his procedure for map generation does not follow natural geological terrain evolution. This process of generation by simulation is called teleological generation (bottom up), where you start with processes that simulate Earth's processes, and tweak parameters and higher level effects to come out with your end goal.

Copying Amit's process has taught me a lot about the basics and many tools of procedural generation that I can use to create my own terrain generation process. For my next project I want to create a map that covers a larger area than the one Amit created. I want it to contains several continents or large islands but not generate terrain on a global scale. I want the map to be large but still a manageable size. I am not looking to make the next Civilization or Spore or No Man's Sky. Given the new tool I have learned. I think I at least have a good jumping off point to begin this project.

There are many things which I wish to improve upon for from the old project. For starters, the whole map is represented as a polygonal graph in the form of a PAN graph, and I want to smooth out the moisture and elevation map to have continuous transition. Currently it just has large steps displayed by the average elevation at each polygon. I know this can be done using barycentric coordinates to come up interpolated elevation within each polygon.

I also wish to implement biomes. Amit does this in his tutorial, however in his game he does not implement a temperature system because his game does not need it. Biome generation is based off of the Whittaker diagrams which show the relationship of biomes based off of temperature and moisture. Amit overcame this by substituted elevation for temperature and made a couple of other modifications to fit his needs. A temperature system should not be difficult to implement to help with creating biomes. Temperature could also help to give context to the world, such as how close to the equator is this map portion and could possibly help in creating a culture in that area.

Amit's implementation of elevation on his island was very simple. It was calculated based on the distance from ocean, scaled after the fact to create a smooth gradient to the middle of the mountain. This works well for his islands and the game he was designing. For his game, the elevation of the region indicated the difficulty of monsters. I wish to take a more teleological approach and simulate plate tectonics to generate the elevations . This will help to create a better distribution of elevations in more reasonable locations. Miguel Cepero of Voxel Farm made a good simulation of plate tectonics using mesh triangulations and the midpoint displacement algorithm to simulate this effect for his continent. I have a slightly different approach in mind, but his example is a good starting point for tackling this problem.

Another thing, More Noise! Amit only uses noise in his project for his random point generation, island shape, and in his renderings of his map. However I really like his approach to adding noise to his map to try to get away from the rigid polygon structure in his map. I just have many more places where I feel that noise can be added to create a more interesting terrain patterns. There is a lifetime that could be explored understanding the possibilities of using noise for procedural generation. I hope to explain some of the possibilities for noise in terrain generation here later.

I want to better model the way water and erosion help to create our landscape. This could be done using hydrology or the rain drop algorithm to create that effect. Using watersheds and drainage basins are extremely important to creating a believable landscape. This helps to carve out habitable areas and is an important part of city generation. All of the early civilizations were created by lakes and rivers, and thus most of our largest cities are in these locations.

A long way down the road I want to work on making the maps that look like they were more hand crafted. For example there are a lot of wonderful hand made maps at the Cartographer's Guild and there are a lot of techniques like relief shading which have been used by cartographer's to make a interesting map that can trick us into seeing the terrain better on a flat surface. Relief shading puts a lot of emphasis on water runoff regions and provides simple lighting which go a long way to creating the illusion of mountains to a map.

Even further down the road I hope to put in some sort of name / culture / history generation for the map as well. Miguel Cepero did a simple example of this using voronoi diagrams and a heightmap.
Cory Lee has also created a political map generator. This culture and and history generation can also be seen in roguelikes such as Dwarf Fortress and Ultima Ratio Regum to name the two most influential for me.

With procedural generation, anything is possible. I look forward to exploring these possibilities and sharing the things that I have learned.

The current results from following Amit's Island generation Tutorial:

Figure 1: Colored Island showing
Sea, Lakes, Rivers, Beaches and Elevation information

Figure 2: Moisture Map with Green being high moisture

Figure 3: Elevation map with white as high elevation