Last week I was playing around with a little EaselJS experiment which required me to do collision detection against all items on the screen. This worked fine with a small number of items, but of course, the more items I added, the slower everything became.
A QuadTree is a data structure in which the coordinate space is broken up into regions / nodes that contain items. If too many items are added into a node, then that node is divided into 4 sub-nodes. This can provide very fast lookup of items based on the coordinates and coordinates and dimensions.
I've released all of the code under an MIT License, and you can download it from my GitHub repository.
Here is an example of the tree in action:
This example shows how to use the QuadTree to pare down the number of items that need to be tested for collision detection.
I have created a couple of other simple examples:
- Collision Detection (shown above)
- Inserting points
- Inserting items with bounds
- Retrieving points
- Retrieving items with bounds
The basic code is pretty simple. Here is an example showing using the QuadTree to store and retrieve points:
And here is a simple example showing using the QuadTree to store and retrieve items with dimensions / bounds:
Again, you can download all of the code from my GitHub Repository. It seems fairly solid at this point, but if you find any issues, or have any suggestions either fork the project, and submit the changes to me, or post them in the comments.
There is still a lot of room for optimization and improvement in the implementation, such as pre-allocating the nodes, but Ill leave that for another day.
Btw, big thanks to Ralph Hauwert for pointing me in the right direction for my project.
Post any questions or suggestions in the comments.