This example is an implementation of a simple flocking algorithm that uses the dynamics of repulsion, attraction, and orientation zones. This example is based off of the algorithm described by Couzin.
The basic principle is that each agent has three regions in a growing radius around it: a zone of repulsion, a zone of orientation, and a zone of attraction respectively. By editing the sizes of these zones you can expect to experience different behaviour.
This example allows you to see the behavior when two types of agents are used, allowing you to specify parameters for each group.
There are two basic types of parameters used: initial conditions and agent parameters. Agent parameters can be updated any time, including while in play. Initial conditions however require a reset before they take effect.
Note: If an initial condition is changed then the
Reset
button will turn yellow, indicating that a reset is required before some changes take effect.
Group 1
and Group 2
agents. Agents from the second group are rendered as the larger dots.k
nearest neighbors outside of the zone of orientation for their attraction vector.[0, 180]
) where the agent can not adjust their direction vector greater than this number for an individual iterationPlay
button to start animationPause
button to stop animationNext
button to do one time step of the algorithm.Dragging/Zooming behavior forked from mbostock's block: Drag & Zoom II
forked from lwthatcher's block: Directional Forces
forked from lwthatcher's block: Flocking
xxxxxxxxxx
<meta charset="utf-8">
<link rel="stylesheet" href="https://maxcdn.bootstrapcdn.com/bootstrap/3.3.7/css/bootstrap.min.css">
<link href="https://gitcdn.github.io/bootstrap-toggle/2.2.2/css/bootstrap-toggle.min.css" rel="stylesheet">
<style> /* set the CSS */
.point {
fill: darkslategrey;
}
.repulsed {
fill: red;
stroke: red;
}
.attracted {
fill: blue;
stroke: blue;
}
.oriented {
fill: LawnGreen;
stroke: LawnGreen;
}
.ao {
fill: DarkTurquoise;
stroke: DarkTurquoise;
}
.moved {
stroke: black;
fill: black;
}
.R_r {
fill: lightsalmon;
}
.R_o {
fill: Chartreuse;
}
.R_a {
fill: lightskyblue;
}
.num {
float: left;
}
.counter {
width: 50px;
float: right;
margin-right: 40px;
}
.counter-small {
width: 50px;
float: right;
margin-right: 0px;
}
.Group {
font-size: 12px;
font-weight: bold;
}
hr {
margin-top: 2px;
margin-bottom: 2px;
}
input[type=range] {
width: 85%;
margin-left: 17px;
}
.g1 {
background-color: lightcyan;
}
.g2 {
background-color: lightgray;
}
</style>
<script src="//ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js"></script>
<script src="https://www.numericjs.com/lib/numeric-1.2.6.js"></script>
<script src="https://gitcdn.github.io/bootstrap-toggle/2.2.2/js/bootstrap-toggle.min.js"></script>
<div class="row">
<div class="col-sm-9">
<svg id="svg" width="740" height="500"></svg>
</div>
<div class="col-sm-3">
<div class="row">
<b>Start Conditions:</b>
</div>
<div class="row">
<div class="num">Agents: </div>
<input class="counter" id="agents" type="number" onchange="updateNumAgents(this.value)" value=30></input>
</div>
<div class="row">
<div class="num">Sparsity: </div>
<input class="counter" id="sparsity" type="number" onchange="updateSparsity(this.value)" value=60></input>
</div>
<div class="row">
<div class="num">Distribution: </div><br>
<input class="range" id="dist" type="range" value=50 onchange="updateDistribution(this.value)"></input>
</div>
<div class="row">
<div class="col-sm-6 g1">
<span id="d-g1">50%</span>
</div>
<div class="col-sm-6 g2">
<span id="d-g2">50%</span>
</div>
</div>
<hr>
<div class="row">
<div class="col-sm-6 g1">
<input id="metric-1" type="checkbox" data-on="distance" onchange="changeMetric(this.checked, 0)" data-off="knn" checked data-toggle="toggle">
</div>
<div class="col-sm-6 g2">
<input id="metric-2" type="checkbox" onchange="changeMetric(this.checked, 1)" data-on="distance" data-off="knn" data-toggle="toggle">
</div>
</div>
<hr>
<div class="row">
<div class="col-sm-6 g1">
<span class="Group">Group 1:</span><br>
<div class="num">Zr:</div>
<input class="counter-small" id="zr-1" type="number" onchange="updateR_r(this.value, 0)" value=20></input>
</div>
<div class="col-sm-6 g2">
<span class="Group">Group 2:</span><br>
<div class="num">Zr:</div>
<input class="counter-small" id="zr-2" type="number" onchange="updateR_r(this.value, 1)" value=50></input>
</div>
</div>
<div class="row">
<div class="col-sm-6 g1">
<span class="Group"></span>
<div class="num">Zo:</div>
<input class="counter-small" id="zo-1" type="number" onchange="updateR_o(this.value, 0)" value=100></input>
</div>
<div class="col-sm-6 g2">
<div class="num">Zo:</div>
<input class="counter-small" id="zo-2" type="number" onchange="updateR_o(this.value, 1)" value=100></input>
</div>
</div>
<div class="row">
<div class="col-sm-6 g1" id="ak-box_1a">
<span class="Group"></span>
<div class="num">Za:</div>
<input class="counter-small" id="za-1" type="number" onchange="updateR_a(this.value, 0)" value=150></input>
</div>
<div class="col-sm-6 g1" id="ak-box_1k" hidden="hidden">
<span class="Group"></span>
<div class="num">k:</div>
<input class="counter-small" id="k-1" type="number" onchange="updateK(this.value, 0)" value=5></input>
</div>
<div class="col-sm-6 g2" id="ak-box_2a" hidden="hidden">
<div class="num">Za:</div>
<input class="counter-small" id="za-2" type="number" onchange="updateR_a(this.value, 1)" value=150></input>
</div>
<div class="col-sm-6 g2" id="ak-box_2k">
<span class="Group"></span>
<div class="num">k:</div>
<input class="counter-small" id="k-2" type="number" onchange="updateK(this.value, 1)" value=5></input>
</div>
</div>
<div class="row">
<div class="col-sm-6 g1">
<span class="Group"></span>
<div class="num">s:</div>
<input class="counter-small" id="speed-1" type="number" onchange="updateSpeed(this.value, 0)" min=0 value=15></input>
</div>
<div class="col-sm-6 g2">
<div class="num">s:</div>
<input class="counter-small" id="speed-2" type="number" onchange="updateSpeed(this.value, 1)" min=0 value=15></input>
</div>
</div>
<div class="row">
<div class="col-sm-6 g1">
<span class="Group"></span>
<div class="num">θ:</div>
<input class="counter-small" id="theta-1" type="number" onchange="updateTurnRate(this.value, 0)" min=0 max=180 value=100></input>
</div>
<div class="col-sm-6 g2">
<div class="num">θ:</div>
<input class="counter-small" id="theta-2" type="number" onchange="updateTurnRate(this.value, 1)" min=0 max=180 value=100></input>
</div>
</div>
<hr>
<div class="row">
<b>Controls:</b>
<br>
<button onclick="play()"><span class="glyphicon glyphicon-play"></button>
<button onclick="pause()"><span class="glyphicon glyphicon-pause"></button>
<button onclick="next()"><span class="glyphicon glyphicon-step-forward"></button>
</div>
<hr>
<div class="row">
<button id="reset" class="btn" onclick="reset()">Reset</button>
</div>
<hr>
<div class="row">
<button class="btn btn-primary" onclick="printEigenvalues()">Get Eigenvalues</button>
</div>
<div class="row">
Fiedler: <span id="eigs"></span>
</br>
# Components: <span id="num_coms"></span>
</div>
</div>
</div>
<script src="https://d3js.org/d3.v4.min.js"></script>
<script>
// === VARIABLES ===
// Agent Parameters
var R_r = [d3.select("#zr-1").attr("value"), d3.select("#zr-2").attr("value")];
var R_o = [d3.select("#zo-1").attr("value"), d3.select("#zo-2").attr("value")];
var R_a = [d3.select("#za-1").attr("value"), d3.select("#za-2").attr("value")];
var K = [d3.select("#k-1").attr("value"), d3.select("#k-2").attr("value")];
var TRAVEL_LENGTH = [d3.select("#speed-1").attr("value"),
d3.select("#speed-2").attr("value")];
var TURN_RATE = [d3.select("#theta-1").attr("value"),
d3.select("#theta-2").attr("value")];
var METRICS = [getMetric(d3.select("#metric-1").property("checked")),
getMetric(d3.select("#metric-2").property("checked"))];
// Start Conditions
var NUM_AGENTS = d3.select("#agents").attr("value");
var INIT_SPARSITY = d3.select("#sparsity").attr("value");
var GROUP_DISTRIBUTION = .50;
// Helper vars
var POINT_SIZE_1 = 2.5;
var POINT_SIZE_2 = 4;
var DT = 100;
var timer;
// === INIT ===
var svg = d3.select("svg"),
width = +svg.attr("width"),
height = +svg.attr("height"),
transform = d3.zoomIdentity;
var points = d3.range(NUM_AGENTS).map(phyllotaxis(INIT_SPARSITY));
var g = svg.append("g");
// === D3 FUNCTIONS ===
var t_p = d3.transition("points")
.duration(DT)
.ease(d3.easeLinear);
var t_r = d3.transition("radii")
.duration(DT)
.ease(d3.easeLinear);
var t = d3.transition()
.duration(DT)
.ease(d3.easeLinear);
var zoom = d3.zoom()
.scaleExtent([1 / 2.5, 8])
.on("zoom", zoomed);
function zoomed() {
transform = d3.event.transform;
g.attr("transform", d3.event.transform);
}
// === CONTROLS ===
var play = function() {
timer = d3.interval(() => {
next();
}, DT);
}
var pause = function() {
timer.stop();
}
function updateR_r(value,i) {
R_r[i] = value;
d3.selectAll(".R_r-"+i).transition(t)
.attr("r", (d) => { return show_radius(d, R_r[i]); });
}
function updateR_o(value,i) {
R_o[i] = value;
d3.selectAll(".R_o-"+i).transition(t)
.attr("r", (d) => { return show_radius(d, R_o[i]); });
}
function updateR_a(value,i) {
R_a[i] = value;
d3.selectAll(".R_a-"+i).transition(t)
.attr("r", (d) => { return show_radius(d, R_a[i]); });
}
function updateK(value,i) {
K[i] = value;
console.log(K);
}
function updateSpeed(value,i) {
TRAVEL_LENGTH[i] = value;
console.log(TRAVEL_LENGTH);
}
function updateTurnRate(value,i) {
TURN_RATE[i] = value;
console.log(TURN_RATE);
}
function updateNumAgents(value) {
NUM_AGENTS = value;
d3.select("#reset").classed("btn-warning", true);
}
function updateSparsity(value) {
INIT_SPARSITY = value;
d3.select("#reset").classed("btn-warning", true);
}
function updateDistribution(value) {
var d2 = 100-value;
GROUP_DISTRIBUTION = d2/100;
console.log(GROUP_DISTRIBUTION)
d3.select("#d-g1").text(d2 + "%");
d3.select("#d-g2").text(value + "%");
d3.select("#reset").classed("btn-warning", true);
}
function reset() {
d3.select("#reset").classed("btn-warning", null);
svg.selectAll(".point").remove();
svg.selectAll(".r").remove();
points = d3.range(NUM_AGENTS).map(phyllotaxis(INIT_SPARSITY));
start();
}
function printEigenvalues() {
var L = getLaplacian();
var eigs = getEigenvalues(L);
console.info("Eigenvalues", eigs);
var fiedler = getFiedler(eigs);
var components = getNumComponents(eigs);
d3.select("#eigs").text(fiedler);
d3.select("#num_coms").text(components);
}
function changeMetric(value,i) {
var j = i+1;
console.log("metric", i, value);
METRICS[i] = getMetric(value);
if (value) { //distance
d3.select("#ak-box_" + j + "k").attr("hidden", "hidden");
d3.select("#ak-box_" + j + "a").attr("hidden", null);
}
else { //knn
d3.select("#ak-box_" + j + "a").attr("hidden", "hidden");
d3.select("#ak-box_" + j + "k").attr("hidden", null);
}
d3.select("#reset").classed("btn-warning", true);
}
// === HELPER FUNCTIONS ===
function show_radius(d, r) {
if (d.show) return r;
else return 0;
}
function randomGroup(i) {
var x = Math.random();
var group = x > GROUP_DISTRIBUTION ? 1 : 0;
return group;
}
function getType(group) {
return METRICS[group];
}
function getMetric(checked) {
if (checked) return "dist";
else return "knn";
}
// === EVENT HANDLERS ===
function onclick(d) {
d.show = !d.show;
console.info(d);
if (d.show) {
// Attraction
if (d.metric === "dist") {
g.append("circle").datum(d).lower()
.attr("class", (d) => {return "r R_a r--" + d.idx + " R_a-" + d.group;})
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", 0)
.attr("opacity", 0.10)
.transition(t)
.attr("r", (d) => { return show_radius(d, R_a[d.group]); });
}
// Orientation
g.append("circle").datum(d).lower()
.attr("class", (d) => {return "r R_o r--" + d.idx + " R_o-" + d.group;})
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", 0)
.attr("opacity", 0.15)
.transition(t)
.attr("r", (d) => { return show_radius(d, R_o[d.group]); });
// Repulsion
g.append("circle").datum(d).lower()
.attr("class", (d) => {return "r R_r r--" + d.idx + " R_r-" + d.group;})
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", 0)
.attr("opacity", 0.35)
.transition(t)
.attr("r", (d) => { return show_radius(d, R_r[d.group]); });
}
else {
d3.select(".R_r.r--"+d.idx).transition(t).attr("r", 0).remove();
d3.select(".R_o.r--"+d.idx).transition(t).attr("r", 0).remove();
d3.select(".R_a.r--"+d.idx).transition(t).attr("r", 0).remove();
}
}
function dragged(d) {
dx = d3.event.x;
dy = d3.event.y;
// update point
d3.select(this)
.attr("cx", d.x = dx)
.attr("cy", d.y = dy);
// update collision state
updateZones();
g.selectAll(".point").attr("class", (d) => {return "point " + d.next.style;});
// update radius
d3.select(".R_r.r--" + d.idx)
.attr("cx", d.x = dx).attr("cy", d.y = dy);
d3.select(".R_o.r--" + d.idx)
.attr("cx", d.x = dx).attr("cy", d.y = dy);
d3.select(".R_a.r--" + d.idx)
.attr("cx", d.x = dx).attr("cy", d.y = dy);
}
// === START ===
function start() {
// SETUP POINTS
g.selectAll(".point")
.data(points)
.enter().append("circle")
.attr("id", (d) => "pt-"+d.idx)
.attr("class", "point")
.attr("cx", function(d) { return d.x; })
.attr("cy", function(d) { return d.y; })
.attr("r", (d) => {return d.group === 1 ? POINT_SIZE_2 : POINT_SIZE_1;})
.on("click", onclick)
.call(d3.drag()
.on("drag", dragged));
// overlay points on top
g.selectAll(".point").raise();
svg.call(zoom);
// color points
updateZones();
g.selectAll(".point").attr("class", (d) => {return "point " + d.next.style;});
}
// invoke immediately
start();
// === UPDATE FUNCTIONS ===
function next() {
// get next positions
updateZones();
// move points
g.selectAll(".point").interrupt().transition(t)
.attr("cx",(d) => { d.x = d.next.x; return d.x;})
.attr("cy",(d) => { d.y = d.next.y; return d.y;})
.attr("class", (d) => {return "point " + d.next.style;});
// move radii
g.selectAll(".r").interrupt().transition(t)
.attr("cx",(d) => { return d.x;})
.attr("cy",(d) => { return d.y;});
}
function updateZones() {
g.selectAll(".point").each((pt1) => {
var r_pts = pointsInRadius(pt1, R_r[pt1.group]),
o_pts = betweenRadii(pt1, R_r[pt1.group], R_o[pt1.group]),
a_pts;
if (pt1.metric === "dist") {
a_pts = betweenRadii(pt1, R_o[pt1.group], R_a[pt1.group])
}
else {
a_pts = knn(pt1, R_o[pt1.group], K[pt1.group]);
}
var neighbors = [];
Array.prototype.push.apply(neighbors, r_pts);
Array.prototype.push.apply(neighbors, o_pts);
Array.prototype.push.apply(neighbors, a_pts);
var ptclass = "";
// nr > 0
if (r_pts.length > 0) {
pt1.angle = r_angle(pt1, r_pts);
ptclass = 'repulsed';
}
// nr == 0
else {
if (o_pts.length > 0 || a_pts.length > 0) {
if (a_pts.length > 0 && o_pts.length === 0) {
ptclass = "attracted";
pt1.angle = a_angle(pt1, a_pts);
}
else if (o_pts.length > 0 && a_pts.length === 0) {
ptclass = "oriented"
pt1.angle = o_angle(pt1, o_pts);
}
else {
ptclass = "ao"
var dir_a = a_angle(pt1, a_pts);
var dir_o = o_angle(pt1, o_pts);
pt1.angle = (dir_a + dir_o)/2;
}
}
}
var da = getNextAngle(pt1);
var dx = pt1.x + TRAVEL_LENGTH[pt1.group] * Math.cos(toRadians(da));
var dy = pt1.y + TRAVEL_LENGTH[pt1.group] * Math.sin(toRadians(da));
pt1.next = {"x":dx, "y":dy, "style": ptclass};
pt1.neighbors = neighbors;
});
}
// === MATH FUNCTIONS ===
function dist(pt1, pt2) {
return Math.pow((pt1.x-pt2.x),2) + Math.pow((pt1.y-pt2.y),2);
}
function getNextAngle(pt) {
var θτ = TURN_RATE[pt.group];
var dθ = pt.dir - pt.angle;
if (Math.abs(dθ) > θτ) {
pt.dir = pt.angle - Math.sign(dθ)*θτ;
}
else {
pt.dir = pt.angle;
}
return pt.dir;
}
function getLaplacian() {
var L = [];
g.selectAll(".point").each((p1,i,nodes) => {
L[p1.idx] = Array(nodes.length).fill(0);
for (var p2 of p1.neighbors) {
L[p1.idx][p2.idx] = -1;
}
L[p1.idx][p1.idx] = -1 * L[p1.idx].reduce( ( acc, cur ) => acc + cur, 0 );
});
console.info("Graph Laplacian:", L.join('\n'));
return L;
}
function getEigenvalues(L) {
var eigs = numeric.eig(L);
return eigs['lambda'].x.map((x) => +x.toFixed(3)).sort();
}
function getFiedler(eigs) {
return eigs.find((v) => {return v > 0;})
}
function getNumComponents(eigs) {
return eigs.filter((v) => {return v === 0;}).length;
}
function r_angle(d, pts) {
var sum = 0;
for (var p of pts) {
sum += Math.atan2(p.y-d.y, p.x-d.x)
}
var ave = sum / pts.length;
return toDegrees(ave) + 180;
}
function a_angle(d, pts) {
var sum = 0;
for (var p of pts) {
sum += Math.atan2(p.y-d.y, p.x-d.x)
}
var ave = sum / pts.length;
return toDegrees(ave);
}
function o_angle(d, pts) {
var sum = 0;
for (var p of pts) {
sum += p.dir;
}
var ave = sum / pts.length;
return ave;
}
function knn(pt1,r, k) {
var neighbors = [];
var compare = (a,b) => {return a.dist - b.dist;}
g.selectAll(".point").each((d) => {
if (pt1.idx != d.idx && !withinRadius(pt1, d, r)) {
var item = {"dist": dist(pt1,d), "point": d}
neighbors.push(item);
}
});
neighbors.sort(compare);
var result = neighbors.map((n) => n.point);
return result.slice(0,k);
}
function pointsInRadius(pt1, r) {
var result = [];
d3.selectAll(".point").each((d) => {
if (pt1.idx != d.idx && withinRadius(pt1, d, r)) {
result.push(d);
}
});
return result;
}
function betweenRadii(pt1, r_inner, r_outer) {
var result = [];
d3.selectAll(".point").each((d) => {
if (pt1.idx != d.idx && withinRadius(pt1, d, r_outer) && !withinRadius(pt1, d, r_inner)) {
result.push(d);
}
});
return result;
}
function withinRadius(pt1, pt2, r) {
var dx = pt1.x-pt2.x;
var dy = pt1.y-pt2.y;
return dx*dx + dy*dy <= r*r;
}
function toDegrees (angle) {
return (angle * (180 / Math.PI)) % 360;
}
function toRadians (angle) {
return angle * (Math.PI / 180);
}
function phyllotaxis(radius) {
var theta = Math.PI * (3 - Math.sqrt(5));
return function(i) {
var r = radius * Math.sqrt(i), a = theta * i;
var group = randomGroup(i);
return {
idx: i,
x: width / 2 + r * Math.cos(a),
y: height / 2 + r * Math.sin(a),
angle: toDegrees(a)+180,
dir: toDegrees(a)+180,
group: group,
metric: getType(group),
show: false //only for the center one
};
};
}
</script>
Modified http://www.numericjs.com/lib/numeric-1.2.6.js to a secure url
https://ajax.googleapis.com/ajax/libs/jquery/1.11.0/jquery.min.js
https://www.numericjs.com/lib/numeric-1.2.6.js
https://gitcdn.github.io/bootstrap-toggle/2.2.2/js/bootstrap-toggle.min.js
https://d3js.org/d3.v4.min.js