DHTML version of "simulation of physical systems"

Kragen Javier Sitaker Sat, 09 Dec 2006 00:37:11 -0800

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>

<p>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.</p>

<p>Frame #<span id="frameno_display">none yet</span>.  Running at
<span id="tups">???</span> time units per step; each step takes <span
id="calcms">???</span>ms to calculate (<span
id="calcms_avg">???</span>ms avg so far) and <span
id="drawms">???</span>ms to draw, then <span id="weirdms">???</span>ms
after drawing doing other unknown things.  (To keep from bogging the
machine down, there's another idle pause after that, of <span
id="total">???</span>ms.)</p>

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

<p>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.</p>

</body></html>

DHTML version of "simulation of physical systems"

Reply via email to