Factorio Forums

jcranmer wrote: ↑

Fri Nov 22, 2019 3:23 pm

Each pointer is 8 bytes. As you get to medium-sized factories, that means your lists are each going to be in the 100K-1MB range. You might then say "I've got 8+GB of RAM, who cares?", but the reality is that it's not the RAM that's precious, it's your caches. If your lists don't fit in the cache, you're now paying a miss to main memory to get the address of the location you need to retrieve from main memory, all the while twiddling your thumbs while you're waiting for main memory. When you have enormous memory requirements, performance optimization tends to become all about optimizing cache locality. The classic example here is the random insertion in a list: at what N does it become faster to use a linked list instead of an array list for randomly inserting elements into the middle?

Well said. I'm quite fond of 'data oriented design' for this reason - it encourages using contiguous arrays for most things, and then having the indices (or a pointer) act as an identifier. So if you have an array of generic entities, and then an array specifying which of those entities are a certain type of entity, you can have that second array contain structs/objects that are essentially a pointer to which generic entity they belong to, and also all the properties that are specific to that type of entity.

The result is that if you only want to iterate over one type of entity, you never have to iterate over the other types. But if you need to iterate over *all* entities, you still can. Also, an entity can be made to act like more than one type (if desired) by having an entry in 2 different 'entity type arrays', so that iterating over each type for processing a certain behavior causes one entity to be processed twice, once for each sort of behavior.

One of the reasons behind data oriented design is that when you're performing operations and comparisons across the data of a large set of entities in a list, you're often comparing the same sort of data with each other. For example, if you're processing collisions, you're doing a lot of bounds checking of rectangles. As such, it makes sense to keep all of the rectangles in a contiguous array separate from the rest of the data, so that iterating through them to do bounds checking becomes incredibly fast, as more rectangles are able to be loaded into the cache at a time for such a comparison.

This is why sometimes you just use the indices as identifiers. All entities share some basic properties with each other, so the idea is to have a structure holding several arrays - one for each property. It acts like a table, and a given index should refer to the same entity for every array in the struct.

Edit: Just wanted to conclude with a 'final' example, a more robust version of the first. You can have a structure of arrays for the properties that all entities have, and more structures of arrays, each for the properties that only a specific type of entity has. In this case, since a single pointer won't be sufficient for pointing to the 'base' entity object, the structures for entity sub-types would have an array holding which index to use in the base entity structure of arrays.

im glad you are working on the lag associated with the destruction of the natives, i never liked having to deal with them in large maps, and in multiplayer it can result in a temporally unplayable game, though usually the person fighting dies due to the lag as well. but now i know why the game chugs when people go on a murdering spree, all the particle entities generated and destroyed, and i don't even care about the splashes as they aren't even on the screen for long enough, and the murdering sprees are just clearing of land for me.

Now I know why my framerate is dropping when I go on a rampage with Nukes

Here are some thoughts for possible future improvements.

Take advantage of the commonality between particles produced by a common source.

Say you have a particle source object, which contains the majority of those 64bytes you mentioned. Then a particle would be a tiny structure which would be appended to the source object. Say you used three numbers for the position relative to the source of each particle (16 bits each) and three more for the velocity (8? bits each) a texture offset (8bit) and a rotation (8bit). That's 14 bytes per particle. I believe that would be sufficient to animate all sorts of particle effects. I'm assuming three coordinates because for example the "blood" streams out like a fountain, I think it would be most efficient to model particle behavior in 3D then translate the 3 coordinates to 2D.

Many of these tiny particles could be saved as a contiguous array in a random order. Particle deletion could then be performed in order. Particle update would usually require iterating the array, but this could depend on the specific particle animation.

This idea may not work so well if the source of the particles was itself in motion. I don't know how often that happens in factorio. in these cases it maybe would be necessary to create new sources periodically instead of allowing the sources to move.

@klonan
I have an Idea for the new entity gui
when i click a powerpole you see your current power with the amount of producers (solar, steam, nuclear) but not how much you can reach within that network. Why not adding an value with the max possible power you can get within that network with all same kind of producers. You can only see how many 1 is producing when pointing with the mouse
the reason I ask is because I am very bad in math together
Maybe that is also the reason why I cannot figure out the circuit network

