Implement quadtrees for general use in game engine #358

Open
nwinter opened this Issue Feb 11, 2014 · 10 comments

Comments

Projects
None yet
3 participants
@nwinter
Contributor

nwinter commented Feb 11, 2014

We're running some O(m*n) algorithm performance bottlenecks where we have to compare all Thangs of one type against all Thangs of another type which may be nearby, and doing that with two arrays of Thangs isn't efficient since we're ignoring distance information. It gets even worse when we have to recalculate distances for each comparison, and when we need to include line of sight, then we're doing raycasting, and raycasting is terrifically slow. Good examples include determining whether Collectors can collect Collectables and which friends and enemies a Thang can see and hear.

It would be better to have a general quadtree implementation we could put Thangs in so that various Systems could perform faster. Quadtrees are a form of binary space partitioning and I'm sure many JS or even CoffeeScript implementations exist that we could adapt to our Thangs.

@nwinter nwinter added the enhancement label Feb 11, 2014

@nicholascgilpin

This comment has been minimized.

Show comment
Hide comment
@nicholascgilpin

nicholascgilpin Mar 11, 2014

Hey, I'm a new member looking to be an Archmage and this looks like a fun project. Is anyone already working on this?

Hey, I'm a new member looking to be an Archmage and this looks like a fun project. Is anyone already working on this?

@nwinter

This comment has been minimized.

Show comment
Hide comment
@nwinter

nwinter Mar 11, 2014

Contributor

Nope! Want to take a crack at it? It would actually be really amazing to have soon, as we're limited in the levels we can build by the current implementations.

Contributor

nwinter commented Mar 11, 2014

Nope! Want to take a crack at it? It would actually be really amazing to have soon, as we're limited in the levels we can build by the current implementations.

@nicholascgilpin

This comment has been minimized.

Show comment
Hide comment
@nicholascgilpin

nicholascgilpin Mar 23, 2014

Update: Unfortunately my school life has suddenly gotten very busy so I won't be able to contribute very much. I'm currently working off this example: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/

Update: Unfortunately my school life has suddenly gotten very busy so I won't be able to contribute very much. I'm currently working off this example: http://www.mikechambers.com/blog/2011/03/21/javascript-quadtree-implementation/

@nwinter

This comment has been minimized.

Show comment
Hide comment
@nwinter

nwinter Mar 23, 2014

Contributor

That's understandable–school can take a lot of life force. If you can post any progress you do make, it'll be helpful.

Contributor

nwinter commented Mar 23, 2014

That's understandable–school can take a lot of life force. If you can post any progress you do make, it'll be helpful.

@ItsLastDay

This comment has been minimized.

Show comment
Hide comment
@ItsLastDay

ItsLastDay Mar 29, 2014

Contributor

I'll look into this issue this weekend and see what I can do. Already heard couple of times about quadtrees, though never actually had a chance to implement it.

Contributor

ItsLastDay commented Mar 29, 2014

I'll look into this issue this weekend and see what I can do. Already heard couple of times about quadtrees, though never actually had a chance to implement it.

@ItsLastDay

This comment has been minimized.

Show comment
Hide comment
@ItsLastDay

ItsLastDay Mar 30, 2014

Contributor

