DHTML version of "simulation of physical systems"

Sat Dec 9 03:37:01 EST 2006

In the interest of making kragen-hacks posts easier to enjoy, I'm
translating 74 of them into dynamic HTML to reduce the hassle of
running them.  This one is, in a vague sense, a physical simulation.
Probably requires Mozilla, might work in Opera, Konqueror, or Safari.

This will eventually be at http://pobox.com/~kragen/sw/dots.html.

<html><head><title>Generate a bunch of random dots. Make them move.</title>
<script type="text/javascript">
// Translated from an old kragen-hacks post "simulation of physical
// systems", 1998-11-14, in Perl. It's kind of maddening reading and
// especially translating this code, as I wouldn't write it nearly as
// badly these days.

// However, it's really remarkable how slow this code is.  On my
// 1.1GHz laptop, with 100 dots, it reports, "Each step takes 586ms to
// calculate (450.44ms avg so far) and 70ms to draw, then 195ms after
// drawing doing other unknown things."  That's something like 5 times
// slower than the Perl+PostScript version, despite some algorithmic
// optimization and some micro-optimization.  The NxN inner loop where
// it calculates forces among all the dot pairs does seem to be the
// bottleneck, since the calculation time goes down as N^2 if I reduce
// the number of dots.

// By comparison, the Perl+PostScript version runs through 1000 frames
// in 2 min 20.5 seconds, 140.5 seconds, which is about 140ms per
// frame --- and in theory it included the time to draw the results,
// although that mode of output doesn't seem to work as well on my
// current machine as it did on the machine where I developed it.

// JavaScript on my machine seems to need something like 15
// microseconds per multiply --- i.e. 15000 instructions..

// Bugs:
// - dots collide and then blow up
// - in general, when timesteps get too big, things tend to blow up
//   --- and some of the dots never make it back
// - trail lengths are a particular number of simulation steps, not a
//   particular number of time units
// - trails that cross wraparound walls draw strangely
// - there should be a dot object --- to heck with all these arrays of
//   arrays
// - it's way too slow!

function $(id) { return document.getElementById(id) }
function forEachRange(n, func) {
  for (var ii = 0; ii < n; ii++) { func(ii) }
}
function forEach(list, func) {
  forEachRange(list.length, function(ii) { func(list[ii]) })
}
function map(func, list) {
  var rv = []
  forEach(list, function(item) { rv.push(func(item)) })
  return rv
}
function range(n) {
  var rv = []
  forEachRange(n, function(ii) { rv.push(ii) })
  return rv
}
function rand(n) { return Math.floor(Math.random() * n) }
function setTextContent(node, value) {
  while (node.firstChild) node.removeChild(node.firstChild)
  node.appendChild(document.createTextNode(value))
}

var max_x = 600
var max_y = 400
function randompoint() {
  // Initially the points are confined to a small part of the canvas
  // to make them act more interestingly.
  return [ rand(max_x / 2), rand(max_y / 2) ]
}
// the canvas arc function takes six arguments:

// center x, center y, radius, start angle (radians clockwise from right),
// end angle, boolean saying whether to draw counterclockwise.

// PostScript's arc function is much the same, but doesn't have that
// last argument (it always draws counterclockwise) and takes angles
// in degrees, counterclockwise from right.  But I suspect I wasn't up
// to discovering that experimentally when I first wrote this program,
// which is why my original definition of "dotat" depended on round
// line-caps.

function dotat(ctx, point) {
  ctx.beginPath()
  ctx.arc(point[0], point[1], 1.5, 0, Math.PI*2, 0)
  ctx.fill()
}

// Probably these would be better as properties of a dot object:
// position, paths, velocities.  But I'm following the Perl original,
// albeit with some concessions for dynamicism.

// var dots, paths, velocities, time_units_per_step, frameno, delta_dots;

function randvelocity() {
  return [rand(20)-10, rand(20)-10]
}

