everybody. It took a tree of squares for my web game. I wrote a preview using Typescript. I would like to hear from you tips on how to improve the code (I just started writing in Typescript). First of all, I would like to improve performance. I have a couple of ideas but I don't know how to implement them:
- What if you don't keep dots in the tree itself but keep them inside some array?
- Are there more optimal insertion and intersection functions than I have written
- Is it better to write four subnodes directly or leave it as my array?
In my game the dots will move and there will be a lot of them (about 8-10 thousand, I take it it is correct to remove and recreate the tree every time?).
So let's start describing the code. First, there are two small classes for a point and a rectangle:
// represent simple point on canvas
class Point {
x: number;
y: number;
constructor(x, y) {
this.x = x;
this.y = y;
}
move(x , y) {
this.x = x;
this.y = y;
}
}
// represent box (rectangle) on canvas
class Box {
x: number;
y: number;
w: number;
h: number;
constructor(x,y,w,h) {
this.x = x;
this.y = y;
this.w = w;
this.h = h;
}
contain(p: Point): boolean {
return (p.x >= this.x - this.w
&& p.x <= this.x + this.w
&& p.y >= this.y - this.h
&& p.y <= this.y + this.h)
}
}
Now the largest code fragment responsible for Node's representation
// Maximum number of points after which the Node will be divided
const MAX_ELEMENTS: number = 5;
// Maximum depth of the QuadTree
const MAX_DEEP: number = 9;
// Represents a node in the quadtree
class QuadNode {
x: number;
y: number;
width: number;
height: number;
maxElements: number;
maxDeep: number;
divided: boolean;
// all points in Node
pointList: Point[];
children: QuadNode[];
constructor(x,y, width, height, deep) {
this.x = x;
this.y = y;
this.width = width;
this.height = height;
this.maxElements = MAX_ELEMENTS;
this.maxDeep = 0;
this.divided = false;
}
// Divide node into subnodes
split() {
this.divided = true;
let x = this.x;
let y = this.y;
let subWidth = this.width / 2;
let subHeight = this.height / 2;
let newDeep = this.maxDeep + 1;
this.children.push(new QuadNode(x - subWidth, y - subWidth, subWidth, subHeight, newDeep));
this.children.push(new QuadNode(x - subWidth, y + subWidth, subWidth, subHeight, newDeep));
this.children.push(new QuadNode(x + subWidth, y + subWidth, subWidth, subHeight, newDeep));
this.children.push(new QuadNode(x + subWidth, y - subWidth, subWidth, subHeight, newDeep));
}
// Node contain point? if yes - true
contain(p: Point): boolean {
return (p.x >= this.x - this.width
&& p.x <= this.x + this.width
&& p.y >= this.y - this.height
&& p.y <= this.y + this.height)
}
intersects (b: Box) {
return (b.x - b.w > this.x + this.width
|| b.x + b.w < this.x - this.width
|| b.y - b.h > this.y + this.height
|| b.y + b.h < this.y - this.height)
}
// The function returns an array of points that are contained inside a Box.
range(b: Box, points = []) {
if (!this.intersects(b)) {
return [];
} else {
for (let point of this.pointList) {
if (b.contain(point)) {
points.push(point);
}
}
if (this.divided) {
for (let child of this.children) {
child.range(b, points);
}
}
return points;
}
}
// Insert point into tree
insert(p: Point) {
if (this.divided) {
for (let child of this.children) {
if (child.contain(p)) {
child.insert(p);
}
}
} else {
if (this.maxDeep == MAX_DEEP) {
this.pointList.push(p);
} else {
if (this.pointList.length < this.maxElements) {
this.pointList.push(p);
} else if (this.pointList.length >= this.maxElements) {
this.split();
this.insert(p);
}
}
}
}
}
And finally, a small piece of code (for better api) representing the trees themselves:
class QuadTree {
rootNode: QuadNode;
constructor(x,y,width,height, ) {
this.rootNode = new QuadNode(x,y,width,height, 0);
}
add(p: Point) {
this.rootNode.insert(p);
}
range(b: Box, points = []) {
this.rootNode.range(b,points);
}
};
Thank you very much!
public
keyword might reduce boilerplate. See example \$\endgroup\$