7
\$\begingroup\$

I am implementing a simulation of colliding disks (ideal 2D billiard balls) in JavaScript.

I follow an event-driven algorithm that avoids discretizing time; the algorithm goes as follows at each step:

  • Compute the moment of the next collision (with walls or between two disks)
  • Translate the spheres during that time interval
  • Update the disks velocities following the collision, and start again

I use JavaScript and d3.js; having little experience with these, I would appreciate a review of the code, in particular:

  1. How I made the code loop (the loop function is called once the transitions have all ended).
  2. If there is another structuring to the code that would make it more clear / efficient.

Here is a working snippet.

<!DOCTYPE html>
<meta charset="utf-8">
<style>
svg {
  border:1px solid black;
}
</style>
<script src="//d3js.org/d3.v3.min.js"></script>
<body>
<script>
var timescale = 800.;
var width = 300,
    height = 300,
    radius = 0.15;
var svg = d3.select("body").append("svg")
    .attr("class", "disk")
    .attr("width", width)
    .attr("height", height)
    .attr("viewBox", "0 0 1 1");

var c10 = d3.scale.category10();

var init_data = [[radius, 0.25, 0.25, Math.random() - 0.5, Math.random() - 0.5],
                 [radius, 0.75, 0.25, Math.random() - 0.5, Math.random() - 0.5],
                 [radius, 0.25, 0.75, Math.random() - 0.5, Math.random() - 0.5],
                 [radius, 0.75, 0.75, Math.random() - 0.5, Math.random() - 0.5]
                ];

var circles = svg.selectAll(".disk")
  .data(init_data)
  .enter().append("circle")
    .attr("r", function(d) { return d[0] })
    .attr("cx", function(d) { return d[1] })
    .attr("cy", function(d) { return d[2] })
    .attr("fill", c10);

function next_event(circles) {
  var nevent = [Infinity];
  var data = circles.data();
  for (var i = 0; i < data.length; i++) {
    var r = data[i][0],
        x = data[i][1],
        y = data[i][2],
        dx = data[i][3],
        dy = data[i][4];
    var dt;
    // x-wall
    dt = ( (dx >= 0 ? (1. - r) : r) - x ) / dx;
    if (dt < nevent[0])
      nevent = [dt, "wall", "x", i];
    // y-wall
    dt = ( (dy >= 0 ? (1. - r) : r) - y ) / dy;
    if (dt < nevent[0])
      nevent = [dt, "wall", "y", i];
    for (var j = i + 1; j < data.length; j++) {
      // pair collisions
      var x2 = data[j][1],
          y2 = data[j][2],
          dx2 = data[j][3],
          dy2 = data[j][4];
      var diffx = x2 - x,
          diffy = y2 - y,
          diffdx = dx2 - dx,
          diffdy = dy2 - dy;
      var scalarprod = (diffx * diffdx + diffy * diffdy);
      var gamma = Math.pow(scalarprod, 2)
                  - (diffdx * diffdx + diffdy * diffdy) * (diffx * diffx + diffy * diffy - 4 * Math.pow(r, 2));
      if ( gamma >= 0 && scalarprod <= 0 ) {
        var tpair = -( scalarprod + Math.sqrt(gamma) ) / (diffdx * diffdx + diffdy * diffdy);
        if (tpair < nevent[0] ) {
          nevent = [tpair, "pair", i, j];
        }
      }
    }
  }
  return nevent
}


