New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Optimize quadtree rebalancing #551

Open
parasyte opened this Issue Aug 13, 2014 · 6 comments

Comments

2 participants
@parasyte
Member

parasyte commented Aug 13, 2014

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...

@parasyte parasyte added this to the 1.1.1 milestone Aug 13, 2014

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 13, 2014

Member

awesome :)

Member

obiot commented Aug 13, 2014

awesome :)

parasyte referenced this issue Aug 15, 2014

[#544] new faster (and working) quadtree implementation based on Tino…
… Hausmann library

this one can also be swapped with his spatial hash algorithm as they
both share the same API :)

@parasyte parasyte modified the milestones: Future, 1.1.1 Oct 14, 2014

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Mar 17, 2016

Member

+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 :):):)

Member

obiot commented Mar 17, 2016

+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 added a commit that referenced this issue Jun 22, 2016

[#551] first attempt at adding a simple remove function for the quadtree
pretty unstable/unstested for now; the framerate just goes horribly low
after a few seconds, like if objects were still being added to the world
container or quadtree (pretty difficult to debug actually).

@obiot obiot modified the milestones: 4.0.0, Future Jun 22, 2016

obiot added a commit that referenced this issue Jun 22, 2016

[#551] properly add/remove objects dynamically
works already better, and obviously solve the previous issue

obiot added a commit that referenced this issue Jun 23, 2016

[#551] fixed world objects not being properly added to the quadtree o…
…n level loading

still needs some improvements (redudant code), but I'm keeping it this
way for now, so that I can properly debug the remove function.

obiot added a commit that referenced this issue Jun 23, 2016

[#551] fix the hasChildren function, and optimize test removal
still have some issues on level changing, due to misplaced quadtree
cleaning/reset/adding/removal
@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Jun 23, 2016

Member

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.

Member

obiot commented Jun 23, 2016

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 obiot modified the milestones: Future, 4.0.0 Aug 2, 2016

obiot added a commit that referenced this issue Aug 2, 2016

[#551] added a remove function
manually backporting this one from branch #551.
@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 2, 2016

Member

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

Member

obiot commented Aug 2, 2016

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

@parasyte

This comment has been minimized.

Show comment
Hide comment
@parasyte

parasyte Aug 2, 2016

Member

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

Member

parasyte commented Aug 2, 2016

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

@obiot

This comment has been minimized.

Show comment
Hide comment
@obiot

obiot Aug 2, 2016

Member

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.

Member

obiot commented Aug 2, 2016

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.

@obiot obiot added this to To Do (Core) in Roadmap Dec 4, 2017

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment