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