Efficiently positioning large numbers of sprites, overhead of calling into compiled code.

:information_source: Attention Topic was automatically imported from the old Question2Answer platform.
:bust_in_silhouette: Asked By steely
:warning: Old Version Published before Godot 3 was released.

I’m working on a project that includes hundreds of tiny moving sprites, on top of a background containing 1250 (25x50) visible background tiles. This does not seem like an unusual graphical load for a small 2D game.

All the moving sprites call set_process(true), and the code that updates their position runs in the _process() function and uses set_pos(). I previously used a simple linear function for position interpolation, but I thought a cubic Bezier curve would look much better. I was correct that it looks a lot better, but it came with a massive performance hit: with 700 moving sprites, the frame rate fell from a tolerable ~50+ fps to an unacceptable ~15 fps.

Is this purely the result of slow arithmetic in GDScript/Python (which GDScript is modeled upon)? This is a fairly complex operation that takes ~30 arithmetic steps, which I would expect to be called up to 50,000 times per second. Caching, LUTs, fast approximation, etc. would probably speed it up dramatically, but I’d like to know if there’s an easier solution.

Would it be worthwhile to handle the Bezier calculation with a C++ function? What is the overhead of making such a call? Is the overhead amortized by making many thousands of calls a second?

Am I doing something wrong by calling set_pos() every frame for every moving sprite? I like the direct control it gives me, but is there a way to offload the position calculations to the Godot engine in a way that would be faster?

1,500,000 operations per second sounds like a lot for any scripting language to be honest. There’s probably room for optimization in the code you’re using, before looking at moving it to C++.

Akien | 2016-06-23 14:37

It might be the rendering costing you a lot of process time, not just the GDScript calculations. You could roughly test it by running it with all your sprites hidden or with a low viewport resolution.

rgrams | 2016-06-23 19:40

@rgrams I ran my prototype at 55 fps with 700 motes and the linear interpolation. Then I replaced the linear version with the Bezier version (no other changes), and the prototype ran at 15 fps with 700 motes.

steely | 2016-06-23 19:54

@Aklen There is certainly a lot of room for optimization everywhere, but I want to know what other options there are so I don’t waste time doing pointless optimization. Speedups could come from switching to a quadratic Bezier, using a big lookup table (5880 elements? ouch), or using a faster but more-complicated-to-write incremental Bezier algorithm.

steely | 2016-06-23 20:35

:bust_in_silhouette: Reply From: Hinsbart

Would it be worthwhile to handle the Bezier calculation with a C++ function? What is the overhead of making such a call? Is the overhead amortized by making many thousands of calls a second?

Afaik, there’s no overhead when using native c++ functions (Well, there’s a bit of overhead involved when you call a function from gdscript instead of native code, but that’s true for every single function in the engine, so don’t worry about that).

I’m trying to get a feel for whether it would be worth it to use C++. I know C and C++ better than anything Godot related, but calling native C++ from within the engine is a risky (apparently undocumented) unknown for me.

steely | 2016-06-23 19:59

:bust_in_silhouette: Reply From: Zylann

How are your sprites moving? Do you really need a Bezier curve?
You could move them incrementally instead of evaluating a curve every frame.

GDScript is very slow, slower than it should be IMO (even though vectors and matrix are built-in). The usual way to get rid of a performance bottleneck would be to move that in C++, and using Data-Oriented-Design could speed it up even more. It depends on how many things you want to simulate.

If the sprites are only visual (i.e their position doesn’t matters for game logic/physics), you could move them in a vertex shader if you can get the curve in a function / texture lookup.

Thanks, I’m trying to determine what my options are. The sprite position essentially has three components:

  1. Which of the background tiles (hexes) contains the sprite. This is the only mechanically salient part.
  2. Interpolation of position as the sprite transfers from one tile to an adjacent one.
  3. An offset so that multiple sprites in the same tile don’t overlap.

It’s a very simple underlying simulation, the slowdown is almost entirely on the visual side. I don’t know much about shaders, how exactly would that work? Would it help if there are a finite number of paths that need to be interpolated? 36 for all combinations of hex directions (49 if I count remaining stationary as a direction). Would I still be able to do fine adjustments (e.g. the offset nudges) if I’m offloading work to the GPU?

steely | 2016-06-23 20:28

No, in that case I don’t think the GPU can be of help.
So, sprites move according to which tiles they are on. Are they all moving all the time?
Instead of a Bezier curve, you could try cubic interpolation if you know at advance the two next tiles your sprite will move to.

Even cheaper: you can use two levels of linear interpolation: first one as you did, and a second one to smooth it. This will cause a slight delay but you get cheap smooth movements :slight_smile:

There are lots of sprites, so you can cheat on the animation. The human eye is not performant enough to spot innacuracies :stuck_out_tongue:

Zylann | 2016-06-23 20:45

I realized during our discussion in the comments here that I was making unnecessary calls to convert from grid coordinates to pixel coordinates every frame. I pulled that calculation out to the underlying tick function of the simulation (~once per second) and cached it within each sprite. Combined with a reduction from a cubic to a quadratic Bezier and some math tweaks, I’ve got it running even faster than my old linear interpolation.

steely | 2016-06-23 21:31

:bust_in_silhouette: Reply From: steely

It turns out that a major portion of my bottleneck was not the simple math operations (even if there are a lot of them), but calling a function of another object hundreds of times per frame to perform a conversion from grid coordinates to screen coordinates. Performing this function call far less frequently and caching the result in the mean time provided me with a dramatic speed increase.

Glad you found the bottleneck :slight_smile:
I was about to send you this project to show you a simple smoothing method: http://zylannprods.fr/dl/godot/LotsOfSprites.zip

Zylann | 2016-06-23 21:44