That's what I've worked out about quadtree:

  1. Quadtree is a tree, where every node has exactly 0 or 4 children. Each node corresponds to rectangular part of some plane (root = the whole plane). Children have roughly 1/4 of father's part.
  2. Data points are stored (in most cases) in leaf nodes. There is a treshold - how many points a node can store. If the number of points exceeds it, we divide the node into 4 parts and transfer it's points to children.
  3. We can store AABB's inside the tree. It's mostly the same, but if some AABB does not completely fall to some node's child rectangle, then it is stored in that node (the only case when we store data in internal nodes).
  4. We can perform a rectangular query on quadtree, which will give us all rectangles that may intersect with our's (~they lie in one node, though that's not very accurate).
  5. If objects are moving, we must delete and reinsert them from a quadtree (if we don't want to just rebuild the whole tree every frame).

I've read 3 implementations and got the drift, going to write some code!
UPD: this could take a while, since I'm studying hard at university atm.

Contributor

ItsLastDay commented Mar 30, 2014

That's what I've worked out about quadtree:

  1. Quadtree is a tree, where every node has exactly 0 or 4 children. Each node corresponds to rectangular part of some plane (root = the whole plane). Children have roughly 1/4 of father's part.
  2. Data points are stored (in most cases) in leaf nodes. There is a treshold - how many points a node can store. If the number of points exceeds it, we divide the node into 4 parts and transfer it's points to children.
  3. We can store AABB's inside the tree. It's mostly the same, but if some AABB does not completely fall to some node's child rectangle, then it is stored in that node (the only case when we store data in internal nodes).
  4. We can perform a rectangular query on quadtree, which will give us all rectangles that may intersect with our's (~they lie in one node, though that's not very accurate).
  5. If objects are moving, we must delete and reinsert them from a quadtree (if we don't want to just rebuild the whole tree every frame).

I've read 3 implementations and got the drift, going to write some code!
UPD: this could take a while, since I'm studying hard at university atm.

@nwinter

This comment has been minimized.

Show comment
Hide comment
@nwinter

nwinter Apr 12, 2014

Contributor

@ItsLastDay Let me know if you make any progress on the quadtrees. Are you working on it in GitHub somewhere?

Contributor

nwinter commented Apr 12, 2014

@ItsLastDay Let me know if you make any progress on the quadtrees. Are you working on it in GitHub somewhere?

@ItsLastDay

This comment has been minimized.

Show comment
Hide comment
@ItsLastDay

ItsLastDay Apr 12, 2014

Contributor

@nwinter Currently I have only a concept of how I want to implement it, but later I'll do that on GitHub.

Contributor

ItsLastDay commented Apr 12, 2014

@nwinter Currently I have only a concept of how I want to implement it, but later I'll do that on GitHub.

@nwinter

This comment has been minimized.

Show comment
Hide comment
@nwinter

nwinter Feb 11, 2015

Contributor

This is now a student project for http://cdl.rosedu.org/

Contributor

nwinter commented Feb 11, 2015

This is now a student project for http://cdl.rosedu.org/

@nwinter

This comment has been minimized.

Show comment
Hide comment
@nwinter

nwinter Mar 2, 2015

Contributor

Here are some steps I'd take when doing this one:

  1. Get the dev environment set up. Make sure to download the database dump.
  2. Add a placeholder quadtree.coffee class in app/lib/world. You can look at Vector.coffee for an idea of how to format it.
  3. In the level editor for, say, Sarven Treasure, open the Inventory System and try to require the QuadTree class to make sure that your import is set up correctly.
  4. Implement the APIs you need to interface between the QuadTree and the Systems' registries, but just using a simple array to start off. Make it so there are two types of registries: normal arrays, and also quadtree registries.
  5. Make sure existing levels still work: collectors can collect coins and hearers can hear sayers.
  6. Create a test level where it takes a lot of CPU to determine what Collects Thangs are collecting what Collectable Thangs (so tons of coins, tons of Collectors).
  7. Record performance stats for the test level in a controlled run.
  8. Implement the QuadTree APIs to make it so that it's not an O(n * m) operation.
  9. Make sure the results of the test level are the same.
  10. Record performance stats for the test level now using quadtrees.
  11. Use the Chrome profiler on the web worker thread when running the level to see where the code is still slow, and optimize it.
  12. Record final performance stats.
  13. If time, refactor some of the Vision and Combat System checks to also use the new quadtree registries.
Contributor

nwinter commented Mar 2, 2015

Here are some steps I'd take when doing this one:

  1. Get the dev environment set up. Make sure to download the database dump.
  2. Add a placeholder quadtree.coffee class in app/lib/world. You can look at Vector.coffee for an idea of how to format it.
  3. In the level editor for, say, Sarven Treasure, open the Inventory System and try to require the QuadTree class to make sure that your import is set up correctly.
  4. Implement the APIs you need to interface between the QuadTree and the Systems' registries, but just using a simple array to start off. Make it so there are two types of registries: normal arrays, and also quadtree registries.
  5. Make sure existing levels still work: collectors can collect coins and hearers can hear sayers.
  6. Create a test level where it takes a lot of CPU to determine what Collects Thangs are collecting what Collectable Thangs (so tons of coins, tons of Collectors).
  7. Record performance stats for the test level in a controlled run.
  8. Implement the QuadTree APIs to make it so that it's not an O(n * m) operation.
  9. Make sure the results of the test level are the same.
  10. Record performance stats for the test level now using quadtrees.
  11. Use the Chrome profiler on the web worker thread when running the level to see where the code is still slow, and optimize it.
  12. Record final performance stats.
  13. If time, refactor some of the Vision and Combat System checks to also use the new quadtree registries.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment