Friday Facts #322 - New Particle system

Regular reports on Factorio development.
Tynach
Inserter
Inserter
Posts: 31
Joined: Sun Aug 21, 2016 9:22 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Tynach »

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.

User avatar
Philip017
Filter Inserter
Filter Inserter
Posts: 355
Joined: Thu Sep 01, 2016 11:21 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Philip017 »

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.

tomvalk25
Burner Inserter
Burner Inserter
Posts: 19
Joined: Tue Apr 25, 2017 10:54 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by tomvalk25 »

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

vorax
Burner Inserter
Burner Inserter
Posts: 7
Joined: Sat Dec 31, 2016 4:51 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by vorax »

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.

tomvalk25
Burner Inserter
Burner Inserter
Posts: 19
Joined: Tue Apr 25, 2017 10:54 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by tomvalk25 »

@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 :oops:
Maybe that is also the reason why I cannot figure out the circuit network :roll:

Tynach
Inserter
Inserter
Posts: 31
Joined: Sun Aug 21, 2016 9:22 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Tynach »

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.

User avatar
MEOWMI
Filter Inserter
Filter Inserter
Posts: 307
Joined: Wed May 22, 2019 12:21 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by MEOWMI »

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.

FasterJump
Fast Inserter
Fast Inserter
Posts: 192
Joined: Sat Jul 09, 2016 11:43 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by FasterJump »

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?

vorax
Burner Inserter
Burner Inserter
Posts: 7
Joined: Sat Dec 31, 2016 4:51 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by vorax »

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.

Tynach
Inserter
Inserter
Posts: 31
Joined: Sun Aug 21, 2016 9:22 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Tynach »

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.

ColonelSandersLite
Fast Inserter
Fast Inserter
Posts: 208
Joined: Tue Apr 24, 2018 5:42 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by ColonelSandersLite »

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?

Pi-C
Smart Inserter
Smart Inserter
Posts: 1639
Joined: Sun Oct 14, 2018 8:13 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by Pi-C »

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?
blueinserter+splitter.png
blueinserter+splitter.png (104.82 KiB) Viewed 7011 times
A good mod deserves a good changelog. Here's a tutorial (WIP) about Factorio's way too strict changelog syntax!

conn11
Filter Inserter
Filter Inserter
Posts: 385
Joined: Wed Sep 14, 2016 5:02 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by conn11 »

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.

uio
Burner Inserter
Burner Inserter
Posts: 12
Joined: Sat Mar 05, 2016 5:36 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by uio »

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.

User avatar
Filter62
Long Handed Inserter
Long Handed Inserter
Posts: 58
Joined: Mon Sep 04, 2017 6:54 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Filter62 »

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

bobucles
Smart Inserter
Smart Inserter
Posts: 1669
Joined: Wed Jun 10, 2015 10:37 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by bobucles »

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

henke37
Long Handed Inserter
Long Handed Inserter
Posts: 91
Joined: Mon Jul 18, 2016 5:43 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by henke37 »

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?

User avatar
Oktokolo
Filter Inserter
Filter Inserter
Posts: 883
Joined: Wed Jul 12, 2017 5:45 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Oktokolo »

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.

Ultros
Fast Inserter
Fast Inserter
Posts: 129
Joined: Thu Apr 04, 2019 4:25 pm
Contact:

Re: Friday Facts #322 - New Particle system

Post by Ultros »

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.

lacika2000
Long Handed Inserter
Long Handed Inserter
Posts: 64
Joined: Sat Jul 07, 2018 7:25 am
Contact:

Re: Friday Facts #322 - New Particle system

Post by lacika2000 »

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

Post Reply

Return to β€œNews”