Skip to content

Instantly share code, notes, and snippets.

@lorenzopub
Created February 26, 2018 07:21
Show Gist options
  • Save lorenzopub/9a0b56fddec0760d74eace2823d59a07 to your computer and use it in GitHub Desktop.
Save lorenzopub/9a0b56fddec0760d74eace2823d59a07 to your computer and use it in GitHub Desktop.
Rectangular Collision Detection
license: mit

Block-a-Day #8. Adapts the core library's forceCollide force to work with rectangles instead of circles. Note that collide.radius([radius]) is replaced with collide.size([size]), which should return an array in the format [width, height].

Nate Bates's block provided a useful reference. The bounding force was created for yesterday's block (although note the addition of checks on lines 182-183 and 188-189, which prevent a rectangle from getting trapped out of bounds).

What I Learned: I now have at least some sense for what every line of forceCollide is doing. Whether I understand it all, well, that's another matter.

What I'd Do With More Time: There's at least one bug that can fail to detect the overlap of two rectangles, causing them to eventually rebound with too much force. I went back and realized where the problem was, cleaning up some other stuff too.

Block-a-Day

Just what it sounds like. For fifteen days, I will make a D3.js v4 block every single day. Rules:

  1. Ideas over implementation. Do something novel, don't sweat the details.
  2. No more than two hours can be spent on coding (give or take).
  3. Every. Single. Day.

Previously

forked from cmgiven's block: Rectangular Collision Detection