function set_number_of_dots(n) {  
  while (dots.length > n) {
    dots.pop()
    velocities.pop()
    paths.pop()
    delta_dots.pop()
  }
  while (dots.length < n) {
    var npoint = randompoint()
    dots.push(npoint)
    paths.push(map(function() { 
      return [npoint[0], npoint[1]]
    }, range(5)))
    velocities.push(randvelocity())
    delta_dots.push([0, 0])
  }
}

function initialize() {
  $('thecanvas').width = max_x
  $('thecanvas').height = max_y
  dots = []
  paths = []
  velocities = []
  delta_dots = []

  set_number_of_dots(50)

  frameno = 1
  time_units_per_step = null
}

function round(n) { return Math.round(n * 100) / 100 }

function showframe() {
  setTextContent($('frameno_display'), frameno)
  frameno++
  setTextContent($('tups'), round(time_units_per_step))
  var cvs = $('thecanvas')
  var ctx = cvs.getContext('2d')
  ctx.clearRect(0, 0, cvs.width, cvs.height)
  ctx.strokeStyle = "#777777"
  forEach(paths, function(path) {
    var firstpoint = path[0]
    ctx.beginPath()
    ctx.moveTo(firstpoint[0], firstpoint[1])
    forEachRange(path.length - 1, function(ii) {
      var point = path[ii + 1]
      ctx.lineTo(point[0], point[1])
    })
    ctx.stroke()
  })
  ctx.fillStyle = "#777777"
  forEach(dots, function(dot) { dotat(ctx, dot) })
}

function hypsq(point) {
  return point[0]*point[0] + point[1]*point[1]
}

/* an inverse square law. */
/* To cut down on error, each timestep is either */
/* four space units for the fastest particle, or four acceleration units for */
/* the particle that's accelerating fastest. */
var law_constant = 20
var handle_walls
var friction_per_time_unit = 0.1
var inertia = true
function make_dots_repel() {
  for (ii = 0; ii < dots.length; ii++) {
    delta_dots[ii][0] = 0
    delta_dots[ii][1] = 0
  }
  var ii, jj, idot, jdot, delta, dx, dy, rsq, denom;
  // delta = [0, 0]
  for (ii = 1; ii < dots.length; ii++) {
    idot = dots[ii]
    for (jj = 0; jj < ii; jj++) {
      jdot = dots[jj]
      //delta[0] = idot[0] - jdot[0]
      //delta[1] = idot[1] - jdot[1]
      dx = idot[0] - jdot[0]
      dy = idot[1] - jdot[1]
      // inlining just this one function call speeds up this routine
      // by 45% on 50 points:
      // rsq = hypsq(delta)
      // rsq = delta[0] * delta[0] + delta[1] * delta[1]
      rsq = dx*dx + dy*dy
      if (rsq < 1) rsq = 1  // what was I thinking when I wrote this?
      denom = rsq * Math.sqrt(rsq)
      // force in x direction is x direction divided by
      // r; x direction is delta x divided by r.
      delta_dots[ii][0] += dx/denom
      delta_dots[ii][1] += dy/denom
      delta_dots[jj][0] -= dx/denom
      delta_dots[jj][1] -= dy/denom
    }
  }
  // Each "time" step, we move the fastest particle at most 1 step
  // and accelerate the fastest-accelerating particle at most 1
  // unit; so we adjust the size of the timestep accordingly.
  var velsq, accelsq, maxchangesq = 0
  if (inertia) {
    for (ii = 0; ii < dots.length; ii++) {
      velsq = hypsq(velocities[ii])
      if (velsq > maxchangesq) maxchangesq = velsq
    }
  }
  for (ii = 0; ii < dots.length; ii++) {
    accelsq = hypsq(delta_dots[ii])
    if (accelsq > maxchangesq) maxchangesq = accelsq
  }
  var scale = 4/Math.sqrt(maxchangesq)
  time_units_per_step = scale
  // NOTE: my original code had a bug here --- this line was meant to
  // make friction per time-step not vary with time-step size, but
  // since I wrote 1-(0.1**tups) instead of ((1-0.1)**tups), I was
  // getting enormous friction when time steps were short.
  var friction_factor = Math.pow((1 - friction_per_time_unit), 
                                 time_units_per_step)
  var where_to_apply_force = inertia ? velocities : dots;
  forEachRange(dots.length, function(ii) {
    velocities[ii][0] *= friction_factor
    velocities[ii][1] *= friction_factor
    apply_force(scale, where_to_apply_force[ii], delta_dots[ii])
    if (inertia) {
      dots[ii][0] += velocities[ii][0] * scale
      dots[ii][1] += velocities[ii][1] * scale
    }
    handle_walls(dots[ii], velocities[ii])
    paths[ii].shift()
    paths[ii].push([dots[ii][0], dots[ii][1]])
  })
}

