Skip navigation

Quadtree(​[properties])

A 2D spatial partitioning data structure. Use it to quickly group objects by their position for faster access and collision checking.

Parameters

properties Optional

Object. Properties of the quadtree.

properties.maxDepth Optional

Number. Maximum node depth of the quadtree. Defaults to 3.

properties.maxObjects Optional

Number. Maximum number of objects a node can have before splitting. Defaults to 25.

properties.bounds Optional

Object. The 2D space (x, y, width, height) the quadtree occupies. Defaults to the entire canvas width and height.

Table of Contents

Basic Use

Every frame you should remove all objects from the quadtree using its clear() function and then add all objects back using its add() function. You can add a single object, a list of objects, or an array of objects.

let { Quadtree, Sprite, GameLoop } = kontra;

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy);
  }
});

import { Quadtree, Sprite, GameLoop } from 'path/to/kontra.mjs';

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy);
  }
});

import { Quadtree, Sprite, GameLoop } from 'kontra';

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy);
  }
});

You should clear the quadtree each frame as the quadtree is only a snapshot of the position of the objects when they were added. Since the quadtree doesn't know anything about those objects, it doesn't know when an object moved or when it should be removed from the tree.

Objects added to the tree must have the properties x, y, width, and height so that their position in the quadtree can be calculated. Sprite defines these properties for you.

When you need to get all objects in the same node as another object, use the quadtrees get() function.

let objects = quadtree.get(player);  //=> [enemy]

Quadtree​.add(​...objects)

Add objects to the quadtree and group them by their position. Can take a single object, a list of objects, and an array of objects.

let { Quadtree, Sprite, Pool, GameLoop } = kontra;

let quadtree = Quadtree();
let bulletPool = Pool({
  create: Sprite
});

let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

// create some bullets
for (let i = 0; i < 100; i++) {
  bulletPool.get({
    // ...
  });
}

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy, bulletPool.getAliveObjects());
  }
});

import { Quadtree, Sprite, Pool, GameLoop } from 'path/to/kontra.mjs';

let quadtree = Quadtree();
let bulletPool = Pool({
  create: Sprite
});

let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

// create some bullets
for (let i = 0; i < 100; i++) {
  bulletPool.get({
    // ...
  });
}

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy, bulletPool.getAliveObjects());
  }
});

import { Quadtree, Sprite, Pool, GameLoop } from 'kontra';

let quadtree = Quadtree();
let bulletPool = Pool({
  create: Sprite
});

let player = Sprite({
  // ...
});
let enemy = Sprite({
  // ...
});

// create some bullets
for (let i = 0; i < 100; i++) {
  bulletPool.get({
    // ...
  });
}

let loop = GameLoop({
  update: function() {
    quadtree.clear();
    quadtree.add(player, enemy, bulletPool.getAliveObjects());
  }
});

Parameters

...objects

A list of (Object or an Array of Objects). Objects to add to the quadtree. Can be a single object, an array of objects, or a comma-separated list of objects.

Quadtree​.bounds

Object. he 2D space (x, y, width, height) the quadtree occupies.

Quadtree​.clear(​)

Removes all objects from the quadtree. You should clear the quadtree every frame before adding all objects back into it.

Quadtree​.get(​object)

Get an array of all objects that belong to the same node as the passed in object.

Note: if the passed in object is also part of the quadtree, it will not be returned in the results.

let { Sprite, Quadtree } = kontra;

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy1 = Sprite({
  // ...
});
let enemy2 = Sprite({
  // ...
});

quadtree.add(player, enemy1, enemy2);
quadtree.get(player);  //=> [enemy1]

import { Sprite, Quadtree } from 'path/to/kontra.mjs';

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy1 = Sprite({
  // ...
});
let enemy2 = Sprite({
  // ...
});

quadtree.add(player, enemy1, enemy2);
quadtree.get(player);  //=> [enemy1]

import { Sprite, Quadtree } from 'kontra';

let quadtree = Quadtree();
let player = Sprite({
  // ...
});
let enemy1 = Sprite({
  // ...
});
let enemy2 = Sprite({
  // ...
});

quadtree.add(player, enemy1, enemy2);
quadtree.get(player);  //=> [enemy1]

Parameters

object

Object. Object to use for finding other objects. The object must have the properties x, y, width, and height so that its position in the quadtree can be calculated.

Return value

An Array of Objects. A list of objects in the same node as the object, not including the object itself.

Quadtree​.maxDepth

Number. aximum node depth of the quadtree.

Quadtree​.maxObjects

Number. aximum number of objects a node can have before splitting.