Optimize me.Container.update with QuadTree

[parasyte]

Right now the world container iterates all of its children, then performs a rectangle overlap check to determine whether its in the viewport (thus determining if it should be updated) We can optimize this selection logic by collecting a list of entities potentially within the viewport using the QuadTree. Thereby allowing the container to iterate only a subset of its children (especially on large maps).

Second, the alwaysUpdate children might have to be placed in a separate child-list that is always iterated and updated. This is pretty similar to #191, actually. Which will be a matter of managing child placement within different lists.

[obiot]

did we actually properly tested several level of containers with the quadtree ? (i'm wondering how is this working, as so far, 99% of the stuff I saw were not using containers)

[parasyte]

Nested Containers now work with QuadTree thanks to @agmcleod in #634

[agmcleod]

After learning a bit on quad trees in that issue, going to try and take a crack at this :)

[agmcleod]

So with this I wonder. Do we not invoke the update on me.game.world? Instead do we from the game.js update get a list of containers/objects that can update, and simply iterate through those?

[agmcleod]

@obiot @parasyte poke

[parasyte]

@agmcleod I've been meditating on this since you mentioned it two weeks ago, and I honestly have nothing new to add. The basic concept was really straight forward; me.game.update would get a list of entities in the viewport using quadtree, and would iterate that list itself. However, it raises a concern about updating containers...

The containers aren't added to the quadtree:

melonJS/src/physics/quadtree.js

Lines 171 to 174 in c629277

	if (child instanceof me.Container) {
	// recursivly insert childs
	this.insertContainer(child);
	} else {

So they would not receive updates by doing this. And even if containers were retrieved from quadtree, it would force updates on children that are potentially outside of the viewport.

The question then is, do we need to update containers at all? ParticleContainer seems to do one thing that is specialized:

melonJS/src/particles/particlecontainer.js

Lines 78 to 80 in 75f93f4

	if (!particle.update(dt)) {
	this.removeChildNow(particle);
	}

But that's really all I can think of...

[agmcleod]

I feel like containers should have an update of sorts. You should be able to translate and move them around like in any scene graph

[parasyte]

Translation happens during draw. But yeah, it's kind of the same problems there; we want to iterate only the list of visible items.

[agmcleod]

Hmm, i think the other problem is, what if someone uses the container's update, expecting it to work? It's an object you're adding to the scene, therefore it should update. I feel like it would just be unexpected behaviour.

[agmcleod]

So i'm starting to back track on getting a list of stuff in the viewport, and updating those. In order to get that list, we will iterate through the children anyways. Why not do that in the update to begin with, and check each one if (QuadTree.has(rect)) invoke the object's update.

[obiot]

I've been thinking about this one again, especially since we exactly do that for pointer detection, and also since containers are now added into the quadtree.

However, my only worry is on objects with the alwaysUpdate flag on, as if not in (or overlaping) the container rect, the quadtree most likely won't include them in the list.

[parasyte]

Good old alwaysUpdate! What a nightmare. Maybe it's time to start thinking about #396 in the context of updates. I can see a case where alwaysUpdate objects get put into their own array for iteration, and everything else uses quadTree. (Work in #396 will be responsible for queueing these special-case objects.)

Now to prevent double-updates...