Quadtree(​properties)

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

Quadtree Parameters

properties

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 since 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(​objectsN)

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());
  }
});

add Parameters

objectsN

Object or an Array of Objects. Objects to add to the quadtree.

Quadtree​.bounds

The 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]

get 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.

get Return value

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

Quadtree​.maxDepth

Maximum node depth of the quadtree.

Quadtree​.maxObjects

Maximum number of objects a node can have before splitting.