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

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

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.

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.

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.

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.

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.

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.

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.

random inside circle

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

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