The game is very slow when there are many angrystones

[HybridDog]

SuperTux version: latest (40ab22f)
System information: Lubuntu 18.04

Expected behavior

Reasonable frame rate while there are many enemies

Actual behavior

In a level in Oliver W2, many angrystones spawn and SuperTux becomes unplayable (less than 4 FPS).

Here's the (modified) level: level26.stl.zip

Flamegraph created with hotspot for SuperTux version c1be0b7:

Steps to reproduce actual behavior

Download and play the level

[Semphriss]

There are 43 cannons in this level (23 on the right and another 20 divided in sub-sections on the left), each of them firing at a rate of one enemy each 0.3 or 0.4 seconds.

After a quick calculation and 10 seconds of gameplay, you have around 1300 enemies in the level - counting only those badguys, excluding the tilemaps and other already existing objects. All of these need to be updated, animated, and drawn 60 times per second.

Adding to this an optimization behavior of the game: Enemies that are too far away from the camera automatically stop being updated and drawn. If you stay far away of the cannons for a bit and suddenly come back in, you have all the badguys that accumulated at the edge of the updater limit that resume being updated all at once. Considering the wall on the left where badguys are supposed to crash is beyond that limit when you jump towards the right, they will accumulate with each second of gameplay, resulting quickly in tens of thousands of badguys after mere minutes of gameplay.

I don't think it is reasonable to expect the game to deliver such capacity at a framerate of 60 FPS; I'd label this as a level design issue and recommend reducing the amount of enemies at once in a level, especially in such a small zone.

[HybridDog]

I'm not the creator of this level; I'm wondering if it worked well at the time when the author created it.
The frame rate drops below 30 FPS already before 6 s, i.e. when there are less than 1300 enemies. In my opinion the calculations for 1300 enemies should take less than 16 ms. Perhaps each object is compared to all other objects somewhere in the code (which leads to quadratic run time).

[Semphriss]

Perhaps each object is compared to all other objects somewhere in the code (which leads to quadratic run time).

You reminded me of something:
src/video/canvas.cpp, lines 51 to 61:

void
Canvas::render(Renderer& renderer, Filter filter)
{
  // On a regular level, each frame has around 50-250 requests (before
  // batching it was 1000-3000), the sort comparator function is
  // called approximatly 3-7 times for each request.
  std::stable_sort(m_requests.begin(), m_requests.end(),
                   [](const DrawingRequest* r1, const DrawingRequest* r2){
                     return r1->layer < r2->layer;
                   });

Yeah... I have no idea how optimized that sorting algorithm is, but we got our quadratic run time 😄

[Mathnerd314]

I think sorting graphics layers is relatively fast; the slow part is likely the collision detection code.

[Grumbel]

There are two slow parts, collision detection is certainly one of them, but the other is not drawing in batches. OpenGL only allows you around 1000 draw calls per frame if you want performance, and preferably you'd reduce that to a couple of hundred at most. In SuperTux every sprite has it's own texture which requires a separate draw call. In cases of particle effects or just adding large objects, that can quickly get out of hand. The tilemap itself should already be somewhat batched, but I am sure there is room for further improvement.

Another issue is that everything in SuperTux is a transparent texture due to the anti-aliased edges, which requires to draw them in order, this makes it difficult to reorder and group the draw calls.

The quickest way to fix this is to simply not design levels with crazy object numbers (or hard code an upper limit in the editor). Adding a texture packer, so that multiple sprites share the same big texture, would be the other alternative.

[Mathnerd314]

Is there the possibility in OpenGL to draw the same sprite multiple times with a single call? Then we could at least batch together drawing all instances of the same badguy, which would handle the level here.

[Grumbel]

Problem is that "same sprite" is often still a different texture, e.g. when animated and the individual frames are different images. Throwing some code int Canvas::render() that takes consecutive drawing requests and merges them into a single one when they use the same textures might however still be worth a try.

[HybridDog]

I have created a flame graph (see top comment) and it looks like rendering is not the bottleneck.

[Mathnerd314]

It isn't interactive so I can only guess at the numbers, but it looks something like:

• 10% rendering
• 45% collision
• 22% badguy update
• 11% player update
• 11% some other kind of update (name not readable)

So yeah, mostly collision.