Speed up custom map generation

[fabsemcfunk]

I want to implement my own map creation algorithm using my own implementation of Worley / Voronoi Noise in Lua. Unfortunately it turns out to be quite slow which causes a short but noticeable break about once each second which is extremely annoying. I believe this is the case because the game keeps generating new chunks in the background (I use the bootstrap on_chunk_generated to modify the generated chunks)

I don't want to limit the size of my map, so generating the whole map at the beginning isn't an option.

I see 2 possibilities to overcome my issue:
1. Parallelize my noise creation. The noise values are completely independent of each other, so it should still be deterministic. Is that possible? I didn't find anything on parallelization in Lua here in the forums

2. move the terrain generation to another part of the program where I have more control over it so I can generate smaller chunks. The drawback of this method would probably be, that I have to implement my own logic when my terrain generation should take place (e.g. when a player is within a certain radius of an ungenerated chunk)


any other ideas?

[darkfrei]

On chunk generated make handlers, on tick work with small amount of them.

The handler here is something like {surface, position}, save them in global.handlers do online few calculations on tick.

[eradicator]

You can use LuaSurface.request_to_generate_chunks(position, radius) and LuaSurface.force_generate_chunk_requests() in script.on_init() to force the game to generate a bunch of chunks *before* the map starts. This will make the map startup slower, but you won't get the stuttering from the background chunk generation at the beginning.

But honestly, the background chunk generation is really slow, like one chunk per second? If your algorithm produces noticible stutter from that then i expect it to generate massive lag when the player actually moves around to explore the map. Have you looked at the noise_expression system that the map generator internally uses? If you could make your algo work with that instead of implementing it in lua it would be significantly faster. (I don't have experience using that system so i can't say much else about it.)

No, you can't parrallize, most of the game - including the lua state - runs single-threaded.

[slippycheeze]

No, you can't parrallize, most of the game - including the lua state - runs single-threaded.

...and this isn't gonna change, either: even if you can get it right and be absolutely deterministic in parallel work, fabsemcfunk, other people won't get it right, and that'd cause desync in multiplayer -- directly, or from your interaction with the C++ API triggering actions in a different way.

Do what darkfrei said, spread your work over time.

[eradicator]

Do what darkfrei said, spread your work over time.

Chunk generation by it's very nature is already somewhat spread over time. If you spread it any further you risk having the player run against a black wall. Modded minecraft is very prone to this - you frequenty stand next to an empty chunk and have to wait till the game finally catches up with generating - makes sure the player loses all will to explore at all. When the player goes to explore the world it's not the time to save cpu on map generation. And you can't pre-generate the map because you don't know where the player will go.

[slippycheeze]

Do what darkfrei said, spread your work over time.

Chunk generation by it's very nature is already somewhat spread over time. If you spread it any further you risk having the player run against a black wall. Modded minecraft is very prone to this - you frequenty stand next to an empty chunk and have to wait till the game finally catches up with generating - makes sure the player loses all will to explore at all. When the player goes to explore the world it's not the time to save cpu on map generation. And you can't pre-generate the map because you don't know where the player will go.

It isn't terribly hard to do this in core, without mods touching on_chunk_generated, in my experience. Most easily demonstrated with the editor, just moving in one direction will exceed the ability of the game to generate chunks. At least on my system. All the stuff other than basic terrain tiles fills in behind.

...and the problem here is that they are emulating C++ features with Lua, which is going to be somewhat slower – especially because it'll usually duplicate the C++ work already done. If they want to reduce the performance hit, they gonna have to work to spread stuff out over time, deterministically. There isn't another choice, save for "not doing it at all" which is, y'know, probably not desirable to them.

[eradicator]

It isn't terribly hard to do this in core, without mods touching on_chunk_generated, in my experience. Most easily demonstrated with the editor, just moving in one direction will exceed the ability of the game to generate chunks. At least on my system. All the stuff other than basic terrain tiles fills in behind.

Using the editor is not "playing the game" and comparing on that basis is equivalent to comparing to use of mods/commands that make you 50 times faster. The fastest you can go in vanilla is 10 exos (the FFF used external tools), with which even my rather slow system can keep up (if barely). But that's not the point. @OP said his algo can't even keep up with the player *not* moving at all at the beginning of the game. There's nothing to spread if you're below the 60UPS margin to begin with.

...and the problem here is that they are emulating C++ features with Lua, which is going to be somewhat slower – especially because it'll usually duplicate the C++ work already done. If they want to reduce the performance hit, they gonna have to work to spread stuff out over time, deterministically. There isn't another choice, save for "not doing it at all" which is, y'know, probably not desirable to them.

But ye know, even ignoring all that...*what* do you even want to spread. Like i already said: If the player is just sitting in their base then no chunks are generated. And if they start exploring they need the chunks *right now* and it's too late to spreading.

TL;DR: The only time you *have* outstanding chunks to spread is when the player needs all of them ASAP.

[fabsemcfunk]

Thanks for the feedback!

The noise expression system look, although on first sight I don't see a possibility to implement cellular noise with it. But I'll dig deeper!

No, you can't parrallize, most of the game - including the lua state - runs single-threaded.

I kind of expected that

But honestly, the background chunk generation is really slow, like one chunk per second?

It's not that slow. It takes maybe 0.1 seconds for about three chunks. But it's enough to make the game stutter.

If the player is just sitting in their base then no chunks are generated.

I believe this is not true. Like I said in the original post, the game generates a few chunks about once a second, even if you don't move! I guess, eventually it will stop generating them, but I ran a game for about 20 minutes without moving and still new chunks were generated (I checked by writing a line in the log file each time on_chunk_generated was executed)

[eradicator]

I'll try to explain it better. I haven't done *that* much with map generation so my observations may be incomplete, and i have to mostly guess about the radius which is affected, but the general principlpe is the same. The game generates chunks by three processes:

1. When a mod/command forces the game to generate more chunks.
2. When the player move close to ungenerated chunks these will be generated with high priority. Probably with a radius of about ~5 chunks or so around the player, i.e. stuff you could see if you fully zoom out.
3. In a slow background process from a list of "low priority" chunks. "Slow" here means that the process generates chunks *slowly* (i.e. one per second), to conserve CPU.

Now...how do chunks get into the "low priority" list?

1. When a player moves around, then a certain radius *beyond* the immedeately generated 5 chunks radius is put into the queue. Probably another 5 chunks (for a total of 10 chunk radius around the player).
2. When a radar scans a chunk everything in a radius of around ~5 chunks is put in the queue. You can see this if you open the map and force a chart of all *existing* chunks on an old map. (On a freshly created map the effect will barely be visible, if at all.)

   Code: Select all

   /c game.player.force.chart_all()

3. At the beginning of a new map everything within a 20 chunk radius will be put in the queue. You can confirm this easily. Start a new map. Do not move. First attach a listener to on_chunk_generated:

   Code: Select all

   /c
   p = game.player
   function chart(radius,position)
     local radius   = radius   or 32*5
     if radius <= 32 then radius = radius * 32 end
     p.surface.request_to_generate_chunks(position, radius/32)
     p.surface.force_generate_chunk_requests()
     p.force.chart_all(p.surface)
     end
   
   script.on_event(defines.events.on_chunk_generated,function(e)
     game.print(string.format('Chunk generated. Map age: %.i seconds.',game.tick/60))
     end)
     

   You will see that the game generates one chunk per second in the background. Now we can force the game to chart everything in this radius immedeately:

   Code: Select all

   /c chart(20*32,p.position)
   

   This will take a few seconds but after that you will notice that the background chunk generation has stopped.

______________________

At 1 chunks / second the initial background generation will take (20*2)^2 / 60 = 27 minutes to finish. I recommend you use /c game.speed = 100 or something if you want to measure it faster and don't trust my code.
______________________

It's not that slow. It takes maybe 0.1 seconds for about three chunks. But it's enough to make the game stutter.

Factorio runs at 60UPS, thus each tick has 16.67ms (milliseconds!). If you use 33ms *per chunk* then you'd have to distribute the generation of a *single* chunk over at least 3 ticks to not stutter. And that's only before the player builds a factory that eats all the milliseconds itself.

If it's interesting enough i'd personally prefer one big stutter every 5 minutes over constant microstutter i think. Do you have some pictures of what you got so far btw? Text-only is so dry :p.

[fabsemcfunk]

Do you have some pictures of what you got so far btw?

Sure. Here you go:

Factorio_Worley.png (281.93 KiB) Viewed 4889 times

Factorio_Worley_3.png (1.94 MiB) Viewed 4889 times

at the moment I don't evaluate the noise at each tile, but only once in a 2x2 square, which makes it 4-times faster, but the edges are jagged.
The images just show the overall shapes that are generated with the noise, I'm well aware that the shown map is probably unplayable because the player is cut-off from all resources
My plan is to create a crash-site-like (from RedMew) scenario but without a map size limitation. And I thought worley noise would be the perfect tool to generate small generic factories. I just hope I'll be able to overcome the modding limitations

[eradicator]

Looks interesting. =)

at the moment I don't evaluate the noise at each tile, but only once in a 2x2 square, which makes it 4-times faster, but the edges are jagged.

