Light obstacles persist when the object is deleted

[Bouh]

Describe the bug

@HarsimranVirk Light obstacles persist when the object is deleted too fast.

To Reproduce

Project example.zip

In the project example, drag&drop fast an object in collision with another one for deleting them, the Light obstacle isn't deleted. (Might be a failure of the light update function?) In the first part of the video everything works, in the second (+20sc) the last cube is deleted correctly but the light obstacle is still present.

https://user-images.githubusercontent.com/1670670/131223119-2ca043ac-7852-41e6-ab85-6a09b2c1dba4.mp4

Other details

• B115 and all builds before 26 May, 2021
• Original forum bug report

[HarsimranVirk]

@4ian @Bouh I've tried testing this for some time, I figured out that the problem lies with the LightsObstacleManager, it isn't removing the object. My best guess here is with the guards that have been put up (this.activated(), this._registeredInManager), as it's unlikely that there will be any problems with the underlying impl of R-Tree.

EDIT: https://github.com/4ian/GDevelop/blob/413fbc529ec786fe3b4f1dbf4284158546068f5f/Extensions/Lighting/lightobstacleruntimebehavior.ts#L55-L79 After some console logging, I figured that nearbyObstacles contains the deleted objects as well. This should mean we have some problems in deleting the objects from the underlying r-tree.

[Silver-Streak]

Just to chime in, I wouldn't be surprised if this is related to object deletion and behaviors in general.

There have been reports over the last year or so about deleted platforms having "ghost" collision box after deletion. Exact same type of perceived behavior we're seeing here, where an object's visuals are deleted, but it's behaviors remain active in the scene as if it was still there.

[Silver-Streak]

Here's an issue that has similar issues, but with the platform behavior: https://github.com/4ian/GDevelop/issues/1463

[AlexandreSi]

After investigating into this issue, I seem to have found the beginning of a cause:

• At each step, if the sprite is moved, we remove and add the obstacle behavior from the RTree
• Sometimes, it looks like the removal fails and we end up with nodes in the RTree with duplicates of the behavior.
  • I don't know why, but i have this feeling:
  • 2 instructions concurrently remove and add the behaviour
  • the first removes the behaviour
  • the second tries to remove the behaviour but doesn't find it
  • then, both add the behaviour
• So, when the object is destroyed, only one duplicate (the first in the list, due to https://github.com/4ian/GDevelop/blob/master/GDJS/Runtime/libs/rbush.js#L460) of its behavior is removed
  • the behavior still has an owner but the instance is not in the RuntimeScene instances anymore

[AlexandreSi]

We could:

• Either remove all instances from behaviours from the RTree and not stop on the first
• Either return true or false from rbush.remove if found or not. And add the behaviour back if true.

[AlexandreSi]

To reproduce the bug, you can download the project and do as the video shows : drag out of the window and back to it a few times and then make it collide with the big square.

https://user-images.githubusercontent.com/32449369/137508379-fa077473-cf6c-4eb2-bdf1-bc7a251d3229.mov

[AlexandreSi]

And as the platform behavior uses an RTree to manage the platforms, I guess solving this should solve #1463.

[4ian]

Super interesting investigation!

Sometimes, it looks like the removal fails and we end up with nodes in the RTree with duplicates of the behavior.

Let's see if we can find/explain exactly how this is happening! This is definitely an issue and fixing the root cause might fix more than this problem :)

[AlexandreSi]

Ok so i'm clear now on the issue, it is not a concurrency issue:

The RTree organizes the items in nodes, each node having its bounding box computed from its items bounding boxes. So here is what happens with this game.

If you want to move the westest square out of the node 1's bounding box, the function contains uses the node's bounding box to determine if the new position the square is inside the bounding box. But it uses the bounding boxes have not been updated with the square new position. So the remove function just goes directly out of the while loop and removes nothing.

But I am not sure that this is the same issue that causes #1463.

So, now, what would be a good solution to this?

• We could add a tolerance in the bounding boxes comparison, but it is hard to know what is a good value for this matter (1px ? 10px ? etc.)
• We could add a remove function that does not take into account bound boxes but we lose the efficiency of the RTree
• We could change the remove function so that if the function as is does not find anything to remove, it will make a second pass ignoring bounding boxes

Do you imagine another solution?

[AlexandreSi]

We could, when calling the remove function, give a tolerance corresponding to the movement of the square so that the search is more or less flexible on the bounding box comparison