Thousend Objects Performance Problems

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By LaCocoRoco

Good Evening, i asking for some guidance regarding a problem of mine.
Since some time i am trying differend approaches for performance optimization.
The target is to move thousends of objects independently.

Tutorials:
Animating thousands of fish with MultiMeshInstance
Optimization using MultiMeshes
Using multiple threads

Approaches:
First i simply tried nodes, but that is out of the question.
Then i started working with multimesh and custom shaders.
I also tested difference approaches with multi threading.

At last i update the Multimesh2d via “set_as_bulk_array” at once and change the corresponding Transforms2D of the instances individually in an “PoolRealArray”. I only change 10000 objects (Move X & Y 1 Pixel) in the _process() and have 120fps. When i do this for 40000 objects it drops to 30fps. In conclusion i removed updating the multimesh, only loop through 40000 elements in _process() and i realized this is my bottleneck. I tried to fix this with multithreading without success.

Reason:
I im thrilled by games like Factorio, Shapes.io, Mindustry, etc. There has to been moved and checked for thousends of collision of elements every frame. But now i asking myself how this is possible when i get problems by simply looping through thousend elements per frame. I excluded the cause of “missing to hide something” because the whole world and every single element has permanently to been processed. So there is no real “frustum culling” fix for calculations i think.

Yours Andreas

:bust_in_silhouette: Reply From: archeron

How about only updating half of the objects every second frame? Or a quarter of them every fourth frame? This way you reduce the work.

As for “how can we check for tens of thousands of collisions per frame”: First of all, remember that using GDScript incurs a penalty because it’s an interpreted language. If you wrote the same code in C++ (maybe as a GDNative “script”), chances are you would get better performance.

Second, if you know your game has to check for tens of thousands of collisions between objects, you’ll most likely arrange your data structures in a way that will make collision checking trivial (but might make other things more difficult). Naive collision checking runs in O(n^2), because you check every object against all the others. So the first order of business would be to see that we don’t do 10’000 * 10’000 collision checks. If I had to write a game like that from scratch (without a pre-existing game engine), I’d most likely subdivide my game into a grid, record each grid’s contents and then do collision checks per grid, which should turn out to yield a smaller total.

But: I don’t actually see any large number of collision checks being performed from trailers of games such as Factorio (which I haven’t played, so please forgive me if I get the game mechanics totally wrong). Instead it looks like the main mechanic of the game is that each object is transported along by a conveyor belt, taken off the belt by a robot arm and put on another belt or in a factory machine. This is completely different from the collision check problem because we know exactly at which points objects will interact with each other. So whenever we put an object on a conveyor belt, we can add it to a list of objects that will need to be processed at a given future time by a given robot arm (for example), and we know the exact time because the conveyor belt (seems to) run with a fixed, known speed.

So I’d assume that the answer to the question “how do they process so many objects at once” is that they don’t: These games probably know exactly which objects will need to be processed in which frames by which robot arms, which means that each individual frame doesn’t have to process tens of thousands of objects - it will only have to process the objects that are scheduled to be processed in that frame (to be put on a new conveyor belt, unloaded from a train, but into a factory machine etc).

So I’m back to my original suggestion: Don’t process every single object every single frame.

P.S:

You write that there is “no real fustrum culling fix for calculations”, but I think that’s wrong. It seems to me that most of what happens in the game is deterministic (there might be fun random stuff like conveyor belt malfunctions that the player needs to fix etc, but these things only need to appear random to the player - they might be planned events from the perspective of the game). So it should be possible for each object to calculate it’s state and position for any given time - including when and where it will reappear on the screen. So the game could stop updating “unimportant” stuff like an objects game world position etc as long as it’s not visible. The game would only have to process interactions with other objects, and as I’ve said before, it’s known in advance when these happen, and which objects interact. Also, these interactions are much less frequent than game position updates. So you can save a large amount of processing power by not having to update game world positions dozens of times per second for off-screen objects.

First, thank you for the fast answer!

That is a very interessting point of view to fix the suggested problem i did not consider! I already rejected the concept of using the buildin collision detection. As you mentioned it is predetermed where the elements will be transported. The main topic of my concern was the point where several materials interact with another. I do not have the interest to make any copy of a game because they are all good as they are, but the basic concept of moving things is the way to go. I think you got a realy good point here. Probably i should stop thinking about transporting and interact elements per tile or frame and think about defining the path to the point where elements start to interact and only then recalculate information. This should remove a big overheat. The part i wrote about frustum culling was specified to the fact that on some point the elements always have to interact with each other even if they are not on screen. As i think more and more about it, even that could be predetermed as you already suggested. Yes, this will probably fix the problem. I will start from skretch with this as basic concept. I also thought about moving to GDNative, but for the moment i realize that i still missing knowledge regarding the engine or other stuff and GDNative probably would complicate this even more. If the concept is good and it works as expected i probably will redo it in GDNative. The chance is high at this point Godot 4 is already released. Also i do not know how effictive realy is GDNative. I will and i do not want to reach the highs of Factorio, but i think it sets a good example.

Thank you for the help!

LaCocoRoco | 2021-03-05 09:28

You’re very welcome.

If I were you, I’d think about how to actually simulate the workings of the factory before I started thinking about the visual representation (e.g. what Nodes to use etc). It’s probably easier to design an efficient simulation of a factory if you’re not constrained by thoughts about it’s visual appearance. For example, even locations are not important for the simulation, as long as the game knows which objects are connected to which others and in which direction the “input” flows. So you can completely separate the simulation of the factory from it’s visual representation.

I agree that staying with GDScript is the best way to go. GDNative does give you a performance boost, but only by a constant factor, and usually performance issues arise not because your language is too slow by a constant factor but because the algorithms you use aren’t ideal. Moving to GDNative would be the last resort (and cut your productivity, since GDScript is much easier to write and test than C++).

Good luck with your project!

archeron | 2021-03-05 09:57