Typically, you would have a list of entities stored somewhere, and you'd use quadtree when you need some collision testing between entities for example, by inserting all of the entities and generating a quadtree, and getting the nearest ones that you need for the tests.

But I was wondering, beyond collision testing, the quadtree could be even more helpful if you didn't have a list, but the entities were directly owned by the cells of the quadtree.

For example, when you need to erase an entity, or find a particular entity, you would have to iterate through your entire list. If the quadtree owned the entities, I could pass the position of my entity and it would only seek through entities that are in the same cell.

Instead of iterating through thousands of entities, it would test 'position contains rectangle' a dozens of time, and iterate through the few entities inside the quadtree cell.

Would this even optimize time, and would it be worth it ?

  • \$\begingroup\$ Why not use both list and quadtree? \$\endgroup\$ – some rand Dec 23 '18 at 12:41
  • \$\begingroup\$ @somerand In the case of when you destroy an entity, you would have to remove it from the list so that would involve performance cost if the list is too large. If only quadtree owns you would only have to erase from quadtree cell, which I presume would be faster if the total number of entities is too much. \$\endgroup\$ – rick Dec 23 '18 at 12:53
  • \$\begingroup\$ Have you tried setting up some test cases and profiling the programs? \$\endgroup\$ – Tyyppi_77 Dec 23 '18 at 15:11
  • \$\begingroup\$ erasing from linked list is fast, finding entity is slow. instead of list use red black tree aka std::map. finding in map is O(logn)). \$\endgroup\$ – some rand Dec 24 '18 at 12:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.