Does this imply that you also call LuaSurface.set_tiles() for groups of only 4 tiles? Because that would mean you could gain quite some speed by batching more tiles together.

[fabsemcfunk]

no, I call LuaSurface.set_tiles() only once for each chunk. I'm only new to factorio modding, not to programming ;P

[darkfrei]

no, I call LuaSurface.set_tiles() only once for each chunk. I'm only new to factorio modding, not to programming ;P

But the time for table with 32x32=1024 tiles in some cases needs more than 1000/60 millisecond, the game makes new chunk every few seconds and you get small lags on each of them.

[TOGoS]

It might be possible to do something like this using spot noise. Spot noise returns a value indicating the closeness to the nearest of many points from an internally-generated list. If you took several spot noise expressions (using different lists of points, which you'd get by providing them with different seeds), you could detect edges by where their difference is close to zero. This wouldn't work to find the edge between two points that happen to be from the same list (there'd be nothing to compare against) but by using several lists of points you could cut down on the number of points whose nearest neighbor is from the same list to detect most of the edges.

Very pseudocode:

Code: Select all

diff1_2 = abs(spot_noise(2) - spot_noise(1))
diff2_3 = abs(spot_noise(3) - spot_noise(2))
diff1_3 = abs(spot_noise(3) - spot_noise(1))

elevation = max(diff1_2, diff2_3, diff1_3)

...or something like that. maxing the diffs might not be quite the right thing for more than 2 spot lists, but if you can probably work out the right formula for combining them.

[fabsemcfunk]

I'll give it a try. But in order to achieve the result shown in my pictures, I'd have to do some basic vector calculations. Is it possible to get the x and y component of the distance to the next spot?

Also, I'd like to use the noise for more stuff than just world generation. Is it possible to store the value in some kind of variable/property that doesn't! Affect the world generation? Or do I have to abuse an existing property like the temperature?

From what I saw in the noise expression tutorial, it's necessary to extend data.lua. So I assume, it's not possible to use the noise expression system in a soft mod / scenario. Is this correct?

[slippycheeze]

I'll give it a try. But in order to achieve the result shown in my pictures, I'd have to do some basic vector calculations. Is it possible to get the x and y component of the distance to the next spot?

Generation is independently evaluating each point, so far as I understand, so I don't believe this would be possible. Perhaps there is another way for that to work, however: what specific calculations are you thinking of here?

Also, I'd like to use the noise for more stuff than just world generation. Is it possible to store the value in some kind of variable/property that doesn't! Affect the world generation? Or do I have to abuse an existing property like the temperature?

What, other than world generation, would you like to use that for? Also, existing properties will have their own behaviours that extend beyond what you want, so ... probably not a good choice.

From what I saw in the noise expression tutorial, it's necessary to extend data.lua. So I assume, it's not possible to use the noise expression system in a soft mod / scenario. Is this correct?

You cannot define a new noise expression at runtime. You *can* alter the map generation parameters, including any variable referenced in a noise expression, at any time. Best results, obviously, require you to do this on a new surface before anything is generated because nothing *updates* the existing chunks when you change properties, but you can do that at any point if you want.

As supporting evidence for the first comment above, the fact that changing map generation parameters on an existing surface will not retroactively change existing chunks points firmly to the fact that chunk generation is independant, and cannot be dependent on properties of other chunks – which may not yet exist, or may have been generated with radically different inputs. (eg: you can change the logic for water placement from a complex noise expression to "-1000", or a constant "not here".)

[TOGoS]

Either the forum doesn't notify me when there's a new reply or I'm missing something basic about how to use it. Anyway...

I'll give it a try. But in order to achieve the result shown in my pictures, I'd have to do some basic vector calculations. Is it possible to get the x and y component of the distance to the next spot?

Currently not, though breaking up the spot noise function into a spot list generator and various functions to query it (value at point, x/y distance to nearest point, etc) is something that I have kind of wanted to do for a while.

Also, I'd like to use the noise for more stuff than just world generation. Is it possible to store the value in some kind of variable/property that doesn't! Affect the world generation? Or do I have to abuse an existing property like the temperature?

You can evaluate noise expressions associated with a surface (via its MapGenSettings) using calculate_tile_properties:https://lua-api.factorio.com/latest/Lua ... properties

If needed you could create new 'dummy' surfaces for this purpose, or just add new properties to existing ones. Any key from MapGenSettings.property_expression_names will be queryable.

From what I saw in the noise expression tutorial, it's necessary to extend data.lua. So I assume, it's not possible to use the noise expression system in a soft mod / scenario. Is this correct?

Correct, as slippycheeze noted. Though I have toyed with the idea of allowing full expressions to be encoded in expression names, which would allow MapGenSettings to define totally custom ones.