| license: gpl-3.0 |
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> |
