基于
https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374
quadtree-js
This is a JavaScript Quadtree implementation of the Java Methods described in this tutorial:
This is not a collision engine, but an algorithm to narrow down objects of possible collision.
Please read the tutorial if you want to know more about Quadtrees.
There are two examples: and .
- red squares represent Quadtree Nodes
- empty white squares represent objects in our Quadtree
- the cursor is the area we constantly test for
- objects turned green are candidates for collision, returned from the receive-function
How to use
Create a new Quadtree with default values for max_objects (10) and max_levels (4)
var myTree = new Quadtree({ x: 0, y: 0, width: 400, height: 300});
If you want to specify max_objects and max_levels on your own, you can pass them as a 2nd and 3rd argument
var myTree = new Quadtree({ x: 0, y: 0, width: 800, height: 600}, 5, 8);
Insert an element in the Quadtree
myTree.insert({ x : 200, y : 150, width : 20, height : 20});
Retrieve elements that "collide" with the given bounds
var elements = myTree.retrieve({ x : 150, y : 100, width : 20, height : 20});
Clear the Quadtree
myTree.clear();
Check out the examples for more information. Feel free to open an issue if you have any problems.
There is an alternative available that allows you to update and remove single objects. This can be handy when most of the objects in your Quadtree are static.