vorax wrote: ↑

Sat Nov 23, 2019 12:05 am

Here are some thoughts for possible future improvements.

Take advantage of the commonality between particles produced by a common source.

Say you have a particle source object, which contains the majority of those 64bytes you mentioned. Then a particle would be a tiny structure which would be appended to the source object. Say you used three numbers for the position relative to the source of each particle (16 bits each) and three more for the velocity (8? bits each) a texture offset (8bit) and a rotation (8bit). That's 14 bytes per particle. I believe that would be sufficient to animate all sorts of particle effects. I'm assuming three coordinates because for example the "blood" streams out like a fountain, I think it would be most efficient to model particle behavior in 3D then translate the 3 coordinates to 2D.

Many of these tiny particles could be saved as a contiguous array in a random order. Particle deletion could then be performed in order. Particle update would usually require iterating the array, but this could depend on the specific particle animation.

This idea may not work so well if the source of the particles was itself in motion. I don't know how often that happens in factorio. in these cases it maybe would be necessary to create new sources periodically instead of allowing the sources to move.

Positions and rotations would be stored in floats or doubles, each being 32 or 64 bits each (respectively). I imagine the 64 bytes are:

1. Position (x and y): 8 bytes to 16 bytes.
2. Velocity (x and y): 8 bytes to 16 bytes.
3. Rotation: 4 bytes to 8 bytes.
4. Time (how long the particle has existed, for calculating where in its path it is and when it should fade out): 4 to 8 bytes.
5. Pointer to texture to draw: 8 bytes.
6. Pointer to particle behavior specification: 8 bytes.

Or something along those lines. If doubles are used instead of floats, that'd be all 64 bytes right there.

That old particle system is really wasteful and ugly design, yikes! Not that I noticed until you pointed it out. Guess it goes to show that when so many aspects are already well optimized, it's hard for even me to spot issues with existing designs. I always assumed mass nukes and so on were slow because they either caused a lot of events to be issued in AI behavior or a lot of calculation with hit detection - of course, it's usually some combination of it all. Either way I'm glad you've improved it.

Always happy to read your FFF.

The 3 things I'm waiting for to continue playing:
-Color update
-New UI (at least character inventory menu, and others very used menus)
-Fluid improvement

Anyone knows when each of those could be ready? (few weeks / few months)
Also, what have been updated yet with the fluids: symmetry, fluid speed (with different viscosity), performance?
What about the UI, I remember seeing a chart in a FFF, anyone has a link to an updated version of it?

Positions and rotations would be stored in floats or doubles, each being 32 or 64 bits each (respectively). I imagine the 64 bytes are:

1. Position (x and y): 8 bytes to 16 bytes.
2. Velocity (x and y): 8 bytes to 16 bytes.
3. Rotation: 4 bytes to 8 bytes.
4. Time (how long the particle has existed, for calculating where in its path it is and when it should fade out): 4 to 8 bytes.
5. Pointer to texture to draw: 8 bytes.
6. Pointer to particle behavior specification: 8 bytes.

Or something along those lines. If doubles are used instead of floats, that'd be all 64 bytes right there.

Im doubtful that a 16 byte number would be necessary anywhere in factorio.
A float for rotation could save a division every time it is evaluated, but there wouldn't be any need for a double unless it's just to follow a convention of using doubles everywhere.

Regardless my main thought was just that there is probably a lot of information that is common among groups of particles.

vorax wrote: ↑

Sat Nov 23, 2019 3:56 am

Im doubtful that a 16 byte number would be necessary anywhere in factorio.
A float for rotation could save a division every time it is evaluated, but there wouldn't be any need for a double unless it's just to follow a convention of using doubles everywhere.

Regardless my main thought was just that there is probably a lot of information that is common among groups of particles.

It's 16 bytes because it's 2 values: x and y. Because it's 2 values, it's 2 floats, or 2 doubles. 2 doubles takes up 16 bytes.