function apply_force_repel(timescale, thing, force) {
  thing[0] += force[0] * timescale * law_constant
  thing[1] += force[1] * timescale * law_constant
}
apply_force = apply_force_repel

function apply_force_rotate(timescale, thing, force) {
  thing[0] += force[1] * timescale * law_constant
  thing[1] += -force[0] * timescale * law_constant
}

function apply_force_attract(timescale, thing, force) {
  thing[0] -= force[0] * timescale * law_constant
  thing[1] -= force[1] * timescale * law_constant
}

function apply_force_atrepel(timescale, thing, force) {
  thing[0] += force[0] * timescale * law_constant
  thing[1] -= force[1] * timescale * law_constant
}

function handle_walls_stopping(dot, velocity) {
  if (dot[0] > max_x) {
    dot[0] = max_x
    velocity[0] = 0
  }
  if (dot[1] > max_y) {
    dot[1] = max_y
    velocity[1] = 0
  }
  if (dot[0] < 0) {
    dot[0] = 0
    velocity[0] = 0
  }
  if (dot[1] < 0) {
    dot[1] = 0
    velocity[1] = 0
  }
}

handle_walls = handle_walls_stopping

function handle_walls_bouncy(dot, velocity) {
  if (dot[0] > max_x) {
    dot[0] = max_x - (dot[0] - max_x)
    velocity[0] = -velocity[0]
  }
  if (dot[1] > max_y) {
    dot[1] = max_y - (dot[1] - max_y)
    velocity[1] = -velocity[1]
  }
  if (dot[0] < 0) {
    dot[0] = -dot[0]
    velocity[0] = -velocity[0]
  }
  if (dot[1] < 0) {
    dot[1] = -dot[1]
    velocity[1] = -velocity[1]
  }
}

function handle_walls_wrap(dot, velocity) {
  if (dot[0] > max_x) dot[0] -= max_x 
  if (dot[1] > max_y) dot[1] -= max_y
  if (dot[0] < 0) dot[0] += max_x 
  if (dot[1] < 0) dot[1] += max_y
}

function setwalls(select) {
  var val = select.options[select.selectedIndex].value
  handle_walls = ({
    stopping: handle_walls_stopping,
    bouncy: handle_walls_bouncy,
    wrap: handle_walls_wrap,
  })[val]
}

function setdots(select) {
  set_number_of_dots(parseInt(select.options[select.selectedIndex].value))
}

var idleratio = 1
function setidleratio(select) {
  idleratio = parseInt(select.options[select.selectedIndex].value)
}

function setfriction(select) {
  friction_per_time_unit = 
      parseFloat(select.options[select.selectedIndex].value)
}

function setforce(select) {
  apply_force = ({
    repel: apply_force_repel,
    rotate: apply_force_rotate,
    attract: apply_force_attract,
    atrepel: apply_force_atrepel,
  })[select.options[select.selectedIndex].value]
}  

