This the third/last of three update posts about the new level generator. The introduction is at Post #1 and the second partis at Post #2.
At this point we have something resembling a map:
It's probably fair to say that the generation logic so far is already complex. But this is only perhaps third of the way to the final map implementation-wise. As more passes work with the data, they make smaller and more specialized changes. There aren't too many steps left, but they are generally an order of magnitude more complex in implementation than most preceding steps. This is also why I attempt to get as much top-level decision making done as soon as possible, so that the later passes work with smaller and more specific parts of the map without making any significant changes to the overall direction.
Tiles
The next big transition between the two generation parts is to actually create a tile layout on top of the clusters. This is quite literally how it works:
The main change is that the tiles actually correspond to the in-game tile hex layout (and all the math from here is in hex grid). It's also important to note that they are much denser than the underlying clusters, so all operation are way more fine-grained:
In other words, a single cluster is represented by a collection of tiles. This is how the cell-like structure of the clusters gets preserved to the final version.
The tiles that get selected (at least, the initial version) pretty much just match the cluster they are on:
While it was not really productive to design the main shape of the island using tiles are the basic "unit", it's important to start seeing individual tiles once the main shapes are determined, so going forward all changes will be done to tiles (directly and indirectly):
The downside of using purely random points to determine the clusters is that sometimes they are just too small or too large when they get converted to tiles. And there's no good way to handle this generally. These are basically statistical outliers, so after "placing" regions into tiles, I also either trim or expand them to a maximum or minimum number of allowed tiles:
The perfectionist in me detests this kind of bodging. So this may be a good time to reflect on this.
Randomness
Randomness is always battling with order. As a concrete example, to create interesting rocky patch shapes I have to allow the random values to be random enough that these shapes get generated. I cannot restrict it too much or I will end up generating the same blob over and over. The problem of course is that random generation has no concept of subjective values like "interesting" or "balanced" or "doesn't break pathfinding horribly". To put it another way, the more cool stuff I let in, the more bad stuff sneaks in. Consequently, the more freedom I allow, the more rules I have to write.
There are several ways to ensure that the generated result is compatible with my goals. Barring just hard-coding all the values, I broadly label these "threshold", "fix", "retry" and "accept". This might sound like nitpicking (and I certainly didn't foresee myself writing an essay on randomness philosophy). But given that I have to make dozens if not hundreds of decisions as to how I will handle each such value, there emerge several patterns.
"Threshold" means setting a strict limit to the possible output of random generation. It may be strong bias, it may be a preset range, it may be a hard limit that cannot statistically be outside the designed range. For example, the middle of the island is always solid land - the threshold for land simply exceeds the noise values that are clamped to the hex shape there. The downside is that such thresholds are often fairly restrictive and I may miss out on interesting outputs simply because I deny too many.
"Fix" is the consequence of letting a lot of randomness through. Subpar outputs and awesome outputs are different ends of the same spectrum. If I aim to preserve the good bits, I have to be prepared to handle the bad bits. Besides reading like a fortune cookie, this just means applying certain fixes to expected problems, like the above example of under/over-sized regions. There is a downside though - I have to actually implement it, test it and forever maintain and adjust it with the rest of the generator, which is all the more complex because of it. This is also an excellent reason to keep such fixes self-contained in separate passes and easily reviewable.
"Retry" means literally that - just run it again. There are two general cases when I would do this. Firstly, if something breaks or I cannot generate something. For example, I might want to place a sand patch 5 tiles away from all the clay patches, but I just happened to generate clay so uniformly that there's no place on the map to place sand now. Secondly, when I don't like the result. Like the earlier example with the island shape - I might hard-code some subjective rules, filters or conditions. As easy as this solution is, it's also dangerous to start rejecting too often rather than have better rules. It's also too easy to filter too much and not give randomness a chance to produce neat results. And with a complex generator like this, one must consider that it becomes computationally costly - I just cannot retry things hundreds of times, especially during later passes.
And finally "accept". Sometimes I just have to give up. The result will never be without fault. That's statistically impossible. The good news is that this is actually mitigated by the layered complexity of the generator as well as high error tolerance of the game itself. It's actually surprisingly difficult to generate a map that's unplayable. Even a tiny map that can barely fit anything and fails half the checks is perfectly playable (and I didn't even cherry-pick the example, I just ran the game once):
Shape cleanup
Similarly to clusters, tiles may end up with small ponds and islets because cluster connections do not always translate to tiles perfectly and it's occasionally possible to create "gaps" between clusters when represented as tiles:
These are really rare and they also don't really matter for other non-water clusters. For example, a gap between a forest in the final layout just makes it more varied, but doesn't cause any gameplay issues:
A bunch of logic depends on coast distance, so I calculate each tile's distance to water and land:
Previously, I often encountered islands with annoying unusable coastal extrusions (long peninsulas) that mostly ended up as sand anyway. Similarly, there often appeared long water "tunnels" into land. I still occasionally get these:
However, now I attempt to find "landmass" and "water mass" areas, which are basically tiles that are deep inland or far from coast. This identifies any regions that are only connected by narrow strips of land/water:
As these are undesirable, I reject these results and retry the whole generation. It's fine for there to be extrusions like this, but they have to be "reasonable" and ensuring "wide connectivity" is the approach I found best to preserve enough interesting but not broken shapes:
Another common issue is an undesirable proportion of land-to-water ratio. Some shapes end up being too large (basically a hex), others too small (boring blob in center). So I calculate how much water there is that's not close to the coast and reject shapes with bad proportions:
A similar common issue is the whole shape being "offset" from the center so that some coastlines are really far from the "world edge", making for huge undesirable water stretches. I reject these shapes as well:
Coastal cleanup
The height map random noise does a decent job of creating shallow and deep water around the island, but it is also prone to creating excessive shallow water. Since I cannot "fix" it during the initial noise pass (I would also affect how much land generates), I manually trim away shallow water too far from land (convert to deep water):
This basically makes deep water transitions more "aggressive". This is also mostly a result of visually confirming what sort of shallow water amounts and variations look goods.
Similarly, sometime the noise transitions are so "steep" that deep water ends up touching the coast, so I offset any deep water too close to the coastline (although I fine with there being only a little gap):
Finally, all this fiddling with water level may end up shallow offshore patches. I did consider leaving them in as small cool variations in the ocean, but they almost never actually look good because they are just extreme outliers of the height map noise. So I basically remove them:
Previous height map also controlled the beach elevation. That is, I spawned beaches based on the height map, which was based on the map size. This created really huge sand areas around the coastline, especially where the coastline wasn't regular. So far, I have completely removed any sand at the coastline except the specially designated beach regions. But I do actually want some narrow beach tiles to randomly appear. So I'm using some noise values to randomly change coastal tiles to sand but only with specific thresholds to avoid any excess:
Despeckle
A common issue with the resulting tile layout is that they sometimes have "sharp" edges - tiles that are almost completely surrounded by another tile type. This just doesn't look good in the final version, so I added a pass to trim these to match their surroundings:
With several iterations, this cleans up any unnatural looking extrusions.
A special case of this are coasts that may end up with micro-extrusions of single-tile peninsulas. I really don't like these in the final resulting tile layout, so I trim these:
Technically, this trimming happens before all the water coastline logic because I cannot modify water/land tiles once I have established the distances. (It was a "fun" bug to chase that caused the generator to crash every 1000th run or so.)
Tile variation
At this point I assign tile variation to the map based on a noise map:
Currently, this only affects grassland tiles (and technically forest tiles that may revert back to grassland). Compared to previous generation, these patches and transitions are a less messy shape and don't overlap contrasting variants as much. Similar to other noise maps, climate affects these for some extra variation between "biomes":
Previously, I used the same height noise map for these as all the other features and while it looked fine, it was also very obvious purely random and not following any sort of natural "land" layout.
This might seem like a fairly trivial decorative feature to discuss in such detail, but the map looks really ugly with all the grass tiles being the same variant, especially after seeing the varied background for so long. Seeing such a huge difference made by such a small variation makes me consider all the other places I can vary in minor ways but to great effect.
Fillers
Finally, I get to filling the contents of regions. This is also what I call the process and the objects - fillers. Specifically, I will spawn trees, shrubbery and deposits all with the same general methodology and much shared logic but different details. Similarly to region creation, this will involve fewer passes that instead process numerous entries but in different ways.
First of all, I need to determine the "depth" of the region tiles, i.e. how far from the region's edge they are:
This may sound like a small thing, but it's a very important step that has huge impact on the resulting visual layout. Without this information, I wouldn't be able to make any transitions between region sufficiently gradual (or sharp) to look decent. It's also important for spawning the right amount of fillers, like deposits. This is not something I could not have done previously, because the map had no concept of "region" - all locations where only as gradual as the noise map at that location.
Currently, I do 3 runs for the different groups. Starting with trees, which get spawned in the forests (regions):
The placement rules, which are basically "how many trees per tile in which tiles" comes from the ruleset I specify:
An earlier generated noise map for tree types (which was affected by the climate) is then used to decide what type of tree to place - spruce, maple to birch. This all ends up creating a nice mix of trees in semi-contained regions:
Very similarly to trees, I place minor vegetation - shrubs, grass and flowers. They also have their own ruleset and noise map, but things are just tweaked to accomplish what I want visually (which really is 90% of how I come up with the parameters):
And finally, I place deposits in the earlier established deposit/minable regions:
Most importantly, these are not just randomly spewed across the map with too many or too few tiles, but rather deliberately chosen to occupy certain areas and be of certain size (as per their region). This is one of the main problems I had with the old generator. Now, deposits follow specific rulesets, including actual deposit counts:
It is also important to note that deposits come with the "amount" value. While count means "how many per tiles" - 1 to 3, amount means how many "logical states" they get in gameplay, which translates to how many times they can be mined.
Even a simple algorithm for "filling" the deposits into a region to look nice and natural ends up being a fairly complex process. For example, I prefer to fill in the deeper region tiles before filling the outer tiles. I also want deeper tiles to have more minable amount than outer ones. But all of this is still randomized.
Output
At this point, we reach the end of the generation. The way I have structured the generator, I technically started implementing it with an input and an output pass, so I have always had "the output". This really is an arbitrary point, which is decided by what the game needs and when I stop. As I mentioned at the start, the primary goal was to get it back to working to the same level as the old generator plus fix the primary problem. At this time, that is roughly where it's at. Of course, it's easily extendable in all sort of ways now, so when I'm adding new features, I can now also consider making changes to the map generator.
I skipped describing much of minor logic and a lot of details. I also skipped all the things that didn't work - a lot of the above is the result of experimenting and making multiple versions for passes. I might mention some if and when I add some feature that is tied specifically to some part of the generation.
Combining all the outputs and data from the passes, I get my final "image":
Importantly, this is all not presented in the actual game, but rather only in the separate generator "project" visualized with a quick debug texture creation. And this also contains all the important data from the preceding passes, that does not appear in the final game in any form. For example, none of the cluster and region information, none of the noise maps or stuff like climates is part of the gameplay. Probably 90% of the data gets discarded. In fact, the only new data that I store compared to the previous version is the spawn location. But this data can be fed into the game now, which really "only" has to spawn the things that the output asks for - tiles and props plus whatever hard-coded spawn features. Notably, the game doesn't have to "fix" anything that the generator messed up - it's basically expected to be correct.
Final thoughts
I've been writing the main points to these posts along with implementing the generator. By the time I'm publishing the update, I do a full write-up from these key points. And, oh boy, were there a lot of those! By the end of it, I could hardly remember what I meant by half of the stuff I wrote down at the beginning. These posts also serve not just to discuss my progress publicly, but also to help me think through many design decisions by "talking them out". And there is still a lot to talk about, but I have to keep it relatively short (I say while having to split this up into 3 parts due to length).
The main conclusions and future plans can be found in the first part: Post #1.