An update to Bouncing Balls II, except using a quadtree as the data structure. In informal experiments on my computer, this results in a performance increase of greater than 2x.
TODO:
<!DOCTYPE html>
<html>
<head>
<style>
body {
margin: 0;
}
</style>
</head>
<body>
<div id="stats"></div>
<div id="simulation"></div>
<script src="https://d3js.org/d3-random.v1.min.js"></script>
<script src="https://d3js.org/d3-quadtree.v1.min.js"></script>
<script src="https://unpkg.com/three@0.105.2/examples/js/libs/stats.min.js"></script>
<script src="https://unpkg.com/geometric@2/build/geometric.min.js"></script>
<script>
// The Simulation class
class Simulation {
init(opts){
this.width = opts && opts.width ? opts.width : innerWidth;
this.height = opts && opts.height ? opts.height : innerHeight;
this.center = [this.width / 2, this.height / 2];
this.data = [];
return this;
}
add(datum){
const d = datum || {};
d.pos = d.pos || [this.width / 2, this.height / 2];
d.radius = d.radius || 5;
d.angle = d.angle || 0;
d.speed = d.speed || 1;
d.index = this.data.length;
this.data.push(d);
return this;
}
tick(){
const quadtree = d3.quadtree()
.x(d => d.pos[0])
.y(d => d.pos[1])
.extent([-1, -1], [this.width + 1, this.height + 1])
.addAll(this.data);
for (let i = 0, l = this.data.length, maxRadius = 0; i < l; i++) {
const node = this.data[i];
if (node.radius > maxRadius) maxRadius = node.radius;
const r = node.radius + maxRadius,
nx1 = node.pos[0] - r,
nx2 = node.pos[0] + r,
ny1 = node.pos[1] - r,
ny2 = node.pos[1] + r;
// Visit each square in the quadtree
// x1 y1 x2 y2 constitutes the coordinates of the square
// We want to check if each square is a leaf node (has data prop)
quadtree.visit((visited, x1, y1, x2, y2) => {
if (visited.data && visited.data.index !== node.index) {
// Collision!
if (geometric.lineLength([node.pos, visited.data.pos]) < node.radius + visited.data.radius) {
// To avoid having them stick to each other,
// test if moving them in each other's angles will bring them closer or farther apart
const keep = geometric.lineLength([
geometric.pointTranslate(node.pos, node.angle, node.speed),
geometric.pointTranslate(visited.data.pos, visited.data.angle, visited.data.speed)
]),
swap = geometric.lineLength([
geometric.pointTranslate(node.pos, visited.data.angle, visited.data.speed),
geometric.pointTranslate(visited.data.pos, node.angle, node.speed)
]);
if (keep < swap){
const copy = Object.assign({}, node);
node.angle = visited.data.angle;
node.speed = visited.data.speed;
visited.data.angle = copy.angle;
visited.data.speed = copy.speed;
}
}
}
return x1 > nx2 || x2 < nx1 || y1 > ny2 || y2 < ny1;
});
// Detect sides
const wallVertical = node.pos[0] <= node.radius || node.pos[0] >= this.width - node.radius,
wallHorizontal = node.pos[1] <= node.radius || node.pos[1] >= this.height - node.radius;
if (wallVertical || wallHorizontal){
// Is it moving more towards the middle or away from it?
const t0 = geometric.pointTranslate(node.pos, node.angle, node.speed);
const l0 = geometric.lineLength([this.center, t0]);
const reflected = geometric.angleReflect(node.angle, wallVertical ? 90 : 0);
const t1 = geometric.pointTranslate(node.pos, reflected, node.speed);
const l1 = geometric.lineLength([this.center, t1]);
if (l1 < l0) node.angle = reflected;
}
node.pos = geometric.pointTranslate(node.pos, node.angle, node.speed);
}
}
}
// Initiate a simulation
const mySimulation = (_ => {
const simulation = new Simulation();
// Initialize this simulation with simulation.init
// You can pass an optional configuration object to init with the properties:
// - width
// - height
simulation.init();
// We'll create 1,000 circles of random radii, moving in random directions at random speeds.
for (let i = 0; i < 1000; i++){
const radius = d3.randomUniform(2, 5)();
// Add a circle to your simulation with simulation.add
simulation.add({
speed: d3.randomUniform(1, 3)(),
angle: d3.randomUniform(0, 360)(),
pos: [
d3.randomUniform(radius, simulation.width - radius)(),
d3.randomUniform(radius, simulation.height - radius)()
],
radius
});
}
return simulation;
})();
// Stats box
const stats = (_ => {
const stats = new Stats();
stats.domElement.style.position = "absolute";
stats.domElement.style.left = "0px";
stats.domElement.style.top = "0px";
document.getElementById("stats").appendChild(stats.domElement);
return stats;
})();
// Draw the simulation
const wrapper = document.getElementById("simulation");
const canvas = document.createElement("canvas");
canvas.width = mySimulation.width;
canvas.height = mySimulation.height;
canvas.style.background = "black";
wrapper.appendChild(canvas);
const ctx = canvas.getContext("2d");
ctx.fillStyle = "steelblue";
ctx.strokeStyle = "white";
function tick(){
requestAnimationFrame(tick);
ctx.clearRect(0, 0, mySimulation.width, mySimulation.height);
// The simulation.tick method advances the simulation one tick
mySimulation.tick();
for (let i = 0, l = mySimulation.data.length; i < l; i++){
const d = mySimulation.data[i];
ctx.beginPath();
ctx.arc(...d.pos, d.radius, 0, 2 * Math.PI);
ctx.fill();
ctx.stroke();
}
stats.update();
}
tick();
</script>
</body>
</html>