While creating cv-viz: Virus infection simulation with D3.js there were a few D3 challenges I had to figure out. These snippets look at dealing with collisions in a force-directed simulation. You can play with the simulation live here. https://cv-viz.web.app/

All the source code is here https://github.com/brucemcpherson/cvviz

Motivation

In the simulation, people move around either within a place (a house or a public place), or between places. The simulation keeps people within a place by forcing them to try to stay close to the center of the circle representing the place they are supposed to be visiting.

That’s straightforward enough with this, where bb represents the bounding box of the circle’s parent – in this case the place they are currently at

    // this forces to center of parent
    .force("forceX", d3ForceX().strength(vp.strengthX).x(d=>{
      return d.bb.x
    }))
    .force("forceY", d3ForceY().strength(vp.strengthY).y(d=>{
      return d.bb.y
    }))

Balancing the strength of this force with a negative charge to keep them apart

    .force('charge', d3ForceManyBody().strength(vp.charge/2))

achieves this kind of effect, captured here in movement as it’s disturbed  by people arriving at or leaving a place

d3.js coronavirus viz

or by collisions, which are detected like this.

 .force('collide', d3ForceCollide(d=> { .... etc

People in movement are in the middle of a transition from one place to another and although still part of the force simulation, are exempted from most of these forces by selectively applying movements provoked by the simulation to those nodes, not in transition.

const tickMove  = (g) => {
  // only move things around with the dim if its not transitioning
  // go back to regular size if we've been infected for more than half a day

  if(g){
    g.filter(d=>d.simNode && !d.simNode.isMoving).each(function(d){
      const self = d3Select(this)
      self.attr("cx", d.x).attr("cy", d.y)
    })
  }
   
}

However, collisions for nodes in both states are required, since this simulation is all about what happens when 2 nodes meet in transit (either moving about inside a place or moving between places).

Detecting force collisions

The .force(‘collide’,…)  function provides a mechanism to force a repulsion when a collision is detected between two nodes. However, it doesn’t easily provide a way to detect which nodes are colliding (each node will report a collision separately). However, my sim needs to process the outcome of such an encounter in addition to detecting it.

 // find the nearest nodes within collision padding
  .force('collide', d3ForceCollide(d=> {    
      const pd = vp.collisionPadding(d)
      
      // we only do a sample, as it wuld be too heavy to check them all
      const {collisionTween} = vp
      const check = collisionTween && collisionTween  >= Math.random() 

      if (check) {
        const {collider, nearest} = findNearest(d, pd)
        if(!nearest) {
          // this can happen as we're ignoring collisions between those not in the same current state
        } else {
          // now we can go for an infection
         
          const inf = infect(collider,nearest.t)
          if (inf.infected) {
            inf.ot
              .style("fill",inf.target.props.color)
              .attr("r", expand(inf.target.simNode.radius))
              .transition('postinfection')
              .attr("r", inf.target.simNode.radius)
              .duration(5000)
          }

        }
      }
      return pd  
     })

Let’s take a look at the detail

Collision padding

The definition of a collision needs to take into account the radius of the node, along with some padding. This is returned as a clue to the repulsion needed to push the nodes apart following a collision.

Collision tween

Collisions are checked at every tick. This would be way too much processing to happen every single tick, so collision tween is a probability setting that decides whether or not to treat a collision as an ‘encounter’ and go on to process an outcome. I use this as a metaphor for compliance (face masks, social distancing etc), so if the simulation is set to low compliance, more collisions will be treated as an encounter, and therefore as infection opportunities.

Find nearest

It’s odd that the two colliding nodes are not passed to the collide function, but they are not. There is a .find function in d3 that can find the nearest node to a given co-ordinate, but firstly it only returns 1 node, and secondly, that node will be the node itself being processed, so it’s not of any help in finding the nearest collider. This function looks at all the nodes and finds the nearest (that’s not the node itself) nodes within collision distance. Another wrinkle is that nodes in transition (people moving between places) don’t have their current position available anywhere, so elsewhere in the sim, transitions have a tween function to interpolate and store their transition position (zx and xy here) at any given moment. This function will return the collider (the node being examined), and the nearest node within collision distance.

const findNearest = (d,pd) => {
  let all = []
  let collider = null
  const {simNode:sd} = d
  getSelection({type:'person'})
  .filter(f=>f.simNode.currentIdx === sd.currentIdx)
  .each(function(f) {
    const t = d3Select(this)
    const {simNode:sf} = f

    if (sf.idx === sd.idx) {
      collider = t
    } else {
      const cx = sf.isMoving ? f.zx : f.x  
      const cy = sf.isMoving ? f.zy : f.y 
      const distance = Math.hypot(d.x-cx,d.y-cy)
      if(distance <= pd*2) {
        all.push({
          distance,
          t
        })
      }
    }
  })
  // just interested in the nearest one
  return  {
    collider,
    nearest: all.sort((a,b) => a.distance - b.distance)[0]
  }
}

An encounter

An encounter is declared when two nodes are within collision distance. Various probabilities and biases are applied in the infect function which I won’t go into here, but the outcome is that either an infection occurs or it doesn’t. If it does, then we need to visually indicate it with a permanent transition in color and a temporary one in size.

expand

This just increases the size (area not radius which would be too much) of the node.

  export const expand = (r,size) => {
    const area =  Math.PI * r * r
    return Math.sqrt(area*(size || Math.PI/2 )/Math.PI)
  }

Transition tweening

Elsewhere in the sim, from time to time a person leaves a place to visit another. This causes their node to be exempted from the force simulation in terms of movement for the duration of their journey, but they are still able to infect or be infected. The same mechanism for collision processing happens (they are officially still part of the force simulation), but we need to track transition progress to detect the nearest nodes, and for that we can use a tween function. This means that the tween co-ordinates need to be interpolated manually, so they can be captured for use in the collision processing.

  return function (t) {
    const self = d3Select(this)
    // have to redo the interpolator each time in case we were diverted somewhere else
    const ix = d3Interpolate(gat(self,'cx'), w.tcx)
    const iy = d3Interpolate(gat(self,'cy'), w.tcy)
    const d = self.datum()
    // these are the intermediate transtion vaues which may be required elsewhere
    d.zx = ix(t)
    d.zy = iy(t)
    d.progress = t
    self.attr('cy',d.zy).attr('cx',d.zx)
    return d
  }
}

At the beginning of the journey, tcx and tcy were set to the destination co-ordinates (random positions within the destination node). The duration is calculated from many factors which I won’t go into here.

  // setup where we're going,and how long its expected to take
        const xy =  randomInsideCircle ({
          x: place.x,
          y: place.y, 
          radius: place.simNode.radius - person.simNode.radius
        })
        person.tcx = xy.x
        person.tcy = xy.y
        
      
        const dur = duration(person)
        const delay = dur/Math.PI * Math.random()
        person.targetEnd =  dur  + delay + new Date().getTime()


          x.transition()
            .attr('cx',person.tcx)
            .attr('cy',person.tcy)

          .duration(dur)
          .ease(d3EaseSinInOut)
          .delay(delay)

          // need to do tweening to record intermediate positions for collistion detecting
          .tween('collision', zpos)

          // detect the end of journey
          .on('end', function () {
            const n = d3Select(this)
            const d = n.datum()
            n.attr("cx", d.tcx)
            n.attr("cy", d.tcy)
    
            d.x = d.tcx
            d.y = d.tcy
            d.simNode.currentIdx = d.simNode.visitIdx === -1 ? d.simNode.homeIdx : d.simNode.visitIdx
            const eventType = d.simNode.isAtHome ? 'home-ends' : 'visit-ends'
            addLog ({...log,eventType})
            n.datum(d)

          })

random inside circle

Calculates a centre point inside the destination node that can accommodate the radius of the node going there

  export const randomInsideCircle = ({x,y,radius}) => {
    // generate a random angle
    const angle = Math.random() * 2 * Math.PI;
    // and a random radius
    const rs = Math.random() * radius * radius
    const rq = Math.sqrt(rs)
    const rx = rq * Math.cos(angle)
    const ry = rq * Math.sin(angle)
    const xy = {
      x: rx + x,
      y: ry + y,
    }

    return xy
  }

Summary

The force-directed simulation provides a way of holding things in position, yet allowing them some movement to handle other nodes coming and going, and its collision detecting capability provides a hook for cross node infection.

The tech

You can play with the simulation here. https://cv-viz.web.app/

All the source code is here https://github.com/brucemcpherson/cvviz