Experimental object collision and positions handling improvements

[4ian]

This enables RuntimeObject positions to be managed by a spatial data structure (a "RTree", called RBush too here), allowing to speed up collision/separate objects/raycast on a large number of objects.

This is still highly experimental, and a large PR. I want mainly to ensure that there is no regression in terms of behaviors in games, and no large performance regression too.

Performance benchmarks (average frame time):

• [x] Collisions benchmark when not hovering the ~1200 boxes with the ~1200 cursor objects:

  • Old version: 120ms
  • New RTree: 2ms

• [x] SeparateObject

  • Old version: 250ms
  • New Naive: 69ms
  • New Rtree: 25ms

• [x] Distance test (Distance between objects benchmark)

  • Old: 52ms
  • New Naive: 66ms
  • New Rtree: 12ms

• [x] "Collisions with creation and deletion benchmark"

  • Old: 30ms
  • New Naive: 38ms
  • New RTree: 13ms

• [x] "Cursor on object benchmark"

  • [x] When everything moves:
    • Old: 40ms
    • New Naive: 32ms
    • New RTree: 52ms (not that bad considering that this is the worst case scenario for the RTree)
  • [x] When nothing moves:
    • Old: 20ms
    • RTree: 16ms

• [ ] Raycast benchmark:

  • Old: 50ms
  • New Naive: 85ms
  • New RTree: 65ms

• [x] "Point inside object benchmark":

  • Old: >200ms
  • New Naive: 82ms
  • New RTree: 56ms

• markObjectAsDirty should be called also when setWidth/setHeight is called for most objects (much like this.hitBoxesDirty).

Todos:

• [x] See if we need to do right now an implementation where we can disable the RTree for some objects
  • [ ] If yes, surface in the UI and in events the ability to enable to disable the usage of a RTree to store positions of each object.

Clean-up todos:

• [ ] Old implementation of collisionTest/separateObjects/distanceTest/cursorOnObject/CollisionPoint/raycast
  • Clean related object functions: separateFromObjectsList, cursorOnObject, isCollidingWithPoint, raycastTest
  • Clean inputtools, objecttools: _cursorIsOnObject
  • Mark twoListsTest deprecated
• [ ] Mark #1297 fixed

Future:

• Adapt the Draggable behavior?
  • [ ] Mark #1298 fixed
• Surface in the Profiler UI the counters and times spent in the game engine like gdjs.ObjectPositionsManager

As GDevelop is a generic game engine, there can be cases where the usage of an RTree can be actually too costly and slow down the game compared to not using one. We would probably need to expose this is a setting somewhere in the IDE.

Trying this

Changes in this PR should be invisible to the user. You probably won't notice even difference in your game, unless you're in the case where the RTree can be speeding up things for you (lots of collision check between lots of objects) or slowing this down (few checks but lots of objects moving).

For now, I want to ensure the stability of this - there is room for optimisation later. In the worst case, this could be disabled by default and enabled in the UI on a case by case basis. For now, it's activated for all objects.

To help me, you can simply download the GDevelop versions below. They are beta 88 with this PR applied:

• Windows
• macOS
• Linux

⚠️ I recommend not to use this version for making your game. Stay on the latest stable version (beta 88), just install this one to try your game and see how it behaves.

Once you have this version, try to open your game and launch it:

• If your game is visibly broken, check if you can send me the part that is broken with a good description of what's wrong.
• If it's working properly, let me know if you find any performance difference (large improvement or regression). You may use the GDevelop profiler, running it for a few seconds and then look at the average time to render a frame in your game - though this may be hard to compare as this depends a lot on other factors.

[rishabhabhani]

A few questions I'd like to ask about this. Is RTree a structure that runs on a separate thread or the same as the others. If it does run on another, is it designed with the objectives in mind or be extensible?

[4ian]

JavaScript is single threaded, so runs on the same thread as the rest. Web-workers or wasm could be used to maybe have it running on another thread, but it was not a goal in this implementation (there is more complexity to achieve this).

[Silver-Streak]

@4ian has the efforts around this been dropped? It seems like your checklist is mostly complete, and I'm sure people would love collision performance improvements. (Especially with Davy's other outstanding PRs)