Friday Facts #390 - Noise expressions 2.0

[Hares]

Was thinking, among the planet types you evaluated, have you ever considered a tidal locked one? Like a planet where you have to connect the sunny desert side with the night frozen one through the lush monster filled stripe in between? It could become a the "train planet".

Hmm... They've mentioned that train interrupts are critical on one planet... Is it it?

[TheKingOfFailure]

I would DEFINITELY purchase a set of science pack ornaments(and cogs), plastic or glass. Either for hanging or just as awesome paper weight desk toys. Beakers with colored epoxy in them, not too complicated to manufacture. Things from video games brought into the real world are Just. So. Cool!

[yeputons]

Hey folks, glad to see a bunch of technical details!

At the same time, I'm very worried about creating a DSL, no matter if with an external parser or an in-house parser. It's easy to get a DSL working, but all attempts that I've seen so far (even inside big companies) typically end up in a incomprehensible mess once you try to write a formal grammar/semantics for the language. Best case scenario, they end up being quirks of the language like {}+{} being NaN in JavaScript or

Code: Select all

auto [a, b] = std::minmax(2, 3);
int x = a + b;

being UB in C++. More typical scenario, lots of parsing/semantics hard-to-catch bugs creep in immediately like in https://github.com/fusionlanguage/fut/issues/26 or https://github.com/leaningtech/cheerp-meta/issues/89 or https://github.com/llvm/llvm-project/issues/52790 or some that I cannot share due to NDA. Think "bugs in binary search" or "forgot to process spaces in the beginning/end", but x10 harder to notice unless you specifically look at it. Mostly happens because parsers/naive compiler tend to think about AST and syntax instead of semantics. Moreover, fixing those may require breaking backward compatibility.

Especially once you start adding optimizations. E.g. optimizing 0*x into 0 is incorrect if x has side effects. Does not happen yet I believe, but if you allow mods to provide functions in these expressions... Or x-x not always being zero even without side effects (

infinities, NaNs

).

If you care about the language being consistent, I believe it may be a good idea to do some fuzz testing at the very least: generate a random expression (not an easy feat on itself), add/remove spaces and random variable names, evaluate it with Python/Lua and compare with your engine. I've seen my own toy compiler working fine with random 50-chars expressions, but failing with 500-chars expressions that could later be simplified into 10-chars regression tests.

Would be happy to take a look at relevant pieces of code or, if you have time, have a chat (e.g. in Discord) about different algorithms, standard compiler gotchas, and how to avoid some corner cases.

[Hares]

Hey folks, glad to see a bunch of technical details!

Especially once you start adding optimizations. E.g. optimizing 0*x into 0 is incorrect if x has side effects. Does not happen yet I believe, but if you allow mods to provide functions in these expressions... Or x-x not always being zero even without side effects (

infinities, NaNs

).

Actually, since these noise functions are explicitly declared as math functions, any x/x, x minus x, 0*x, or x/1 (and so on) optimizations are legal. Yes, in math you are not allowed to multiply infinity-like f(x) by zero-like g(x) without the limit expansion, but you are allowed to multiply f(x) -> ∞ by a TRUE zero (constant value), resulting in a zero (constant value). This is the case because math functions are not allowed to have side effects

[Genhis]

I'm very worried about creating a DSL...

Noise expressions DSL has been in Factorio since 2017, but it's true that this rework and addition of functions could have overlooked some issues. Even though we tried to think of valid and invalid scenarios and wrote unit tests, the real test will come when modders start (ab)using it.

Regarding user-defined functions, they can't have side effects and must return a noise expression, so you could think of a function as a "parameterized noise expression". They are external - you can't define them in an expression. Variable assignments are also not allowed.

Next, map generation doesn't need the result to be precise, so we can get away with x*0 => x even if `x` is NaN. NaN is generally not expected but we don't test for it - in the worst case, terrain will be a bit different. There are a few more compromises in the engine to deal with constant folding (x^0 => 1) because we favor performance.

If you want to chat about noise expressions or anything related, I am available on Discord.

[Pithlit]

But that shot with the Christmas tree makes me want to request something else: holiday themed sprites. Either as separate mods, or as things built into the game that automatically enable on and for the duration of the holiday, then turn back off after. And some random joke stuff on April 1st.

There're actually two mods which change science packs and artillery shells into Christmas gifts.

There is already a holiday-themed mod-pack: Christmas Candy Factory
What is missing are snow covered entities - they would be a great addition to this mod.

[fusionfan]

This is quite the deep dive (for me, at least), enjoyed reading it.

[Avezo]

Reminds me of dwarf fortress map generator

[TOGoS]

The hope I had when I created the terrain noise system was that someone, someday, would take the idea and extend and polish it, which it seems you have. It's a slight bummer to lose compatibility with the old Lua noise expression definitions[1] (a goal of that design was to an AST-based common-denominator format for this type of thing), but it was admittedly a heavy data structure, especially when things got complicated. I figured the lack of conditionals would be the main limiting factor of noise expression complexity (since it means every part of the tree needs to be evaluated for each cell of the surface) so didn't worry too much about the 'compile-time' cost (and I had a hard time convincing Rseding that it was 'compile-time', since it happened at run-time from the perspective of the C++ compiler )

