2
\$\begingroup\$

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:

  1. What if you don't keep dots in the tree itself but keep them inside some array?
  2. Are there more optimal insertion and intersection functions than I have written
  3. 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!

\$\endgroup\$
1
  • \$\begingroup\$ Using public keyword might reduce boilerplate. See example \$\endgroup\$ Commented Jan 11, 2022 at 13:49

0

Browse other questions tagged or ask your own question.