function setinertia(checkbox) {
  inertia = checkbox.checked
}

function timeit(thunk) {
  var start = new Date()
  thunk()
  return (new Date()).getTime() - start.getTime()
}

var total_calcms = 0
var nturns = 0
function animate() {
  var start = new Date()
  var calcms = timeit(make_dots_repel)
  setTextContent($('calcms'), calcms)
  total_calcms += calcms
  nturns += 1
  setTextContent($('calcms_avg'), round(total_calcms / nturns))
  setTextContent($('drawms'), timeit(showframe))
  var mysterious_time = new Date()
  function reschedule() {
    // We run this guy from a setTimeout-0 because apparently the
    // actual work done inside the showframe function is almost an
    // order of magnitude smaller (60ms vs. 500ms) than some work that
    // it apparently defers for later.  I think it's horrible and
    // appalling that my browser's canvas can't display 100 dots in
    // less than 500ms, but whatever.  This keeps it from bogging down
    // the machine too much.
    var now = new Date()
    setTextContent($('weirdms'), now.getTime() - mysterious_time.getTime())
    var duration = now.getTime() - start.getTime()
    var idletime = duration * idleratio
    setTextContent($('total'), idletime)
    setTimeout(animate, idletime)
  }
  setTimeout(reschedule, 0)
}

function start_animation() {
 initialize()
 showframe()
 animate()
}
</script>
</head><body onLoad="start_animation()">
<h1>Generate a bunch of random dots. Make them move.</h1>

I'm really terribly sorry this is so incredibly slow. I don't know
how Mozilla managed to make JavaScript ten times slower than Perl, but
I guess JavaScript just isn't the best possible language for numerical
simulations. Consequently this isn't as captivating as the
Perl+PostScript version was.

Frame #none yet. Running at
??? time units per step; each step takes ???ms to calculate (???ms avg so far) and ???ms to draw, then ???ms
after drawing doing other unknown things. (To keep from bogging the
machine down, there's another idle pause after that, of ???ms.)

<div style="float: right"><form>
<select id="walls" onchange="setwalls(this)">
<option value="stopping" selected="selected">Stopping walls</option>
<option value="bouncy">Bouncy walls</option>
<option value="wrap">Wraparound walls</option>
</select>
<br />
<select id="force" onchange="setforce(this)">
<option value="repel">Inverse square repulsion</option>
<option value="rotate">Inverse square tangential</option>
<option value="attract">Inverse square attraction</option>
<option value="atrepel">Vertical attract, horizontal repel</option>
</select>
<br />
<select id="ndots" onchange="setdots(this)">
<option>2</option>
<option>3</option>
<option>10</option>
<option>20</option>
<option selected="selected">50</option>
<option>100</option>
<option>200</option>
</select> dots
<br />
<input type="checkbox" id="inertia" checked="checked" 
onchange="setinertia(this)"><label for="inertia"
>Dots have inertia</label>
<br />
<select id="friction" onchange="setfriction(this)">
<option value="0">No friction</option>
<option value="0.01" selected="selected">1% friction per time unit</option>
<option value="0.1" selected="selected">10% friction per time unit</option>
<option value="0.5">50% friction per time unit</option>
<option value="0.9">90% friction per time unit</option>
<option value="0.99">99% friction per time unit</option>
<option value="1">100% friction per time unit</option>
</select> 
<br />
<select id="dutycycle" onchange="setidleratio(this)">
<option value="19">5%</option>
<option value="9">10%</option>
<option value="1" selected="selected">50%</option>
<option value="0">100%</option>
</select> duty cycle on CPU
<br />
</div>

<canvas width="200" height="200" id="thecanvas"></canvas>

If this line is right underneath the other text, without several
lines of space in between, your browser probably doesn't support
&lt;canvas&gt;. If there aren't dots moving in it, maybe your browser
has some other problem, like having JavaScript turned off, or maybe my
code is broken.

</body></html>