As for 'why was it built this way', well, the v1.0 noise generation system was itself a rebuild of Kuba's autoplace system, which used several octaves of Factorio Basis Noise in a fixed pipeline sort of way. There were several knobs you could turn, but you certainly couldn't, for example, take atan2(y,x) and feed that as a parameter to something else. That version was itself an improvement on the original implementation that used a slightly different basis noise function, maybe Perlin noise. And Perlin noise is simply the default tool that everyone grabs for when they need a coherent noise function for infinite terrain generation, if they aren't aware of Simplex noise, which I think is slightly better (it scales to higher dimensions more efficiently due to being based on tetrahedrons instead of cubes and has reduced discontinuities in its first or second derivative, or something).

Of course you don't have to base your terrain generation entirely on coherent noise. You could use recursive subdivision or a wave function collapse algorithm or something like Stable Diffusion or have a room full of people who draw new areas of the world just before players walk into them. But coherent noise has the advantage of being conceptually very simple. All you need to calculate the contents of a cell of the map is (x, y, map-specific constants). And it works well enough that neither Tomas, nor Kuba, nor I, nor Earendel or Genhis felt the need to throw the whole thing out and do something completely different. Though it is of course fun to think about!

[1] I think we (maybe I) can build a compatibility layer in Lua relatively easily. So, modders: don't freak out about having to rebuild your noise expressions for v2.0 just yet.

[ElderAxe]

Lets put this mod from Earendel here. https://mods.factorio.com/mod/cogmas

Happy new year

[JoshuaJosephson]

Surprised that you guys stuck with Perlin Noise instead of doing some advanced Wave Function Collapse type stuff to give scripted areas, like dungeons or mountains/volcanoes on Nauvis!

[Koub]

I can't believe I missed an FFF at some point. Glad I had the opportunity to catch up.

There is one gripe I have with the map generation we've had for the last 7-ish years, it's that compared to the previous one, the starting area is less easy on the engineer. I liked the way iron, copper, stone, and water were a little more tightly packed in a smaller area, allowing less running back and forth before automation, fewer belts (or pipes, or power poles) when starting to automate, ...
Here are two examples of "all default maps" generated in 0.10 and 1.1 :

0.10

2024-07-28 09_14_27-Factorio 0.10.12.jpg (1.02 MiB) Viewed 1014 times

1.1

2024-07-28 09_14_09-Factorio 1.1.105.jpg (1.09 MiB) Viewed 1014 times

Both fully zoomed out. Just compare how things are tighter together in the 0.10 version, the coal, the water, iron, copper and stone are all within reach. The current map has those ressources sooooo spread away, it's like marathon simulator before automation. The starting patches are even closer to the nearest biters than it is to water.

In every other aspect, the current map gen is vastly superior, but ... man I miss the old starting area.

[Qon]

Surprised that you guys stuck with Perlin Noise instead of doing some advanced Wave Function Collapse type stuff to give scripted areas, like dungeons or mountains/volcanoes on Nauvis!

Perlin has large scale features and the ability to evaluate each coordinate individually with only the coordinate and map settings as input, and it's pretty fast. That is what makes perlin noise good for Factorio, without those features the map size would have to very small so that it could completely generated at game start.

And I think WFC is inherently incompatible with those features. WFC has examples of infinite map generation, but it still doesn't satisfy the conditions that Perlin noise does. As an example, you wouldn't be able to teleport from x = -2000000 to x = 2000000 without generating all the chunks between the coordinates. Also the map that is generated isn't determined from just a seed, the reveal order is also important since WFC tries to satisfy conditions for each new chunk with already generated chunks. So unless the reveal order is predetermined (like a spiral out from a singular start) then you get other issues. And then the map size would grow quadratically instead of linearly for explorations in a line out from start since everything within the square that contains all revealed chunks has to be revealed.

Also WFC is much slower, to the point it might be hard to do procedural generation at all at a quality that you would find acceptable. Sure for simplistic rules it could be fast-ish, but if you want large scale features with interesting map features then back-tracking in the algorithm would mean large generated areas would have to be thrown away many times to find a possible collapse. It has similarities with depth-first search, meaning it could potentially explore the whole possibility space before completing. Meaning even tiny maps would require exponential time to finish, making it impossible to compute at all for a computer consisting of the entire universe in all of time. Now that would only happen for some rules and unfortunate evaluation orders, but the point is that you would accidentally make those kinds of issues when you started trying to make interesting maps.

I haven't written a WFC map generator and I don't know a lot about them, but from the small parts I do know there seems to be huge technical issues which are incompatible with the features currently provided by Factorio.

[Hares]

Hou-hou-hou!
We really need that snowy sprites and Christmas Tree in-game!

I assume that these snowy sprites are a sneak preview of the next planet and its particle effect covering all sprites with snow.

Told ya!