04. QuadTree
Visualizes 2D space collisions with quad tree. Optimizes number of collision comparison significantly than a bruteforce method (O(n^2)).
Worst query time is O(n)
Program only handles 1000 entities due to small screen and over 1000 entities did not seem necessary for demonstration purpose.
To add entity, LEFT CLICK any area in the orange box to add single entity on clicked position or press A to add 10 entities on random position.
To remove entity, RIGHT CLICK on the entity to remove single entity or press E to remove first 10 entities on the entity list (FIFO).
If entity is too small to remove, pause the simulation by pressing SPACE.
To remove all entities, press C.
To track single entity, click the entity (it's small so I receommend to pause the simulation by SPACE key and then click) you want to track. Blue entity will be the one you track and green entity will be the near entities which can possibly collide with blue one.
If duplication check is enabled, it avoids checking collision with entities that were already checked before.
For this, I used fixed size of vector look up table instead of std::unordered_map<int, bool> because map was very slow comapred to vector.
Toggle this option by pressing D.
If collision resolution is enabled, entity will kind of 'bounce off' from collided entity instead of passing by.
Collidided/Colliding entities are shown as red on the screen.
Toggle this option by pressing R.
If grid is enabled, you can see the sub division of QuadTree in the system. Toggle this option by pressing G.
You can increase of decrease QuadTree's maximum level of subdivision.
This feature is limited between 5 and 10.
Since simulation area is limited, it's hard to see QuadTree subdividing more than level 5.
This program will count how many collision check was performed on every frame. You can also check the current number of entities in the orange box.
Numbers are displayed on right top of window.