Getting started

This repository contains the monorepo for the following TypeScript packages:

• @4bitlabs/quadtree - A simple 2D quadtree (2×2 spatial division) for fast, efficient spatial queries
• @4bitlabs/ennetree - A simple 2D ennetree (3×3 spatial division) for fast, efficient spatial queries.

Quadtree

import { quadtree } from '@4bitlabs/quadtree';

class Entity {
  bounds(): Bounds {
    /* determine bounds */
    return [0, 0, 0, 0];
  }
}

const space = quadtree<Entity>([0, 0, 1000, 1000], Entity.prototype.getBounds);
Copy

Ennetree

Similar to a quadtree but instead of binary recursive subdivisions, an ennetree uses trinary (3×3) subdivisions.

Depending on the use-case, this can sometimes yield more efficient spatial queries.

import { ennetree, type Bounds } from '@4bitlabs/ennetree';

class Entity {
  bounds(): Bounds {
    /* determine bounds */
    return [0, 0, 0, 0];
  }
}

const space = ennetree<Entity>([0, 0, 1000, 1000], Entity.prototype.getBounds);
Copy

Quadtree/Ennetree Options

Both quadtree() and ennetree() accept a third argument of options:

option	Description	Defaults
maxDepth	The maximum depth/subdivisions that the graph will divide.	quadtree = 7, ennetree = 4
maxChildren	The maximum number of objects in a node before it will split	quadtree,ennetree = 10

const space = quadtree<Entity>([0, 0, 1000, 1000], Entity.prototype.getBounds, {
  maxDepth: 5,
  maxChildren: 50,
});
Copy