все! Я написал небольшое дерево квадов с помощью typescqript. Я пытаюсь использовать его, чтобы нарисовать несколько тысяч движущихся точек. Но это очень медленно.
Например, я уже добавил 1500 точек, но если вы добавите 5000 точек, то запустятся лаги.
В чем может быть проблема? Я писал четырехугольное дерево, используя Википедию и примеры кода оттуда.
Может быть, я не так рисую с помощью canvas.
Весь код здесь:
function genRandom(end: number) {
return ((Math.random() * end) + 0)
}
// 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;
}
// random point jitter
rmove() {
this.x += Math.random() < 0.5 ? -1 : 1;
this.y += Math.random() < 0.5 ? -1 : 1;
}
render (ctx) {
ctx.fillStyle = "gray";
ctx.beginPath();
ctx.arc(this.x, this.y, 1.5, 0, Math.PI*2, true);
ctx.closePath();
ctx.fill();
ctx.stroke();
}
}
// 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)
}
}
// 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[] = new Array;
children: QuadNode[] = new Array;
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);
}
}
}
}
getAllNodes(nodesList) {
if (this.children.length > 0) {
for (let child of this.children) {
nodesList.push(child);
child.getAllNodes(nodesList);
}
}
nodesList.push(this);
return nodesList
}
}
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);
}
getAllNodes(nodesList) {
if (this.rootNode.children.length > 0) {
for (let child of this.rootNode.children) {
child.getAllNodes(nodesList);
}
}
nodesList.push(this.rootNode);
return nodesList
}
render(nodeList) {
ctx.strokeStyle = "rgb(180, 180, 180)";
for (let node of nodeList) {
ctx.beginPath();
ctx.rect(node.x, node.y, node.width, node.height);
ctx.stroke();
ctx.closePath();
}
}
};
/**
* Drawing Quadtree
*/
let canvas = <HTMLCanvasElement> document.getElementById('canvas');
let ctx = canvas.getContext('2d');
let cwidth = canvas.width;
let cheight = canvas.height;
const POINTS_SIZE: number = 1500;
const particles = [];
// Add a square where the user clicks
canvas.addEventListener("click", function(evt) {
var e = {
x: evt.pageX - canvas.getBoundingClientRect().left,
y: evt.pageY - canvas.getBoundingClientRect().top
};
particles.push(new Point(e.x - 1.5 / 2, e.y - 1.5 / 2));
});
function initTree() {
for (let i = 0; i < POINTS_SIZE; i++) {
particles[i] = new Point(genRandom(cwidth), genRandom(cheight));
}
}
function render () {
// clear screen
ctx.clearRect(0, 0, cwidth, cheight);
// create new quadtree
let tree = new QuadTree(cwidth/2, cheight/2, cwidth, cheight);
// random move points and add points in tree
for (let p of particles) {
p.rmove();
tree.add(p);
p.render(ctx);
}
// draw quadtree
let nodeList: QuadNode[] = new Array;
nodeList = tree.getAllNodes(nodeList);
tree.render(nodeList);
}
initTree();
let t = setInterval(function() { render() }, 90);
С помощью Инструменты измерения производительности, я понял, что эта функция делает больше всего:
function render () {
// clear screen
ctx.clearRect(0, 0, cwidth, cheight);
// create new quadtree
let tree = new QuadTree(cwidth/2, cheight/2, cwidth, cheight);
// random move points and add points in tree
for (let p of particles) {
p.rmove();
tree.add(p);
p.render(ctx);
}
// draw quadtree
let nodeList: QuadNode[] = new Array;
nodeList = tree.getAllNodes(nodeList);
tree.render(nodeList);
}
Каждый тик я обновляю sh дерево квадратов (удаляем точки из него) и добавляю новое, слегка изменяя их координаты.
Помогите мне улучшить мою производительность!