Not sure what a Quadtree is? A Quadtree is a way of splitting a game world (or other 2D space) in to separate spatial nodes, allowing a more efficient way to query which objects are in a given area. Read more here!

Installation

npm install @evilkiwi/quadtree

Usage

The library exposes a single class, Quadtree, which you can use to insert and query objects.

import { Quadtree } from '@evilkiwi/quadtree';

// First, we create the Quadtree.
const tree = new Quadtree({
  width: 1024, // The width of the game world.
  height: 1024, // The height of the game world.
  max_depth: 12, // The maximum depth of the quadtree - i.e. how many times it can split in to quads.
  max_objects: 15, // The maximum number of objects that can be in a quad before it splits.
});

// Next, we insert some objects.
tree.insert({
  // All objects require a unique ID.
  id: 'object-1',
  // The position and size of the object.
  x: 489,
  y: 200,
  width: 20,
  height: 20,
});

// You can also insert multiple objects at once.
tree.insertAll([
  {
    id: 'object-2',
    x: 460,
    y: 190,
    width: 20,
    height: 20,
  },
  {
    id: 'object-3',
    x: 1000,
    y: 1000,
    width: 20,
    height: 20,
  },
]);

Querying Objects

Once you've inserted some objects into the Quadtree, you can query it for objects that are in a given area. The Objects returned are just in the quad(s) that cover the given area - meaning they may not be within the requested area, but are close enough that you can do collision detection on them.

const objects = tree.retrieve({
  x: 480,
  y: 180,
  width: 100,
  height: 100,
});

console.log(objects);

// [
//   {
//     id: 'object-1',
//     x: 489,
//     y: 200,
//     width: 20,
//     height: 20,
//   },
//   {
//     id: 'object-2',
//     x: 460,
//     y: 190,
//     width: 20,
//     height: 20,
//   },
// ]

Updating Objects

You can't update objects once they've been inserted into the Quadtree, given it has to rebuild the quads every time an object is updated. Instead, you can use the clear() method to remove all objects from the Quadtree, and then insert them again.

// First, we clear the Quadtree.
tree.clear();

// Then we re-insert the objects with their updated positions.
tree.insert({
  id: 'object-1',
  x: 450,
  y: 195,
  width: 20,
  height: 20,
});

...

What is a Quadtree?

A regular way of checking collisions in a game would be getting ObjectA and checking it's position against every other Object/Entity in my game, and then doing the same for every other Object/Entity. This is minimal with a smaller amount of entities, but isn't scalable. And whilst you can optimise this somewhat, it fundamentally cannot scale. This method is called the n^2 method, as if you have 100 Object/Entities, you'll need to do 100^2 checks to run the collision logic (10,000 checks).

The idea behind a Quadtree in Game Development is to get around this by having spacial awareness. For example, if I'm checking collisions for ObjectA, I only need to check the other Entities/Objects that are around it - there's no point checking for collision against an Entity that's on the other side of the game world. You could do something similar to this in the n^2 method by looping over every single Object/Entity, checking whether its position is close to ObjectA and only then running collision logic on it, but this is still fundamentally unscalable as you are still doing some level of logic on every Object/Entity in the game world, hence the performance bottlenecks of n^2 still apply.

A Quadtree does this by taking Objects that you supply it (In Game Dev, these would be Entities), and then subdividing the game world in to quads based on how many Objects are in a given area. For example, see this image:

The blue lines show the quads that were generated by the quadtree after inserting the red objects (Entities).

For more information on Quadtrees and how they work, check out this video: What are Quadtrees.