QT

A Quadtree implementation using JavaScript

Check out the demo here

Getting Started

Clone this repository or download it as a zip file.

Installation

npm is required to install the library. Get it here

npm init
npm install qt-js

To use the modules with vanilla HTML/JavaScript install browserify and/or watchify to bundle your JavaScript codes along with the modules.

npm install -g browserify
npm install -g watchify

Use require to include the modules in your JavaScript.

const {Geom, QT, Collision} = require('qt-js');

To create the bundle, use the command

browserify scripts/logic.js -o scripts/logic-bundle.js

or if you want the codes to be bundled whenever you save

watchify scripts/logic.js -o scripts/logic-bundle.js

use a <script> tag to include your new bundle

<script src="scripts/logic-bundle.js"></script>

Modules

GEOM

The Geom module allows the creation of new geoms (point, box and circ).

The module also contains helpers to calculate the distance between points, the angle of a vector and split a vector into X and Y components.

point(x, y)
create a new point

let point = new Geom.point(0 , 0);

//point.x is 0;
//point.y is 0;

box(x, y, width, height)
create a new box

let box = new Geom.box(0 , 0, 50, 25);

//box.x = 0;
//box.y = 0;
//box.width = 50;
//box.height = 25;

circ(x, y, radius)
create a new circle

let circle = new Geom.circ(0 , 0, 25);

//circle.x = 0;
//circle.y = 0;
//circle.radius = 25;
//circle.width = 50;
//circle.height = 50;

dist2Points(x1, y1, x2, y2)
calculate distance between two points

let distance = Geom.dist2Points(0, 0, 10, 10);

//distance = 14.142135623730951

angle(xLen, yLen)
calculates the angle (degrees) of a vector

let pt1 = {x: 0, y: 0},
    pt2 = {x: 10, y: 10;

let xLen = pt2.x - pt1.x;
let yLen = pt2.y - pt1.y;

let angle = Geom.angle(xLen, yLen);

//angle = 45

vector(magnitude, angle)
breaks a vector into X and Y components

let vector = Geom.vector(14.142135623730951, 45);

//vector.x = 10;
// vector.y = 10;

QT

The QT module allows the creation of quadtrees for spatial partitioning.

This module contains methods to insert or delete a rectangle from a tree and retrieve a list of possible objects it can collide with.

PROPERTIES

maxChildren
the maximum objects a node can contain before splitting

quadTree.maxChildren  = 15;

maxLevel
the maximum number of times that a node can be split

quadTree.maxLevel   = 15;

METHODS

node(level, bounds)
creates a new quadtree node

const bounds = new Geom.box(0 , 0, 100, 100);
const quadTree = new QT.node(0, bounds);

clear()
clears all child nodes

quadTree.clear();

split()
split current node into quadrants

quadTree.split();

getQuadrant(rectangle)
get quadrant containing the rectangle in the current node

let rec = new Geom.box(0, 0, 25, 25);

quadTree.getQuadrant(rec);

insert(rectangle)
insert a rectangle into the node (can be a Geom.box or Geom.circ)

let rec = new Geom.box(0, 0, 25, 25);

quadTree.insert(rec);

retrieve(returnList, rectangle)
retrieves all possible objects that the rectangle can collide with and stores them in the returnList

let rec = new Geom.box(0, 0, 25, 25);
let colliderList = [];

quadTree.retrieve(colliderList, rec);

delete(rectangle)
deletes a rectangle from the quadtree

quadTree.delete(rectangle);

COLLISION

The Collision module contains methods for testing rectangular or circular collision.

testRect(rec1, rec2)
creates a new quadtree node

let rect1 = new Geom.box(0, 0, 50, 25);
let rect2 = new Geom.box(5, 10, 50, 25);

let result = Collision.testRect(rect1, rect2);

//result = true;

testCirc(circ1, circ2)
creates a new quadtree node

let circ1 = new Geom.circ(0, 0, 25);
let circ2 = new Geom.circ(5, 10, 25);

let result = Collision.testCirc(circ1, circ2);

//result = true;

License

This project is licensed under the MIT License - see the LICENSE.md file for details

Helpful Resources

• https://gamedevelopment.tutsplus.com/tutorials/quick-tip-use-quadtrees-to-detect-likely-collisions-in-2d-space--gamedev-374
• http://buildnewgames.com/broad-phase-collision-detection/
• http://devmag.org.za/2009/04/13/basic-collision-detection-in-2d-part-1/