Rotations are usually stored in radians, which absolutely would require a float or double.

Regardless, you never want to 'append' things to an object. Every time you 'append' to an object, you change its type - and you deallocate and reallocate the whole thing. Instead you would have a pointer to an array, probably contained in a vector or other such wrapper class.

However, there's no reason to do this. There's no reason to associate a particle with the parent object that created it, because the particle is a visual effect. There might be many types of particles, and they might be spawned by many items, but once they're spawned at all it no longer matters what spawned them - just matters what type of particle they are, and even that only matters so that motion can be calculated correctly each frame and the correct sprite can be drawn.

Ohz wrote: ↑

Fri Nov 22, 2019 6:23 pm

If you lost count, this scene contains 15,689 entities

oh ok

Definitely not 15,688.

Edit: I just went from being a red inserter to a blue inserter. How in the world am I supposed to reach the belt now?

ColonelSandersLite wrote: ↑

Sat Nov 23, 2019 5:04 am

Edit: I just went from being a red inserter to a blue inserter. How in the world am I supposed to reach the belt now?

Okay, with optimizations like this it's more understandable now, why we have still less than a year at hand before release. Factorio appears to be the only game, effectively achieving its sequel before even reaching 1.0.

you mentioned saves... I hope it dosen't save smoke and fire and stuf taht is temporary in save file... Also i see on multiplayer map somtimes saves become huge. And fiting on whole map might be problem too if you save all particles.. Maybi exclude particles of things that have moment efect like smoke and flametrowers for 1 s, and you catch up to them when you load up.

This guys... They never ceases to amaze me.

Does this mean the game world can have random "particle" effects that pop up whenever?

I say, why stop at two kinds of entities? Why limit yourselves to normal entities and particle entities? What if there was two kinds of particles, ones that do affect gameplay and those that are pure eye candy?

Rseding91 wrote: ↑

Fri Nov 22, 2019 1:28 pm

Lubricus wrote: ↑

Fri Nov 22, 2019 1:03 pm

Isn't particles usually some sort of shaders that only lives in the graphics card? And thus use no CPU power nor RAM.

Particles in Factorio can spawn other particles, other entities, smoke, do damage, and so on. They couldn't ever just live in render-only land. Also, you still have to spend CPU time and RAM to tell the GPU what to do so it's never possible to "use no CPU por nor RAM".

You could still ban the real particles (the simple eye-candy-only ones) from the CPU and RAM and let the GPU do some work too.
Factorio is a CPU-heavy game. Don't forget, that there also is a GPU wich often has dedicated RAM and a lot of small compute units wich would be happy to move thousands of particles around each frame. One less system competing for the CPU cache.

Oktokolo wrote: ↑

Sat Nov 23, 2019 9:25 pm

Rseding91 wrote: ↑

Fri Nov 22, 2019 1:28 pm

Lubricus wrote: ↑

Fri Nov 22, 2019 1:03 pm

Isn't particles usually some sort of shaders that only lives in the graphics card? And thus use no CPU power nor RAM.

Particles in Factorio can spawn other particles, other entities, smoke, do damage, and so on. They couldn't ever just live in render-only land. Also, you still have to spend CPU time and RAM to tell the GPU what to do so it's never possible to "use no CPU por nor RAM".

You could still ban the real particles (the simple eye-candy-only ones) from the CPU and RAM and let the GPU do some work too.
Factorio is a CPU-heavy game. Don't forget, that there also is a GPU wich often has dedicated RAM and a lot of small compute units wich would be happy to move thousands of particles around each frame. One less system competing for the CPU cache.

This.

If smoke can be re-implemented with a more efficient system, the same can be done for the graphics-only particles that don't spawn other entities (such as blood splatters). This also would make turning them off (like smoke) much easier and ease the burden for lower tier systems.

I guess it's up to the devs whether such an optimization is worth it. Considering the volumes of biters on multiplayer games, I think this would be an excellent improvement for multiplayer speed optimization.

It is absolutely amazing how the Factorio team keeps optimizing the game. Hats off to you!!