search

melonjs / melonJS

a fresh, modern & lightweight HTML5 game engine
https://melonjs.org
MIT License
5.9k stars 645 forks source link

Optimize quadtree rebalancing #551

Open parasyte opened 10 years ago

parasyte commented 10 years ago

From discussion in #544: The quadtree is cleared and rebuilt on each frame. It can be optimized by allowing the objects to reposition themselves within the tree as they move about the world. Performance gain will be minimal, but may impact mobile more than desktop...

obiot commented 10 years ago

awesome :)

obiot commented 8 years ago

+1 for that one that felt behind ! we should probably start by adding a test unit for the quadtree implementation. That will help ensuring we don't break everything then :):):)

obiot commented 8 years ago

i just realized i completely overlooked this thing (although yes it was written in the initial message of this ticket) . Remove an item is actually the easy part, but to make it work, the whole tree also needs to be "re-validated" every time an object is moving, which makes me wonder if this is not almost the same (in terms of required cpu-cycle) than just rebuild the tree from scratch on every frame like we do now.

basically it could be something like : check if every object of the tree are still i their initial node (or add a way for an object to notify the quadtree it changed position), if not, remove the object, clean the node/sub-node if necessary, and the re-insert it.

obiot commented 8 years ago

backported the changes from the #551 branch to master, and changing the milestone to "future" (4.1.0?)

parasyte commented 8 years ago

FWIW, you don't have to rebalance the tree for removals, just adds.

obiot commented 8 years ago

yes indeed it should be something like this. To be honest the biggest part was to add this "remove" function, but i just don't have the time (if we want to have a 4.0 version released this year) to fully debug it (although it seems to be working pretty well now) and add the missing part of this ticket.