Map Generator 3.0 - Please Critique!

Development Programming & Scripting Blueprint
1

This thread is an extension of my previous Map Generation threads(see signature). If I do not show something in this thread, then it may be explained in one of the other threads. The generator currently uses 200+ variables and 160+ functions so it would be impossible to cover in fine detail. This will be much more general in nature.

Overview:
The Map Generator procedurally generates hexagon maps using Voronoi diagrams(google it) for use in a Civilization style game, or really any game that can use a hexagonal map. The generator is fairly complex, taking into account tectonics, elevation, temperature bands(latitude), precipitation, river growth, etc, with more complicated climate systems to come(among many other things). There are currently 15 player settings that can change just about everything about the map from hellishly hot to snowball earth, Pangaea to global Oceania, dry bones desert world to endless jungle, flat earth to mountainous tectonic nightmare, etc, etc. Most settings have additional uniformity/diversity settings that let you determine how diverse the terrain is, such as having terrain features that stretch for vast distances, or more broken up by changes in precipitation, elevation, etc.

At 5000 tiles, this is a little bit bigger than your standard Civ Map. Currently, the largest map size is ~20,000 tiles which is similar to Gigantic.

For reference:
Arctic = Snow
Tundra = Snowy grass
Boreal Forest = Snowy Evergreens
Coniferous Rainforest = Evergreens
Deciduous Forest = The average Green trees
Jungle = Bluegreen Palm trees
Marsh = Light Teal plains
Grassland = Green plains
Steppe = Brownish plains
Desert = Sand colored plains
Arid Mountain = Reddish rock mountain
Mountain = Rocky with snowy peak
Arctic Mountain = Mostly snow covered with a little rock showing.
Lake = Deep Blue surrounded by land
Coast = Blue Green surrounding the land
Ocean = Dark Blue
Sea Ice = Light Blue

I will try to outline where the generator is and where it is going. Most systems are being upgraded, so that will be tracked here:
Continents/Oceans V3.0 - Tectonic Simulation using 3 layers of Voronoi diagrams.
Elevation/Topology V2.0 - Random Seed, single Voronoi layer. (V3.0 will involve plate collision and simulated tectonic activity driving mountain creation)
Temperature V1.0 - Based on latitude, each tile belongs to a temperature band. Any changes to this system will depend on how the Precipitation system evolves, but should generally be fairly static.
Precipitation V2.0 - Random Seed, single Voronoi layer. (V3.0 will involve a more complicated weather/climate system)
River/Lakes V1.0 - Rivers flow around the edges of the tiles, flow into and out of lakes, and eventually dump into an ocean. (V2.0 and beyond mostly involves tweaking the flow path and upgrading the start points)
Lowland/Marsh V2.0 - Random Seed, single Voronoi layer. Plains that have poor drainage characteristics and access to water turn into Marshes. (V3.0 depends on the Precipitation upgrades)
Resource Generator V1.0 - Random Seed. Resources currently spawn randomly after being filtered through several player settings. This is turned off while I work on other systems.

Here is the overall generator

I will explain more of each system in subsequent posts devoted to each system.

Right now, I will try to explain how the basics of how the the information is stored and accessed for vector field that drives everything.

Everything about the map is housed by arrays. Each tile in the map has 1 index in an array and every piece of information about that tile has the same index in every array that stores such information. The map arrays are Indexed as such:

As you can see, there are 2 examples of what a neighbor check looks like in both Even and Odd offsets, along with the math to to find their index. Since the map uses world wrap, the tiles on the other side of the map are shown for easy reference. Top array is a 10x20 map, and the bottom is 20x40. All map sizes scale to values of 10. Doubling the map size quadruples the number of tiles. A size 10 map has 1 tile per temperature band(per hemisphere), with a size 100 map having 10 tiles per temperature band.

One of the first things that I create is the Vector Field, which is indexed to the map size and is used in almost every other system in the generator. Depending on the size of the hexagon the math may turn out differently, but this creates all the vectors for the tiles in my map:

I looked at using Axial coordinates, and do have an Axial coordinate array implemented, but have yet to find a use for them that trumps my offset index methods. If I use axial, then at some point I have to convert back to index anyway. Since I am doing all the math with the offset indexes, then I don’t need to convert. The tricky part is ensuring you properly account for the offset, but once you have that down it works just fine. Both methods require checking for edges and world wrap, and that can be a serious pain in the butt, but once you create functions to handle those problems things become much easier.

The core of the generator uses Voronoi diagrams to plant and grow Seeds into landmasses, oceans, deserts, jungles, etc, etc. When a tile is checking to see whether it is land or water, wet or dry, etc, it is going to look at all the nearby Seeds of that type to see which one is the closest. Each tile in the map goes through this process one or more times, for each piece of terrain information that is being determined.

Distance checking without world wrap is pretty easy. Compare the length between the current tile vector, and each seed vector. The closest seed wins. Distance checking with World Wrap is a bit more complicated:

The world wrap is currently implemented by duplicating the main map into 2 shadow maps. The 2 shadow maps simple spawn with an offset on each tile. Each shadow map is also indexed the same way as the main map. If I cut down trees on any of the maps, I just call that index on the other maps and perform the same action. When you scroll east or west, you hit a volume that teleports you to the same position on the other side of the map. This allows you to scroll endlessly in any direction as if you were on a globe.

This wrap method has issues that I intend to fix someday. All meshes are multiplied times 3 and are always rendering. This is noticeable on maps with 10K+ tiles. Additionally, there is a slight motion blur during teleportation, but I am told that can be fixed in the post process.

Ideally, I work out a method where I can stream a single shadow map ahead of you in whatever direction you travel. Or in some cases, I may need to stream 2 of them if you zoom out far enough. There is also the case where a player clicks the minimap to snap to a location across the world which could require a 3rd map to be streamed in if it can’t appear quickly enough. These are problems for another day though. Also need the devs to add a few features to the streaming system/world browser to allow more control from blueprint anyway.

This is how the tiles are rendered and interacted with:

Each visible tile is an InstancedStaticMeshComponent. I add a mesh to the world, add that mesh to an instance variable, and then use that variable to spawn the instances in the world. Instanced rendering is key to stable performance with this many meshes spawned.

Anytime I change an instance, such as cutting down a forest, each other instance in the map is deleted and respawned. This has been seamless even with tens of thousands of instances on the map.

As you can see in the second of those 2 images, I use Enums to drive what tile is spawned at any given location. Each tile has information about sea level, precipitation, temperature, etc etc. Depending on the combination of that information, different tile types will spawn. For instance, a tile that is Land, Plains, Tropical, Wet, and a Lowland will spawn a Jungle over a Marsh. A tile that is Land, Hill, Tundra, Moderate, and Lowland will spawn a Boreal Foreston a Hill. When spawning the instances, it merely goes through a series of switches until it gets to the correct Add Instance node.

You can’t interact with that instance though, so each tile has a set of invisible volumes spawned on top that I hit with line traces to pull that tile’s index and then perform whatever actions I want on it.

As you can see in this picture, the red lines representing my tectonic boundaries are my volumes made visible and colored red. The volumes double as a great visual debugging tool. :slight_smile:

So that is most of the general information. I will use separate posts below to go through how each of the systems generates the information that fills each terrain array.

2 Likes
2

Below I will explain how the Tectonic Plates(outlined in Red) are made and how the Continents/Oceans are Seeded within:

Here is a zoomed in view of the tectonic generator section, as well as Step 1 and 2. Upper right is Step 1, and Lower Right is Step 2.

So first thing that happens is in Step 1 a number of random tiles indexes are chosen as Seeds. Each of these Seeds will grow into the first iteration of a tectonic plate in Step 2. Using the Earth as an example, we would Seed 7-14 times to create a similar tectonic layout.

The Generic Biome Locator that from Step 2 is the core of the Voronoi diagram process:

And the Distance Check that was shown in the first post:

So with step 2 complete, we have some very angular looking polygons for plates. We need plates that look more organic. This is a bit more complicated than steps 1 and 2, but roughly the same process.

The first thing we have to do those is take all the tiles in our plates and group them together as one in Step 3:

The first image is running every tile in the map through the Plate Array Grouper(image 1), until every tile has been added to a plate array. The Plate Array Grouper is going to run neighbor checks on every tile next to the current tile and add all tiles that match the first tile to the Open List. Then, the Open List will continue to iterate through all tiles in that plate until none are left. This all happens in the first loop of the first image. 1 entire plate is added to the Closed List and dumped as a single unit into the Struct Array. Then, when the loop in the first image runs a second time, it will probably find that the tile is already accounted for. It will move on until it finds a tile that belongs to a new plate and organize all of it’s tiles. Repeat until all plates’ tiles have been grouped together in the Struct Array.

Here is the Neighbor Checking function zoomed in on some of the neighbor checks:

The Byte line is the Tectonic Group Array where we categorized each tile as having a plate. We are comparing the Current Index to each of the 6 Neighbor Indexes and if they match, we are dumping them into the Open List so we can then check their neighbors.

Here is the NorthEast Neighbor Check for reference.

As you can see, I am taking into account the Offset, the Wrap, and whether or not it is on the North/South edge of the map which also depends on the Offset. As you can see, if I am at the very top of the map, I can do a NorthEast check if Current Index is Even because the Odd tile will be there, but if it is Odd, then there will not be a tile at NorthEast and I will want to skip that check. The other 5 Neighbor Checks are similar, but North and South are extremely simple because they don’t care about Offset or Wrap, just whether they are on the top or bottom respectively.

So, Step 3 has done all the work of organizing the tiles into the Tectonic Plate Struct Array.

Now we can Seed those plates for a second time in Step 4 and Generate into more Organic shapes in Step 5:

So for each Tectonic Plate, we take it’s length, divide by 30(so 1 Seed per 30 tiles in that plate), and put that many Seeds into a Seed Array. We then stuff that Seed Array into another Struct Array, followed by similar Seed Arrays for every other plate in the map.

Then in Step 5 we do your typical Voronoi generation, except we have an extra loop in the middle. That loop is essentially keeping track of what plate we are on because we need that information to re-group all those tiles into their new plate shape. Like normal, the closest Seed to the Current tile is what we set the current tile to, but in this case we are setting it’s plate information so that is used for the Nearest Group Index which is then fed into the new Tectonic Group Array.

Now on to Step 6, which is quite a lot like Step 3, except a good deal more complicated:

When I was first working this out, I was seeing a weird bug where I had more arrays than I did input plates. I finally figured out that as I grouped the plates back together after generating them the second time, they had cut themselves in half in many cases. This is because of the random nature of the seed distibution, if you have one seed off by itself and another plate grows into its territory you effectively have a new plate.

So, Part 1 accounts for all plates. Part 2 does it again but this time it classifies each new part as a separate plate. You might have started with 8, but now you have 9, 10, etc. You have to account for this because we are going to use the plates for more seeding in the future and if they are cut in half things get out of whack.

Part 2 completes the process of ensuring the number of plates equals the number of arrays created. Additionally, you see the Plate Organizer there at the end:

The Plate Organizer takes all the plates and organizes them by size, from biggest to smallest. This helps us ensure that not all the big plates become oceans while the small plates become continents and vice versa. I will also use that information in other systems that benefit such as Tectonic collision and whatnot.

One more thing we do with the plate information is categorize which tiles are on the boundary between plates. This is important for many reasons, such as using the boundaries as visual markers for the plates, Seeding those boundaries separately from the plate itself, and perhaps generating earthquakes along them during gameplay:

This neighbor check essentially looks at the neighbor tile’s plate info, checks if any of them are different, and if so, marks that tile as a boundary tile.

Finally, with the plates formed into nice organic shapes, we can Seed them into Oceans and Continents:

The Ocean Quantity Setting is a % so we run that against the actual number of plates to determine how many plates will become oceans. We then alternate through the plate array assigning Oceans. If we run through it once and there are still oceans left we go through it again until we run out.

Then, we Seed each plate according to its type; Ocean or Continent. If it is an Ocean, we Seed a large number of Water Seeds into it for the bulk of the ocean, and then a smaller number of Land Seeds to form the islands with similar for the Continents.

There are 2 sets of settings for the Seeds. The Water/Land level settings affect how big the continent is, or how unbroken by large islands the Ocean is. The Uniformity settings affect how many islands form in the ocean and how many lakes/seas form in the continent.

At the end, the Tectonic Boundaries are Seeded with water:

This is what gives the actual continents their definition, and also adds another layer of organic form in addition to the Plates themselves. If you look at a world map with the plates shown, you see that most plate boundaries are under oceans with very few cases of them under land. At some point I will work out a setting for the player to erode or strengthen this boundary. Less of a boundary means more connections between continents, even to the point of merging them together. For an earth-like look I am hoping to do this in a more controlled manner since it is a little brute force to create nice isthmuses like Central America and the Middle East.

Last but not least, here is the Sea Level Generator that grows the continents and oceans into their shapes:

The biggest difference between this generator and the tectonic generators is that I am only checking within 5 tiles of the current tile for Seeds instead of all tiles in the map, which is just an optimization that is especially nice on larger maps. Then those Seeds within 5 tiles are added to the Open List which is run against the current tile.

And that is basically it for the Tectonic Generation of Continents and Oceans. I will be expanding upon this system to cover cases like the Indian Sub-continent plate smashing into the Eurasian plate. This will roll right into the upgrade of the Elevation system.

Let me know if you see any room for improvement or have any questions!

3

Update your signature :slight_smile:

4

This post is reserved for the Elevation Generator.

The current Elevation Generator has a primitive seeding method with the generator looking like the Sea Level Generator.

When I upgrade this system I will update this post with the new Elevation Generator.

5

This post is reserved for the Temperature and Precipitation Generator. Will upgrade to become the combined Climate Generator.

The current Temperature and Precipitation Generators have a primitive seeding method with the generator looking like the Sea Level Generator.

When I upgrade this system I will update this post with the new Climate Generator.

You are too fast for these 60 second post limits… :stuck_out_tongue:

6

This post is reserved for the River Generator.

When I upgrade and optimize the River Generator following the new Climate system I will post a full write up of that here.

7

This post is reserved for other random systems such as Resources among other things.

8

Dude, I cannot wait to see this when you finish it. There is so much information you have supplied to the community. You are so inspiring to keep going. I remember back in March? when you were just barely working with a basic hex map. Keep up the wonderful work.

9

Thanks! Being able to make this much progress is empowering and knowing that people appreciate the work and information provides extra motivation to keep chugging along. :slight_smile:

I will try and finish filling out the rest of these posts today and tomorrow.

Fortunately and unfortunately, Beyond Earth comes out this weekend so I have to do some “research”. :stuck_out_tongue: I won’t let it suck up too much of my dev time though. :slight_smile:

10

Completed the post on Tectonic Generation.

11

How do you handle your random distribution, when I had a hierarcal generation system like this in an old c++ project (did galaxies down to planet info instead), I essentialy saw it all as a logical tree.
I generate a seed for each child, used that to generate the number of children of each node with a random seed for each. Then each node could generate it’s local contentent.

That allowed me, to genrate the broad scope of the galaxy, and then add details deeper into it, knowing that as long as i don’t change an earlier step it will be persistant and can generate all data up to that point the same, allowing the greater system to stay in place while touching up details.

Are you working out of one seed at top level?

12

By seed you mean something like Random Integer from Seed?

I have wondered whether I should use Random from Seed nodes rather than plain random nodes. I haven’t had any specific need to use Random From Seed up to this point. It might be a good idea to do that with a specific continent setup when I begin to implement the Climate/Weather system. That way I can take the same world and see how all the different weather patterns affects the terrain.

But yeah, right now it is completely random on every generation.

13

Yes exactly. Seeds are good to use for what you say, if you just want to test parameters for a smallerthing depending on the whole.
Also, if the seed is exposed to a end user, and they get a problem, it’s easier to reproduce and figure out.

14

Thanks for the idea. :slight_smile: I will see if I can work that out before working on plate collision. Could be useful to have static plates while I test out different functions.

Should be pretty easy to give the player an option for random or specified seed.

Edit: Well implementing the Random From Seed was quicker than I thought it was going to be, and I spent most of the last 30 minutes playing with my son too. :stuck_out_tongue: Now if only the next thing on the agenda were that easy! :smiley:

15

So I have been pondering my next move with tectonics for a few days now. My initial thought was to find some method for colliding certain plates on the whole, but I came to the conclusion that this method would be rather difficult to implement for the results that I want.

I am going to try a different, more realistic approach that involves setting certain stretches of plate boundary tiles as one of a few plate movement types; Divergent, Convergent, and Transform.

Divergent boundaries, whether Continental or Oceanic, will have Ocean Seeds.

Convergent boundaries will get seeds depending on the plate type. Ocean plates gets Ocean Seeds and Continental plates get Land/Mountain seeds along the Convergent boundary.

Transform boundaries will probably get a mix of Ocean and Land/Mountain seeds.

This should create a range of terrain features similar to the Atlantic Ocean, the Rockies and Himalayas(at least partially), Central America, etc.

16

Colored the plate boundaries by plate and set up a toggle so I can hide/unhide that overlay in game:

You will also start to notice that the plates, landmasses, and vegetation are all locked to a specific random seed so the changes from the plate boundary types should be apparent between screenshots going forward. (Thanks TheSpaceMan :slight_smile: )

17

I would be interested after following your progress for a while to ask how much time does it take to generate a world per size setting? For simplicity lets say generating a small, medium and large map.

18

200 tiles is a couple seconds, 5000 is ~20-30 seconds, and 20,000 is ~210 seconds.

I imagine that putting my core distance checking algorithms into C++ could give me 30-50% more efficiency, but I don’t have a pressing need to move into the source just yet.

There are probably a few other optimizations I could make, such as the river generator taking 30 seconds by itself on a 20,000 tile map(a lot of wasted rivers in that gen).

19

I understand, Thank you for sharing. I was just curious.

Good progress so far, Keep it up.

20

Thanks. :slight_smile:

Got the plate boundary types partially implemented. It was one of those things where I sat in front of the computer like a zombie for 6-8 hours and then basically completed in 2 hours of in-the-zone development.

In this image the tectonic plate boundaries are marked based on whether they are Divergent(Red), Convergent(Purple), or Transform(Blue):

800Ă—383 451 KB

The key piece was ensuring that a boundary type stayed consistent from one end of the plate to another, generally only changing when crossing paths with a different plate. Also ensuring that both sides of a plate boundary line kept the same boundary type(so converging on converging, diverging on diverging).

The transform boundaries is rather tentative in the current state. It is basically acting a stopgap to handle those areas where 3 or more plates meet in one location, or some areas where a plate boundary is doubling back on itself. Ideally, transforms would occur at certain locations and stretch on for a small distance such as seen with the San fault. They are rare enough that I might not care about them though, and they generally don’t create significant geological features that differ from a convergent plate boundary. At least not enough different to matter at this level of simulation. We will see if I implement transforms any further.

There are still a few problems I am working out though. If you notice in the SouthWest ocean that the convergent plate boundary to the north is feeding landmasses down into the ocean. That boundary should have seeded water since it is convergent on an ocean boundary, yet it is seeding land for some reason.

Generally I intend for Ocean-Continent Convergence to Seed land(and mountains) on the continental boundary and water on the ocean boundary. Ideally, this would give a nice clean coastline like you see in Western North/South America.

2 Continental Plates sharing a Convergent boundary will both seed land, and later on Mountains, which should lead to a mashup similar to India hitting Eurasia, though probably on a much larger scale in many cases. It will take some serious fine-tuning to allow the players to determine how big and how often these continental convergences occur.

2 Continental Plates sharing a Divergent boundary should seed water on both sides which should lead to cases like Eastern North/South America and Western African/Europe. The mid-Atlantic rift would be this divergent plate boundary, and would cause the growth of the Atlantic ocean or similar.

My problem with the land seeds being out of place will probably be solved when I ensure ocean-ocean plate boundaries are divergent, but I will have to work this bug out first since I think the plates are being mis-labeled somewhere in the process.