This the second of three update posts about the new level generator. The introduction is at Post #1 and the third/last part is at Post #3.
I will now go into step-by-step process of the generation passes. For clarity, I will try to explain things in the way that makes most sense rather than sticking to exact technical pass layout. I'll try to group sections by generation "topic", although there is a lot of overlap.
Clusters
Previously, the generated terrain was based purely on a noise map (Perlin noise). This created decent-looking gradual layouts, but this did not let me actually change anything in absolute values. That is, I could adjust things relatively - for example, have sand at 5% threshold, but then it would be random amount of sand up to 5% on any size map, which might be terrible on huge maps. There was no way for me to say - I want only 3 "patches" of sand, because there was no concept of a "patch" or "scale".
So the first and main terrain step is to produce discrete "clusters" (based on the map size). First, I generate a bunch of random (shapeless) points:
Then I tessellate these (basic Voronoi diagram) into individual (shaped) clusters:
Due to randomness, some of these often end up being too large or too small, so I run an extra smoothing/averaging pass (Lloyd's relaxation):
This produces a nicely distributed and organically-looking pattern (kind of like cells). Jumping way ahead, this is what will give the terrain the "clustered" look I'm going for (warning: now you will never unsee it):
Water
The next big thing that I generate is the separation between water and not-water by heightmap, which is a convoluted way of saying that I'm building a coastline. This is where a noise map like Perlin noise works really well, so that's what I'm using:
Now, I cannot directly apply this to clusters, because the edges need to be water and the middle needs to be the island mass - by design. Previously, I was using a squashed circle on top of the height map to "cut out" the rough shape, but this created a lot of water in some directions and too much land in others. So now I implemented a much more accurate hex shape with proper "distance to edge" calculations:
I can then overlay this shape over the actual heightmap, reducing or increasing the random value to force it below or above certain thresholds:
This makes sure that anything outside the "big" hex becomes water and anything inside the "small" hex becomes land. The in-between area is then where the noise actually affects the shape. With some visual experimentation in later passes, I can tweak the noise parameters to produce satisfactory results.
I can then apply the "clamped" height map values to the clusters themselves and decide which clusters become coastal shallow water and deep water:
Of course, due to the very nature of applying thresholds to randomness over an area, I sometimes end up with little inland pond and offshore islets. For gameplay purposes (and all the issues these cause), I am removing these when I find them:
And this is just the start of the "battle" against randomness "ruining" my islands. I'll talk about this more a little later.
Island shape
There is no perfect way to generate an island shape. Perhaps there are more suitable algorithms just for the island shape generation, but I also have all the other generator's parts to consider and they have to all be compatible. So instead of seeking some perfect algorithm, I'm just brute-forcing the generation a bunch of times until it doesn't get rejected. Some passes are there purely to reject the result and tell the generator to restart.
One such pass is for, broadly, "island shape". I generate a few "control points" in a rough approximate ellipse around the island and check if they are land or water:
If there's too much water, too much land or too much repetition, I reject the shape. Otherwise, it's probably interesting enough to keep. There is no science behind this - I was just looking at hundreds of islands until I came up with heuristics and parameters that struck a good balance between random and still somewhat hex-like shaped.
This is a good time to reflect on just how many maps I generate throughout the process:
I have set up my generator to support output export at every step, so that I can leave it running for many iterations and then check them for any systematic problems. This is not something I could do before, and this is an invaluable methodology for designing and implementing a system like this.
Climate
Among many experiments to make different regions of an island feel more varied, I settled on a "climate" concept, which flags clusters as belonging to a certain climate (to a certain amount) and other passes can use this data to alter their generation. So this doesn't do anything by itself, but it provides additional customization for later passes. It's kind of like biomes, but currently there isn't any biome-specific terrain, so I'm calling it "climate".
For start, I select a few "control points" in a circle around the map (I chose this shape for simplicity and because the maps aren't large enough to come up with complicated layouts). Each climate has a area it can influence:
Then several climates are assigned randomly, specifically 2 forest, 2 plains and 1 rocks (and the rest stay default):
These are just thematic names that describe my intentions. The climate regions then flag clusters within their influence with an appropriate climate value/weight for later use:
Again, jumping way ahead, slight variations is later passes would create noticeable differences:
Spawn
Previously, I placed the starting area or spawn in the middle of the island and manually cleared it from obstructions and non-buildable tiles. And while this works, it's implemented backwards. Instead, what I really want is to decide on the spawn location and then make sure I don't obstruct it with anything and place the relevant things around it.
So now I pick a random location on the island within a spawn selection area torus:
From there, I pick a valid (for example, not too close to water) closest cluster and construct a spawn area (this uses the same logic as regions, which I will describe later):
This creates one "main" point for the spawn and "grabs" nearby clusters to expand the area to a specified desired size. In addition, I place several "meadow rocks" areas, so I can spawn starting stone deposits around but not on top of the spawn area.
Finally, I create a small spawn exclusion zone, where many things can generate normally, but it will mostly remain free of obstruction:
While this may sound simple, it's extremely easy to get wrong and took me enough experimentation to make a working version. There was a good reason why I previously kept the spawn centered and it was to avoid the many issues of random placement of potentially-overlapping terrain features.
Regions
Most of the map is generated in two big parts - discrete features like rocks and clay patches and continuously semi-random ones like forests or flowers. Regions are for preset discrete locations, so they have to be generated first before everything else is "filled in".
It is very difficult to break down region generation into multiple passes, because they are basically all identical except their rulesets. And separating these rulesets is only useful for visualization (which would take huge amounts of work, so I didn't really do it). So what I end up is producing the region map in a single pass:
Generally speaking, regions are groups of neighboring clusters that form an area for some purpose. For example, there could be a 4 cluster region for coal rocks. Each type of region has a long list of hand-crafted rules and requirements, mostly derived from experimenting. Plus, most of these have some sort of rules about distances in relation to each other. So it makes more sense to just see the results for all at once.
For example, here is a ruleset for placing sand regions:
What this says is that it will place 2-3 region with 2 clusters semi-randomly; it won't place two regions close to each other and will place regions close to but not next to the coastline.
There are many more rules and nuances I could add, but it's best to keep it simple - more parameters just means more work adjusting them and debugging issues. And there are already 12 different region groups just to match the basic level generation goals.
There are some notable rules though worth mentioning. For instance, some regions are much more likely to generate in certain climates. Notably, all rocks-based minable regions are more likely to appear in the rocks climate:
Jumping ahead to final generation, this would allow the terrain to shape village direction and create a part of the map that would naturally focus on mining and industry:
This is not something I could have influenced like this before and is only possible because I can "direct" such discretely-selected regions towards certain results I'm looking for.
Another example is a beach region (in addition to regular thin noise-based beaches discussed later), which randomly generates along the coast in a few locations:
This adds variety to the map without covering half the map in sand, like it used to do before.
I should note that while this is how I primarily use the regions for now, they do not specifically just control tiles (grass, sand, rocks, whatever), rather they flag the clusters as belonging to that region. In fact, the number of tiles that later get converted to their "region designation" is more strict than "cover the whole region". So regions in that sense more of an abstract layer informing later generation what to select but not necessarily exactly how. More like "this is a good place for X".
Filler regions
The second type of regions are the "filler" regions that, as the name implies, fill out the rest of the clusters that aren't already designated for something. Because this doesn't require any discrete counts, this can be done with a noise map. I'm using several slightly different noise maps for different purposes, specifically tree cover, tree types, plant type and tile variation. It's also fairly simple to add new variants and then use them in later passes.
For example, here is (part of) the tree cover noise:
This assigns a "tree cover value" to each cluster (point):
Then a bias to increase or decrease the noise value is applied based on the climate it's in:
These are small adjustments that each climate provides, but they can create a significant variation for each "filler":
Now with the noise values decided, empty clusters can decide what sort of content they want. For example, tree cover decides where the forests will be located:
These noise maps will be further used in later passes for relevant selections. The above selection was more or less binary, but there are many more things that can be decided based on the full range of the random value.
And more!
I'll continue describing the remaining steps in the next, but this seems like a good time to reflect upon all the things that I am not doing. As I mentioned, it's important to set myself some limits on what I'm implementing, otherwise I will never finish this. I am certainly thinking about a lot of cool things that I could do.
As an example, I used the cluster layout and the Voronoi diagram edge connectivity to build a cluster "height map", spawn a "lake" region and then build a river running from the lake to the nearest coast:
Of course, this is far from something that I can translate into tiles and gameplay, so it's more of a proof of concept. But I thought to mention this just to give an idea of the possibilities.
Next post: Post #3