📦 sbuggay / boids

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120class Point {
    constructor(x, y) {
        this.x = x;
        this.y = y;
    }
}

class Rect {
    constructor(x, y, w, h) {
        this.x = x;
        this.y = y;
        this.w = w;
        this.h = h;
    }

    contains(point) {
        return (point.x >= this.x - this.w &&
            point.x < this.x + this.w &&
            point.y >= this.y - this.h &&
            point.y < this.y + this.h);
    }

    intersects(range) {
        return !(range.x - range.w > this.x + this.w ||
            range.x + range.w < this.x - this.w ||
            range.y - range.h > this.y + this.h ||
            range.y + range.h < this.y - this.h);
    }
}

class QuadTree {
    constructor(boundary, capacity) {
        this.boundary = boundary;
        this.capacity = capacity;
        this.list = [];
        this.divided = false;
    }

    insert(boid) {

        const point = boid.position;

        if (!this.boundary.contains(point)) return;

        if (this.list.length < this.capacity) {
            this.list.push(boid);
        }
        else {
            if (!this.divided) {
                this.subdivide();
            }

            this.ne.insert(boid);
            this.nw.insert(boid);
            this.sw.insert(boid);
            this.se.insert(boid);
        }
    }

    query(range, found) {
        if (!found) {
            found = [];
        }

        if (!this.boundary.intersects(range)) {
            return;
        } else {
            for (let p of this.list) {
                if (range.contains(p.position)) {
                    found.push(p);
                }
            }
            if (this.divided) {
                this.nw.query(range, found);
                this.ne.query(range, found);
                this.se.query(range, found);
                this.sw.query(range, found);
            }
        }
        return found;
    }

    subdivide() {
        let x = this.boundary.x;
        let y = this.boundary.y;
        let w = this.boundary.w;
        let h = this.boundary.h;

        let neRect = new Rect(x + w / 2, y + h / 2, w / 2, h / 2);
        let nwRect = new Rect(x - w / 2, y + h / 2, w / 2, h / 2);
        let swRect = new Rect(x - w / 2, y - h / 2, w / 2, h / 2);
        let seRect = new Rect(x + w / 2, y - h / 2, w / 2, h / 2);
        this.ne = new QuadTree(neRect, this.capacity);
        this.nw = new QuadTree(nwRect, this.capacity);
        this.sw = new QuadTree(swRect, this.capacity);
        this.se = new QuadTree(seRect, this.capacity);
        this.divided = true;

    }

    render() {

        if (this.ne) this.ne.render();
        if (this.nw) this.nw.render();
        if (this.se) this.se.render();
        if (this.sw) this.sw.render();

        if (this.ne && this.nw && this.se && this.sw) return; // Don't render if we render all children

        push();
        stroke(200, 200, 200, 100);
        fill(0, 0, 0, 0);
        rectMode(CENTER);
        translate(this.boundary.x, this.boundary.y);
        rect(0, 0, this.boundary.w * 2, this.boundary.h * 2)
        pop();
    }
}