<!DOCTYPE html>
<meta charset="utf-8">
<body>
<script src="//d3js.org/d3.v4.min.js"></script>
<script>
var width = 960
var height = 500
var numParticles = 20
var maxVelocity = 8
var color = d3.scaleOrdinal().range(d3.schemeCategory20)
var nodes = Array.apply(null, Array(numParticles)).map(function (_, i) {
var size = Math.random() * 60 + 20
var velocity = Math.random() * 2 + 1
var angle = Math.random() * 360
return {
x: Math.random() * (width - size),
y: Math.random() * (height - size),
vx: velocity * Math.cos(angle * Math.PI / 180),
vy: velocity * Math.sin(angle * Math.PI / 180),
size: size,
fill: color(i)
}
})
var drag = d3.drag()
.on('start', dragStarted)
.on('drag', dragged)
.on('end', dragEnded)
var svg = d3.select('body').append('svg')
var rects = svg
.attr('width', width)
.attr('height', height)
.selectAll('rect')
.data(nodes)
.enter().append('rect')
.style('fill', function (d) { return d.fill })
.attr('width', function (d) { return d.size })
.attr('height', function (d) { return d.size })
.attr('x', function (d) { return d.x })
.attr('y', function (d) { return d.y })
.call(drag)
var collisionForce = rectCollide()
.size(function (d) { return [d.size, d.size] })
var boxForce = boundedBox()
.bounds([[0, 0], [width, height]])
.size(function (d) { return [d.size, d.size] })
d3.forceSimulation()
.velocityDecay(0)
.alphaTarget(1)
.on('tick', ticked)
.force('box', boxForce)
.force('collision', collisionForce)
.nodes(nodes)
function rectCollide() {
var nodes, sizes, masses
var size = constant([0, 0])
var strength = 1
var iterations = 1
function force() {
var node, size, mass, xi, yi
var i = -1
while (++i < iterations) { iterate() }
function iterate() {
var j = -1
var tree = d3.quadtree(nodes, xCenter, yCenter).visitAfter(prepare)
while (++j < nodes.length) {
node = nodes[j]
size = sizes[j]
mass = masses[j]
xi = xCenter(node)
yi = yCenter(node)
tree.visit(apply)
}
}
function apply(quad, x0, y0, x1, y1) {
var data = quad.data
var xSize = (size[0] + quad.size[0]) / 2
var ySize = (size[1] + quad.size[1]) / 2
if (data) {
if (data.index <= node.index) { return }
var x = xi - xCenter(data)
var y = yi - yCenter(data)
var xd = Math.abs(x) - xSize
var yd = Math.abs(y) - ySize
if (xd < 0 && yd < 0) {
var l = Math.sqrt(x * x + y * y)
var m = masses[data.index] / (mass + masses[data.index])
if (Math.abs(xd) < Math.abs(yd)) {
node.vx -= (x *= xd / l * strength) * m
data.vx += x * (1 - m)
} else {
node.vy -= (y *= yd / l * strength) * m
data.vy += y * (1 - m)
}
}
}
return x0 > xi + xSize || y0 > yi + ySize ||
x1 < xi - xSize || y1 < yi - ySize
}
function prepare(quad) {
if (quad.data) {
quad.size = sizes[quad.data.index]
} else {
quad.size = [0, 0]
var i = -1
while (++i < 4) {
if (quad[i] && quad[i].size) {
quad.size[0] = Math.max(quad.size[0], quad[i].size[0])
quad.size[1] = Math.max(quad.size[1], quad[i].size[1])
}
}
}
}
}
function xCenter(d) { return d.x + d.vx + sizes[d.index][0] / 2 }
function yCenter(d) { return d.y + d.vy + sizes[d.index][1] / 2 }
force.initialize = function (_) {
sizes = (nodes = _).map(size)
masses = sizes.map(function (d) { return d[0] * d[1] })
}
force.size = function (_) {
return (arguments.length
? (size = typeof _ === 'function' ? _ : constant(_), force)
: size)
}
force.strength = function (_) {
return (arguments.length ? (strength = +_, force) : strength)
}
force.iterations = function (_) {
return (arguments.length ? (iterations = +_, force) : iterations)
}
return force
}
function boundedBox() {
var nodes, sizes
var bounds
var size = constant([0, 0])
function force() {
var node, size
var xi, x0, x1, yi, y0, y1
var i = -1
while (++i < nodes.length) {
node = nodes[i]
size = sizes[i]
xi = node.x + node.vx
x0 = bounds[0][0] - xi
x1 = bounds[1][0] - (xi + size[0])
yi = node.y + node.vy
y0 = bounds[0][1] - yi
y1 = bounds[1][1] - (yi + size[1])
if (x0 > 0 || x1 < 0) {
node.x += node.vx
node.vx = -node.vx
if (node.vx < x0) { node.x += x0 - node.vx }
if (node.vx > x1) { node.x += x1 - node.vx }
}
if (y0 > 0 || y1 < 0) {
node.y += node.vy
node.vy = -node.vy
if (node.vy < y0) { node.vy += y0 - node.vy }
if (node.vy > y1) { node.vy += y1 - node.vy }
}
}
}
force.initialize = function (_) {
sizes = (nodes = _).map(size)
}
force.bounds = function (_) {
return (arguments.length ? (bounds = _, force) : bounds)
}
force.size = function (_) {
return (arguments.length
? (size = typeof _ === 'function' ? _ : constant(_), force)
: size)
}
return force
}
function ticked() {
rects
.attr('x', function (d) { return d.x })
.attr('y', function (d) { return d.y })
}
var px, py, vx, vy, offsetX, offsetY
function dragStarted(d) {
vx = 0
vy = 0
offsetX = (px = d3.event.x) - (d.fx = d.x)
offsetY = (py = d3.event.y) - (d.fy = d.y)
}
function dragged(d) {
vx = d3.event.x - px
vy = d3.event.y - py
d.fx = Math.max(Math.min((px = d3.event.x) - offsetX, width - d.size), 0)
d.fy = Math.max(Math.min((py = d3.event.y) - offsetY, height - d.size), 0)
}
function dragEnded(d) {
var vScalingFactor = maxVelocity / Math.max(Math.sqrt(vx * vx + vy * vy), maxVelocity)
d.fx = null
d.fy = null
d.vx = vx * vScalingFactor
d.vy = vy * vScalingFactor
}
function constant(_) {
return function () { return _ }
}
</script>
</body>
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment