Bouncing Balls III

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:

When circles collide, they simply swap angles and speeds. This gets the job done, but it does not let circles glance off of each other. I need a more realistic method of transferring energy when they collide.
Canvas is fast, but WebGL is faster.

<!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>

https://d3js.org/d3-random.v1.min.js

https://d3js.org/d3-quadtree.v1.min.js

https://unpkg.com/three@0.105.2/examples/js/libs/stats.min.js

https://unpkg.com/geometric@2/build/geometric.min.js