Friday Facts #258 - New autoplace

Posted by TOGoS, Twinsen on 2018-08-31

Taming the random generator (Twinsen)

One of the things in the large TODO list for 0.17 is giving a final polish to the map generator.

There are quite a few obvious problems now in 0.16, and some less obvious ones. Here are some of the fixes and improvements (some work in progress):

  • All combinations of settings should no longer create strange maps such as circles of cliffs.
  • Much more predictable starting area resources that don't overlap each-other and are not covered by water.
  • The resource generation settings now have a much more dramatic effect (previously they had little to no effect).
  • Increased the number of steps (small, medium, big, etc) for each setting from 5 to 9 for even more customization.
  • The starting area will always contain water, most often a lake close to the spawn position.
  • Since the algorithm for generating ores was pretty much completely rewritten, there are many small improvements.

Now for the less obvious problem: unpredictability. I saw quite a few people complain with vague comments like "the map generator sucks". So I often asked them what the problem is in detail. Some were complaining about the above problems, some did not understand what the settings do, and some had problems finding a "good map". I saw quite a few players click "regenerate" like crazy until they got a map with fat patches in the starting area, big oil patch and also uranium, complaining that it's too hard to find a "good map". Due to the randomness we seem to have set the expectation for "good map" a bit too high. Oil and uranium were never intended to be in the starting area, but due to the randomness of the generator they sometimes were there. Also sometimes maps were so wild that you would start off either swimming in resources or desperately looking for another iron patch.

It would be simple to just say "that's just RNG, deal with it", but blaming poor game experience on RNG is just bad design.
So what we did is:

  • The starting area contains only iron, copper, coal and stone, in very predictable amounts. Uranium and oil are explicitly excluded from the starting area.
  • Starting area resources are usually in one ore patch each (depending on settings).
  • The starting area patches are usually close together.
  • The starting area size setting no longer affects resource placement, it just has a fixed size.

Outside the starting area, the regular algorithm "kicks in" so you can still get quite wild results, but they are far enough that it averages out. I believe this is a good balance where you can still have different experiences depending on your luck, but your starting experience is much more predictable and does not leave you with the feeling that you got screwed over by the map generator. We definitely don't want the map generator to be extremely flat and predictable. Opinions on the subject are quite wild too, with people having different expectations of what a good map should look like, so we try to only make changes based on actual problems.

This might seem a bit controversial so we can add an option that disables this whole starting area logic, for purists.

We plan some small tweaks coming to biters also (a tiny bit more biters close to the starting area), small tweaks to terrain, cliffs, water generation and possibly some new features to make the generated trees and decoratives look better.

Most of these problems including the obvious and apparently simple ones were not that easy to solve. It's hard to make random generators do what you want, so TOGoS will explain what it took to actually get it done.

Taming the random generator - the technical side (TOGoS)

Good day procedural map generation enthusiasts!

The terrain generation in Factorio works by calculating probability and richness for every autoplaceable tile, entity, and decorative at every point on the map. To oversimplify slightly, the thing with the highest probability "wins" and then gets placed (if it's a tile) or has that probability of being placed (for entities and decoratives).

As some of you may recall, one of the features we added in 0.16 was a new terrain generation system driven by functional expressions built in Lua code. Mods define a function (not a Lua function, but a data structure representing a function in the mathematical sense) to be applied at every point on the map to calculate those values. This gave us a lot more control over elevation, temperature, humidity, and a few other variables across the map. However, the probability and richness functions for specific objects (notably resources) were controlled by a separate system.

I had wanted to unify these two systems since I started working on terrain generation last summer. Since releasing 0.16, our desire to improve resource placement, combined with my inability to come up with a good way to do it using the existing autoplace system, led me to finally bite the bullet and undertake 'the big autoplace refactoring'.

It was a lot of work.

The result is that existing AutoplaceSpecifications still work (because rewriting them all would have meant even more work), but under the hood they are compiled to expression trees, just like the ones for elevation, temperature, etc. As an alternative to the peak/dimension system, autoplace specifications can be defined in terms of a probability and richness expression directly, allowing a mod author to use the full potential of the programmable noise system.

An advantage of this approach is that we can now add new types of noise expressions without the need to reconcile them with all of the existing autoplace specifications or cram them into the ever-mode-complex monolithic AutoplaceSpecification object.

Specifically to make generation of resource patches more controllable, I added a new noise expression type called "spot noise". The way it works is that the map is divided into regions (large areas whose size is configurable per spot noise expression) and for each region:

  1. A list of random points is generated.
  2. Density, quantity, radius, and favorability are calculated for each point, based on noise expressions provided as parameters.
  3. The total desired quantity for the region is calculated by averaging the density from all points and multiplying by the region's area.
  4. Points are sorted according to their favorability, highest-to-lowest.
  5. Points are chosen from the front of that sorted list until the target quantity for the region is reached.

Having generated a list of spots with position, quantity, and radius, the output of the spot noise function is high near the spot centers and zero at a distance equal to their radius, such that the total value in the spot equals the spot's quantity. This value can then be used (for example) as the richness for a resource (such as iron-ore). By itself, this gives us 'conical' spots (if you think of resource patches as being mountains):

This result can have some noise added to it to make the resulting spots non-circular:

I had to be somewhat careful when applying this noise; since there is more area outside the spot where richness can be raised above zero than there is inside to be lowered, any randomization will add a positive bias to the overall quantity. I have been compensating for this by subtracting some constant fraction of the amplitude of the noise, though it's been on my mind that the problem could also be resolved by using differently shaped spots.

This system opens up a lot of possibilities:

  • We can use the maximum of two different spot noise expressions to place starting area ores using completely different settings than we do for the rest of the map.
  • We can vary quantity per spot and frequency of spots independently, which will allow the sliders on the new map screen to have more predictable effects.
  • Spot quantity can depend on the suitability of the location. For example, we could set suitability to correspond to elevation so that spots are not placed underwater. The system would then continue through the list of candidate spots, placing more spots at locations above water to compensate. In the base game we're planning to do this for starting area resources, but not for resources outside of the starting area.
  • In general, spot noise allows us to mess around with the placement of resources while keeping overall quantities constant.

Here are some map previews of the same seed, to illustrate spot-placed resource patches being moved to avoid water in the starting area as the water level is raised:

Putting everything together, here's what a typical starting area and surrounding region generated by the new system looks like. We may make a few more tweaks before 0.17 but this is probably pretty close:

All that said, I was perfectly happy when ore placement was unpredictable and sometimes there was no copper in the starting area and really long belts (and walls to defend them) were in order. So if I have my way there will be a "no special starting area resource placement" option.

As always, let us know what you think on our forum.