“There are no blank spots on the map anymore, anywhere on earth. If you want a blank spot on the map, you got to leave the map behind.”
― Jon Krakauer
Introduction
So in this blog post, I am running through the creation method for map creation. The steps of which are below and the main part for Noise generation is covered here Starting With Procedural Generation | A Logic Called Joe (webador.co.uk). With the explanation of Pseudo-Random number generators' basic idea, Pseudo-Random Numbers Oversimplified | A Logic Called Joe (webador.co.uk).
1 -Generates a map of noise using a pseudo-random number generator that I wrote myself. This is generated from seed, so I get the same map results if I set the same seed. The random number in this place is roughly equivalent to land level.
2 -Generates several land centers based on the highest values within the noise.
3 -Uses Lloyd's relaxation to shift the centers around so there is no clumping up.
4 -Create tectonic plates by splitting the map between the highest land points into sections.
5 -Adds seas to the side of the map and along the meeting points of the tectonic plates to create the seas in-between the continents.
6 -Groups the map into cells and builds a matrix of how the locations connect.
7- Apply erosion so tiles with less height and adjacent to a sea tile also become a sea tile and then use recursion.
8 -Take the top 20% of height generated from the noise and designate them as mountains
9 -use the matrix generated above and the sea list in step 5 and run an A-star algorithm to work out the fastest route from the mountains to a sea tile and therefore creates where rivers form.
10 - Use distance from the poles and the distance from rivers to estimate temperature and moisture and designate what type of biome it should be. The biomes are SNOW (less than 25% temperature and 50% wet), Mountains (Top 20% of height), Tundra (Cold and dry), Grasslands most places not at an extreme, If extreme hot and wet becomes a rainforest dark green and if hot and dry becomes a desert.
11 - Generate a randomized language weighting the consonants so that some are more common, assign finals, and sibilants, choose a randomized syllable style and generate 8 monoheme's to form the basis of language. Generate consistent rules for handling silent vowels which happen when a letter appears twice in a row. Random languages are weighted so some use short words others very long words
12 - Assign random names using rules so each cell gets a random name.
13 - Display! See below pictures.
Gallery
Oceans are blue, grasslands light green, forests or rainforests dark green, deserts are sandy coloured, tundra is brown, and frozen poles are white. The names of places are randomly generated and while they are currently randomly placed all locations get assigned a name. The mountains are grey.
Mountains are generated as the top 20% of tallest locations on the map. The height of location is generated by the random numbers so bigger = taller. This consistency of using random numbers to determine where would flood is used later. This is a good lesson in using random numbers but be consistent with their use throughout the whole design.
Biomes are assigned based on a rough approximation of temperature based on how close a location is to the equator and the distance from a river that flows from the mountains to the sea.
Seas are generated as being along the edges or along with tectonic plate points. An erosion function will cause some low-lying land to flood which creates some additional islands and makes the coastal areas look normal and jagged.
The below is a single mega continent. You can see with the mega continent that the temperature banding has a big effect and I think there is a task to create some more biomes or introduce some randomity as I like the dark green forests and grasslands being the predominant colours but I could do with introducing something to just break it up for large landmasses.
Maybe some hills for grasslands and swamps for rainforests or some more work on the river pathfinding as I don't think it treats mountains as blocked.
I have only 2 values hot/cold and wet/dry. I could create more biomes.
Maybe introduce another metric or variable that changes the biome further. Lots of possibilities.
I think for the time being I will generate multiple continents. I guess though that really I cannot think of millions of biome types.
How was made.
Generating Noise
So I am going to produce a lot of random numbers for figuring out the canters for the Voronoi cells (representing city and region centres). You could just use a random number generator such as the standard ones found in C++ or Python. I instead made my own and I found two ways one of which was just to use a sequential random number generator that took a seed and could also use the X and Y to determine the outcome.
I used the X and Y process by applying a mathematical function to create a pseudo-random number partially derived from the grid coordinates as well as the more normal pseudo-random number generator.
Though the principle here is you will need lots of random numbers to randomly generate the map and you will probably want to understand how to seed random number generators and create a matrix of random numbers.
So first thing first get used to producing lots of random numbers.
Placing Cities
The reason you will need all these random numbers is for deciding what points will be the centre of the cells we will use. This will create several Voronoi Cells an example of which you can see below. The Wikipedia page is here Voronoi diagram - Wikipedia. The principle is much simpler you choose a set of points at the level of the per-pixel cycle around the centres and add any unclaimed points to the Voronoi cell.
So if one cell is at a map point 4,4 and another is at 8,8 both will expand to fill the space around them until somewhere along the intersection of 6,6 they will meet each other and then expand sideways. This is useful for producing all sorts of natural-looking systems as the finished product looks like cells in a living organism given that their starting position is randomly placed and they expand to fill the area.
Though in placing these locations we do not want to generate clumps of cities too close together. Therefore we will apply some Lloyds relaxation which for each of the randomly selected centres we will calculate the square of the distance compared to every other location for if we moved up, down, left or right. We will then pick and move the cell in the direction that maximizes this sum. This will result in the Voronoi cells moving to locations that maximize the distance amongst them and will reduce the clumping.
This is what a Voronoi diagram looks like. Each location is assigned a colour and a number on the graph. 20 steps with the Lloyd Relaxation algorithm have been applied to reduce clumping.
The below is without the Lloyd relaxation affect being added. A bit more chaotic use the white bit for reference. You can see why I am not a fan of Lloyds relaxation technique and sort of feel can ignore it. That being said I have seen maps where I thought ewww that needs to relax a bit... it is obvious when there is a big clump of forests in the wrong place that it is artificially produced.
This is how I wrote my Lloyd Relaxation function, it takes a list of points in value graph, is told map boundaries in max_x and max_y and the number of times that it will run. At each step it will shift each cell one step. This could have been better written as it could be written to stop when nothing needs to move any further but the reality is this would take a long time as the calculations for each new move is a square of the number of locations on the map. Therefore it can take some time to run if you want to produce say 1000+ cells then the Lloyd Relaxation technique can eat up some time.
There are other things in this process that are similarly time consuming but out of them I think the Lloyd relaxation technique feels the most trivial and one of the most costly.
Tectonic Plate Shifts
I wanted to create seas along the top bottom and sides, I could have entirely split the map along tectonic lines which will describe below though I also wanted ocean along the edges. This is easy to do I just had a list called seas and where a Voronoi cell claims a location at the edge of a map it is added to the list seas.
Several locations are decided to be centers of tectonic plates these places are the tallest locations already assigned as mountains. The Voronoi cells are then assigned to the there closest tectonic plate. A matrix (described how created below) can then be used which tells me what cells border each other. Where two cells border each other and those cells belong to different tectonic plates then they are assumed to flood under earthquakes and tectonic plate movement.
I haven't tried this with lots of continents yet I think this would shatter the map into lots of islands. Though presently it is good enough to produce maps with a few large continents of varying size a few islands with
Finally, any seas will flood any location below it creating a sea-level process. This utilizes the random numbers generated in the noise at the beginning and where a sea decided by the above process borders a location with a lower random number then that cell will flood. Again it is all about using your random numbers consistently through the design.
Graphs Are Our Friends
You will notice the above requires a graph of how the cells border each other to work all this out...
When generating the Voronoi cells it is trivial when check if a location on the map is free to claim for the new cell and if not to then create a matrix of locations that the location borders on. To do this create a list of lists so each cell has its list and when it meets a new border is formed and the locations are joined up.
You will notice that in my process the Voronoi cells are numbered I have followed a simple convention that in all the places that data is stored the location corresponds to the number.
The whole set of Voronoi cells can be turned into a graph/map and then how the locations meet each other can be the edges and the location can be the nodes. It then becomes easy to search along the edges to determine things like pathing and other map-related things.
I then cycle through each mountain location and use the A star pathing algorithm the function which is shown below and which works out the quickest path from the mountain to the sea. The A-star algorithm and pathfinding in games could have their blog post. Though the principle is simple cycle through all adjacent locations measure the distance to a list of target destinations. Pick the option that reduces the distance to your destination the most and this is the bit that is important add any currently visited locations to a list and don't visit them again, having chosen the new location to visit use recursion to run the code again but now considering the new location.
Recursion is by the way the practice of a function rerunning itself often with new pieces of information. A practice usually using graphs as when you have accessed one point on a graph you might now look at new locations available from that node. Therefore recursion is a useful trick and the easiest way to think about graph related algorithms as a decision repeated at each point in the graph.
A bit of a metaphysical life lesson but this also applies in the A-star algorithm If you don't remember where you have been you can get stuck cycling between locations, if you don't measure the distance to where you're going you cannot choose your next step, with both it is mathematically proven if there is a way you will get there; without one or another you will get lost... good luck on your Journey but perhaps the below code will clarify things.
But the result is a map of locations that act as signposts and the A star algorithm can navigate from any point to any other point.
CODE BELOW:
The Water Cycle
Using the above A Star Algorithm I get a list of places that are on the paths between mountains and seas. These places are now considered rivers. I can then assign each location a temperature as the distance a cell is from the poles based on the map's Y-axis. I can also estimate how wet a location is from its distance to a river network.
I turn this into a % of the highest value. Each of the cells becomes icy polar glaciers if wet and cold, rocky muddy tundra if dry and cold, forest or rainforest if warm or temperate and wet, and desert if dry and hot.
Thereafter using the Voronoi cells I can tell per pixel what colour it should be from the biomes decided throughout this fully pseudo-random process. Though the edges look natural like how forest and rivers don't follow straight lines the Voronoi cells create jagged edges and border regions.
I could and maybe should spend some time doing some extras I could try and path the rivers on the map. I could also spend some time getting the colours just right (I especially feel the Tundra colour is still a bit off).
I am currently trialling this as the map generation process for a fantasy game idea and have a background economic simulation already built where resources flow and get traded. The bit that is clever here is that I have already produced the pathing system and matrix that will be used in troop movement and things moving around the map.
I plan to go through the Language generation process separately as that is a different and lengthy process. Though I am hoping to expand the language generator to represent fantasy cultures and their history with the aim that I can then randomly produce non-Tolkeinesque fantasy worlds.
What are your thoughts?
Closing Thoughts
I think that should be a general introduction for most people on how to procedurally generate a map. I am sure you can add more biomes or more ideas. Hope you have fun.
Add comment
Comments