Efficient Collision Detection with Quadtrees
Introduction
Quadtrees are, as the name suggests, tree-shaped data structures in which each node has 4 child nodes. For the purpose of collision detection, we let each of the 4 nodes represent a quadrant of a coordinate plane. We then let each node contain a list of items within its quadrant. When the list of items grows too long, the node is split into 4 quadrants, and its items are redistributed among them. This allows for us to recursively search the tree for items within a boundary. Performance-wise, this process is vastly superior to alternative implementations, such as search a 2D array.
There are other implementations for quadtrees in JavaScript, such as those by Mike Chambers and Silflow, but there is still ground to be broken. In particular, I aim to create an immutable quadtree implementation.
Usage
Creating a quadtree
// Create a 200x200 coordinate planeconst range = ;let quadtree = Quadtree;
Inserting items
// Items must have x, y, width, and height properties// So they should be boundaries// Or something composed with boundariesconst item = ;quadtree = Quadtree;
// You can also batch insert itemsconst items = ; quadtree = Quadtree;
Searching
const range = ;const viewport = ; let quadtree = Quadtree; const items = ; quadtree = Quadtree; // [boundary(149, 121, 2, 1), boundary(64, 120, 5, 7), boundary(112, 57, 2, 2), boundary(49, 49, 2, 2)]const results = Quadtree;
Clearing
quadtree = Quadtreeclearquadtree;
Building and Testing
To download and install
$ git clone https://github.com/Zubry/immutable-quadtree.git
$ cd immutable-quadtree
$ npm install
To build
$ npm run-script lint
$ npm run-script build
To test
$ npm run-script test
or
$ npm test