class AABB {
constructor(x, y, w, h) {
// Use Float32Array for better performance when dealing with many boundary checks
this.data = new Float32Array([x, y, w, h]);
}
// Optimized contains check with cached property access
contains(x, y) {
const data = this.data;
const x0 = data[0];
const y0 = data[1];
return (
x >= x0
&& x <= x0 + data[2]
&& y >= y0
&& y <= y0 + data[3]
);
}
// Optimized intersection check with cached property access
intersects(other) {
const a = this.data;
const b = other.data;
return !(
b[0] > a[0] + a[2]
|| b[0] + b[2] < a[0]
|| b[1] > a[1] + a[3]
|| b[1] + b[3] < a[1]
);
}
}
class Square {
static init() {
Square.nextId = 0;
}
constructor(x, y, size) {
// Using Float32Array for better performance
this.data = new Float32Array([
x, // 0: x
y, // 1: y
size, // 2: size
(Math.random() - 0.5) * 2, // 3: dx
(Math.random() - 0.5) * 2, // 4: dy
Square.nextId++ // 5: id
]);
this.element = document.createElement("div");
this.element.className = "square";
this.element.style.width = this.element.style.height = `${size}px`;
this.isColliding = false;
this.updateTransform();
}
// Update method is now simplified and delegated to the Demo class
updateTransform() {
this.element.style.transform = `translate(${this.data[0]}px,${this.data[1]}px)`;
}
}
Square.init();
class QuadTree {
static init() {
QuadTree.pool = [];
QuadTree.maxPoolSize = 1000;
// Pre-create the pool to avoid allocations during runtime
for(let i = 0; i < 100; i++) {
QuadTree.pool.push(new QuadTree(null,
4,
5,
0));
}
}
static acquire(boundary, capacity = 4, maxDepth = 5, depth = 0) {
if(QuadTree.pool.length > 0) {
const qt = QuadTree.pool.pop();
// Set properties instead of creating new objects
qt.boundary = boundary;
qt.capacity = capacity;
qt.maxDepth = maxDepth;
qt.depth = depth;
qt.items.length = 0;
qt.divided = false;
qt.nw = qt.ne = qt.sw = qt.se = null;
return qt;
}
return new QuadTree(boundary,
capacity,
maxDepth,
depth);
}
static release(qt) {
if(qt.divided) {
QuadTree.release(qt.nw);
QuadTree.release(qt.ne);
QuadTree.release(qt.sw);
QuadTree.release(qt.se);
// Clear references to help garbage collection
qt.nw = qt.ne = qt.sw = qt.se = null;
}
if(QuadTree.pool.length < QuadTree.maxPoolSize) {
QuadTree.pool.push(qt);
}
}
constructor(boundary, capacity = 4, maxDepth = 5, depth = 0) {
this.boundary = boundary;
this.capacity = capacity;
this.maxDepth = maxDepth;
this.depth = depth;
this.items = [];
this.divided = false;
this.nw = this.ne = this.sw = this.se = null;
}
subdivide() {
const data = this.boundary.data;
const x = data[0];
const y = data[1];
const w = data[2] * 0.5; // More efficient than dividing by 2
const h = data[3] * 0.5;
// Create new AABB objects for children
const nwBoundary = new AABB(x,
y,
w,
h);
const neBoundary = new AABB(x + w,
y,
w,
h);
const swBoundary = new AABB(x,
y + h,
w,
h);
const seBoundary = new AABB(x + w,
y + h,
w,
h);
this.nw = QuadTree.acquire(nwBoundary,
this.capacity,
this.maxDepth,
this.depth + 1);
this.ne = QuadTree.acquire(neBoundary,
this.capacity,
this.maxDepth,
this.depth + 1);
this.sw = QuadTree.acquire(swBoundary,
this.capacity,
this.maxDepth,
this.depth + 1);
this.se = QuadTree.acquire(seBoundary,
this.capacity,
this.maxDepth,
this.depth + 1);
this.divided = true;
}
insert(item) {
// Early boundary check optimization
if(!this.boundary.contains(item.data[0],
item.data[1]))
return false;
// If we have capacity or reached max depth, add item here
if(this.items.length < this.capacity || this.depth >= this.maxDepth) {
this.items.push(item);
return true;
}
// Subdivide if needed and insert into appropriate child
if(!this.divided)
this.subdivide();
// Try to insert in each quadrant (optimized with short-circuit evaluation)
return (
this.nw.insert(item)
|| this.ne.insert(item)
|| this.sw.insert(item)
|| this.se.insert(item)
);
}
query(range, found) {
// Early exit optimization - no intersection with this quadrant
if(!this.boundary.intersects(range))
return found;
// Check all items in this node
const items = this.items;
const itemsLength = items.length;
// Manual loop is faster than for...of
for(let i = 0; i < itemsLength; i++) {
const item = items[i];
if(range.contains(item.data[0],
item.data[1])) {
found.push(item);
}
}
// Recurse into children if they exist
if(this.divided) {
this.nw.query(range,
found);
this.ne.query(range,
found);
this.sw.query(range,
found);
this.se.query(range,
found);
}
return found;
}
}
QuadTree.init();
class Demo {
constructor() {
this.wrapper = document.getElementById("wrapper");
this.container = document.getElementById("container");
this.elementsLayer = document.getElementById("elements-layer");
this.treeLayer = document.getElementById("tree-layer");
// Use alpha: false for better canvas performance
this.ctx = this.treeLayer.getContext("2d",
{ alpha: false });
this.width = 0;
this.height = 0;
// Use individual variables instead of array fill
this.speedValue = null;
this.speedMultiplier = 1;
this.fpsDisplay = null;
this.lastFpsUpdate = 0;
this.frameCount = 0;
this.holdTimer = null;
this.squares = [];
this.running = true;
this.showTrees = false;
this.collisions = 0;
this.holdDelay = 100;
this.queryResults = [];
this.collisionPairs = new Set();
// Reusable AABB for queries to avoid object creation
this.queryRange = new AABB(0,
0,
0,
0);
this.resize();
window.addEventListener("resize",
() =>
this.resize());
this.setupControls();
this.addSquares(50);
// Use requestAnimationFrame properly
this._animateBound = this.animate.bind(this);
requestAnimationFrame(this._animateBound);
}
resize() {
const size = Math.min(this.wrapper.offsetWidth,
window.innerHeight * 0.8 - 100);
this.width = this.height = size;
this.container.style.width = this.container.style.height = `${size}px`;
this.treeLayer.width = this.treeLayer.height = size;
}
setupControls() {
const setupBtn = (id, action) => {
const btn = document.getElementById(id);
// Use more efficient event handling
const handlePointerDown = () => {
action();
this.holdTimer = setInterval(action,
this.holdDelay);
};
const handlePointerUp = () => {
if(this.holdTimer) {
clearInterval(this.holdTimer);
this.holdTimer = null;
}
};
btn.addEventListener("pointerdown",
handlePointerDown);
btn.addEventListener("pointerup",
handlePointerUp);
btn.addEventListener("pointerleave",
handlePointerUp);
};
// Toggle buttons
const toggleButtons = {
"playPause": () => {
this.running = !this.running;
return this.running ? "STOP" : "PLAY";
},
"toggleTrees": () => {
this.showTrees = !this.showTrees;
this.container.classList.toggle("debug",
this.showTrees);
this.treeLayer.style.display = this.showTrees ? "block" : "none";
return this.showTrees ? "CLEAR" : "DEBUG";
}
};
Object.entries(toggleButtons)
.forEach(([id, action]) => {
document.getElementById(id).onclick = () => {
document.getElementById(id).textContent = action();
};
});
setupBtn("minus",
() =>
this.remSquares(10));
setupBtn("plus",
() =>
this.addSquares(10));
setupBtn("slow",
() =>
this.slower());
setupBtn("fast",
() =>
this.faster());
this.speedValue = document.getElementById("speed");
this.speedMultiplier = 1;
this.fpsDisplay = document.getElementById("fps");
this.frameCount = 0;
this.lastFpsUpdate = performance.now();
}
addSquares(count) {
const maxSize = Math.min(window.innerWidth,
window.innerHeight) / 27;
for(let i = 0; i < count; i++) {
const s = Math.random() * Math.round(maxSize) + 5;
const square = new Square(
Math.random() * (this.width - s),
Math.random() * (this.height - s),
s
);
this.squares.push(square);
this.elementsLayer.appendChild(square.element);
}
this.updateCount();
}
remSquares(count) {
const remove = Math.min(count,
this.squares.length);
// Use splice once with a callback instead of forEach
const removed = this.squares.splice(-remove);
for(let i = 0; i < removed.length; i++) {
this.elementsLayer.removeChild(removed[i].element);
}
this.updateCount();
}
slower() {
this.speedMultiplier = Math.max(this.speedMultiplier - 0.1,
0.1);
this.updateSpeed();
}
faster() {
this.speedMultiplier = Math.min(this.speedMultiplier + 0.1,
5.0);
this.updateSpeed();
}
updateSpeed() {
this.speedValue.textContent = `x${this.speedMultiplier.toFixed(1)}`;
}
updateCount() {
document.getElementById("elementCount").textContent
= this.squares.length.toString()
.padStart(3,
"0");
}
checkCollisions() {
this.collisions = 0;
this.collisionPairs.clear();
// Create main quadtree
const qt = QuadTree.acquire(new AABB(0,
0,
this.width,
this.height));
// Insert all squares into the quadtree
const squares = this.squares;
const squaresLength = squares.length;
for(let i = 0; i < squaresLength; i++) {
const square = squares[i];
square.isColliding = false;
qt.insert(square);
}
// Reuse query range object
const range = this.queryRange;
const queryResults = this.queryResults;
// Check for collisions
for(let i = 0; i < squaresLength; i++) {
const square = squares[i];
const s = square.data;
// Update range data directly instead of creating a new object
range.data[0] = s[0] - s[2];
range.data[1] = s[1] - s[2];
range.data[2] = s[2] * 3;
range.data[3] = s[2] * 3;
// Clear and reuse query results array
queryResults.length = 0;
qt.query(range,
queryResults);
// Process potential collisions
const resultsLength = queryResults.length;
for(let j = 0; j < resultsLength; j++) {
const other = queryResults[j];
if(other === square)
continue;
const o = other.data;
const pairKey = `${Math.min(s[5],
o[5])},${Math.max(s[5],
o[5])}`;
if(!this.collisionPairs.has(pairKey)) {
// Optimized collision check
const collision = !(
s[0] + s[2] < o[0]
|| s[0] > o[0] + o[2]
|| s[1] + s[2] < o[1]
|| s[1] > o[1] + o[2]
);
if(collision) {
this.collisionPairs.add(pairKey);
square.isColliding = other.isColliding = true;
this.collisions++;
}
}
}
}
// Update collision visual state
for(let i = 0; i < squaresLength; i++) {
const square = squares[i];
square.element.classList.toggle("colliding",
square.isColliding);
}
document.getElementById("collisions").textContent
= this.collisions.toString()
.padStart(3,
"0");
// Render debug visualization if enabled
if(this.showTrees) {
this.renderDebug(qt);
}
QuadTree.release(qt);
}
renderDebug(tree) {
const { ctx } = this;
const width = this.width;
const height = this.height;
// Get background color from CSS once
ctx.fillStyle = getComputedStyle(document.body)
.getPropertyValue("--surface");
ctx.fillRect(0,
0,
width,
height);
// Draw quadtree structure
ctx.strokeStyle = "rgba(56, 189, 248, 0.33)";
ctx.lineWidth = 0.25;
// Use iterative approach instead of recursive for better performance
const renderNode = node => {
const nodesToProcess = [node];
while(nodesToProcess.length > 0) {
const currentNode = nodesToProcess.pop();
const { data } = currentNode.boundary;
// Draw boundary rectangle
ctx.strokeRect(data[0],
data[1],
data[2],
data[3]);
// Draw points for items in this node
if(currentNode.items.length) {
ctx.fillStyle = "rgba(56, 189, 248, 0.5)";
const items = currentNode.items;
const itemsLength = items.length;
for(let i = 0; i < itemsLength; i++) {
const item = items[i];
const itemData = item.data;
ctx.beginPath();
ctx.arc(
itemData[0] + itemData[2] / 2,
itemData[1] + itemData[2] / 2,
1.5,
0,
Math.PI * 2
);
ctx.fill();
}
}
// Add child nodes to processing queue if this node is divided
if(currentNode.divided) {
nodesToProcess.push(currentNode.se);
nodesToProcess.push(currentNode.sw);
nodesToProcess.push(currentNode.ne);
nodesToProcess.push(currentNode.nw);
}
}
};
renderNode(tree);
// Draw collision query ranges
ctx.strokeStyle = "rgba(255, 100, 100, 0.27)";
ctx.lineWidth = 0.5;
// Convert to array once for iteration
const pairKeys = Array.from(this.collisionPairs);
const pairLength = pairKeys.length;
for(let i = 0; i < pairLength; i++) {
const pairKey = pairKeys[i];
const id = +pairKey.split(",")[0];
// Find square with matching ID
const squares = this.squares;
const squaresLength = squares.length;
for(let j = 0; j < squaresLength; j++) {
const square = squares[j];
if(square.data[5] === id) {
const s = square.data;
ctx.strokeRect(s[0] - s[2],
s[1] - s[2],
s[2] * 3,
s[2] * 3);
break;
}
}
}
}
updateSquares() {
const width = this.width;
const height = this.height;
const speedMultiplier = this.speedMultiplier;
const squares = this.squares;
const squaresLength = squares.length;
for(let i = 0; i < squaresLength; i++) {
const square = squares[i];
const s = square.data;
// Apply velocity
s[0] += s[3] * speedMultiplier;
s[1] += s[4] * speedMultiplier;
// Boundary checks for x-axis
if(s[0] <= 0) {
s[0] = 0;
s[3] *= -1;
}
else if(s[0] + s[2] >= width) {
s[0] = width - s[2];
s[3] *= -1;
}
// Boundary checks for y-axis
if(s[1] <= 0) {
s[1] = 0;
s[4] *= -1;
}
else if(s[1] + s[2] >= height) {
s[1] = height - s[2];
s[4] *= -1;
}
// Update DOM element position
square.element.style.transform = `translate(${s[0]}px,${s[1]}px)`;
}
}
animate(now) {
// Calculate and update FPS
if(now - this.lastFpsUpdate >= 1000) {
const fps = Math.round(this.frameCount * 1000 / (now - this.lastFpsUpdate));
this.fpsDisplay.textContent = fps.toString()
.padStart(2,
"0");
this.frameCount = 0;
this.lastFpsUpdate = now;
}
this.frameCount++;
// Schedule next frame
requestAnimationFrame(this._animateBound);
// Update simulation if running
if(this.running) {
this.updateSquares();
this.checkCollisions();
}
}
}
new Demo();