function update(circles, nevent) {
  circles.each(function (d, i) { 
               d[1] = d[1] + nevent[0] * d[3];
               d[2] = d[2] + nevent[0] * d[4];
               });
  if (nevent[1] == "wall") {
    circles.each(function (d, i) { 
                    if (i == nevent[3]){
                      switch(nevent[2]) {
                        case "x":
                          d[3] *= -1;
                          break;
                        case "y":
                          d[4] *= -1;
                          break;
                      }
                    } 
                 });
  } else if (nevent[1] == "pair") {
    var i = nevent[2],
        j = nevent[3];
    var data = circles.data();
    var x = data[i][1],
        y = data[i][2],
        dx = data[i][3],
        dy = data[i][4];
    var x2 = data[j][1],
        y2 = data[j][2],
        dx2 = data[j][3],
        dy2 = data[j][4];
    var diffx = x2 - x,
        diffy = y2 - y,
        diffdx = dx2 - dx,
        diffdy = dy2 - dy;
    var ex = diffx / Math.sqrt(diffx*diffx + diffy*diffy),
        ey = diffy / Math.sqrt(diffx*diffx + diffy*diffy);

    circles.each(function (d, k) { 
                    if (k == i) {
                      d[3] += ex * (diffdx * ex + diffdy * ey);
                      d[4] += ey * (diffdx * ex + diffdy * ey);
                    } else if (k == j) {
                      d[3] -= ex * (diffdx * ex + diffdy * ey);
                      d[4] -= ey * (diffdx * ex + diffdy * ey);
                    }
                 });
  }
}

function endall(transition, callback) { 
    if (transition.size() === 0) { callback() }
    var n = 0; 
    transition 
        .each(function() { ++n; }) 
        .each("end", function() { if (!--n) callback.apply(this, arguments); }); 
  } 

function loop(circles){
  var nevent = next_event(circles);
  trans = circles.transition().duration(nevent[0] * timescale).ease("linear")
       .attr("cx", function(d){
         return d[1] + nevent[0] * d[3];
       })
       .attr("cy", function(d){
         return d[2] + nevent[0] * d[4];
       })
       .call(endall, function() { update(circles, nevent); loop(circles) })
}
loop(circles);


</script>
</body>

\$\endgroup\$
3
  • \$\begingroup\$ Welcome to Code Review! Good job on your first question. \$\endgroup\$
    – SirPython
    Commented Mar 30, 2016 at 0:56
  • \$\begingroup\$ This is really good code and I don't see any major improvements. You could turn scalarprod() into a function and use fewer variables, but that's really minor. You could also sort to find the next event (instead of if (dt < nevent[0])), but really all of that is just nitpicking. \$\endgroup\$
    – user1149
    Commented Mar 30, 2016 at 19:24
  • \$\begingroup\$ I see @BarryCarter; well, still good to have some advice that I did things right (for instance, I wasn't sure that I looped the right way). Thanks for the attention ;) \$\endgroup\$
    – Maxim
    Commented Mar 31, 2016 at 7:37

1 Answer 1

Reset to default
2
\$\begingroup\$

Some issues and solutions:

  • Using arrays for key-value data

    What does each element of one of the init_data mean? What is accessed by data[j][4]? Instead of modelling each circle as an array with the fields stored as indices 0–4, it would be clearer to make each an object with named fields radius, x, y, dx and dy. You can initialise them about as concisely (but more clearly) by declaring a function to construct them from arguments, and calling that 4 times.

  • Repetitive .attr calls

    D3 supports passing in an object to selection.attr. It's equivalent to 4 separate calls:

    [ ... ]
.append('circle').attr({
    r:  function(d) { return d[0] },
    cx: function(d) { return d[1] },
    cy: function(d) { return d[2] },
    fill: c10
})

  • Verbose vector logic

    All that nested arithmetic for the collision detection is currently harder than necessary to understand. A vector library would have the right classes and abstract operations built into it to make all those into just a few lines.

  • Calling circles.each to update data

    In D3-land the assumption is usually that selections don't modify data, only read and render it. You could instead call init_data.forEach, which is logically equivalent, but clearer about what arrays contents are being changed and going with existing expectations.

  • Non-commented collision detection logic

    Your question's explanation is good, but that explanation should be in the code. It is much easier to read vector arithmetic when you understand the general idea of what it's trying to do. Kudos for all of the ones you have already (like // x-wall, etc): debugging other people's collision code is so painful that any comments at all are are like desert oases.

  • Non-commented transition endall trick

    That's super nasty, but I know it's necessary! :) It might be best to link to that answer everybody probably copypastes the implementation from, for the benefit of readers of your code who haven't yet faced this edge case.

\$\endgroup\$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.