1 // Boid flocking based on http://harry.me/2011/02/17/neat-algorithms---flocking

     2 var boid = (function() {

     3   function boid() {

     4     var position = [0, 0],

     5         velocity = [0, 0],

     6         gravityCenter = null,

     7         neighborRadius = 50,

     8         maxForce = .1,

     9         maxSpeed = 1,

    10         separationWeight = 2,

    11         alignmentWeight = 1,

    12         cohesionWeight = 1,

    13         desiredSeparation = 10;

    14 

    15     function boid(neighbors) {

    16       var accel = flock(neighbors);

    17       d3_ai_boidWrap(position);

    18       velocity[0] += accel[0];

    19       velocity[1] += accel[1];

    20       if (gravityCenter) {

    21         var g = d3_ai_boidGravity(gravityCenter, position, neighborRadius);

    22         velocity[0] += g[0];

    23         velocity[1] += g[1];

    24       }

    25       d3_ai_boidLimit(velocity, maxSpeed);

    26       position[0] += velocity[0];

    27       position[1] += velocity[1];

    28       return position;

    29     }

    30 

    31     function flock(neighbors) {

    32       var separation = [0, 0],

    33           alignment = [0, 0],

    34           cohesion = [0, 0],

    35           separationCount = 0,

    36           alignmentCount = 0,

    37           cohesionCount = 0,

    38           i = -1,

    39           l = neighbors.length;

    40       while (++i < l) {

    41         var n = neighbors[i];

    42         if (n === this) continue;

    43         var npos = n.position(),

    44             d = d3_ai_boidDistance(position, npos);

    45         if (d > 0) {

    46           if (d < desiredSeparation) {

    47             var tmp = d3_ai_boidNormalize(d3_ai_boidSubtract(position.slice(), npos));

    48             separation[0] += tmp[0] / d;

    49             separation[1] += tmp[1] / d;

    50             separationCount++;

    51           }

    52           if (d < neighborRadius) {

    53             var nvel = n.velocity();

    54             alignment[0] += nvel[0];

    55             alignment[1] += nvel[1];

    56             alignmentCount++;

    57             cohesion[0] += npos[0];

    58             cohesion[1] += npos[1];

    59             cohesionCount++;

    60           }

    61         }

    62       }

    63 

    64       if (separationCount > 0) {

    65         separation[0] /= separationCount;

    66         separation[1] /= separationCount;

    67       }

    68 

    69       if (alignmentCount > 0) {

    70         alignment[0] /= alignmentCount;

    71         alignment[1] /= alignmentCount;

    72       }

    73       d3_ai_boidLimit(alignment, maxForce);

    74 

    75       if (cohesionCount > 0) {

    76         cohesion[0] /= cohesionCount;

    77         cohesion[1] /= cohesionCount;

    78       } else {

    79         cohesion = position.slice();

    80       }

    81       cohesion = steerTo(cohesion);

    82 

    83       return [

    84         separation[0] * separationWeight +

    85          alignment[0] * alignmentWeight +

    86           cohesion[0] * cohesionWeight,

    87         separation[1] * separationWeight +

    88          alignment[1] * alignmentWeight +

    89           cohesion[1] * cohesionWeight

    90       ];

    91     }

    92 

    93     function steerTo(target) {

    94       var desired = d3_ai_boidSubtract(target, position),

    95           d = d3_ai_boidMagnitude(desired);

    96 

    97       if (d > 0) {

    98         d3_ai_boidNormalize(desired);

    99 

   100         // Two options for desired vector magnitude (1 -- based on distance, 2 -- maxspeed)

   101         var mul = maxSpeed * (d < 100 ? d / 100 : 1);

   102         desired[0] *= mul;

   103         desired[1] *= mul;

   104 

   105         // Steering = Desired minus Velocity

   106         var steer = d3_ai_boidSubtract(desired, velocity);

   107         d3_ai_boidLimit(steer, maxForce)  // Limit to maximum steering force

   108       } else {

   109         steer = [0, 0];

   110       }

   111       return steer;

   112     }

   113 

   114     boid.position = function(x) {

   115       if (!arguments.length) return position;

   116       position = x;

   117       return boid;

   118     }

   119 

   120     boid.velocity = function(x) {

   121       if (!arguments.length) return velocity;

   122       velocity = x;

   123       return boid;

   124     }

   125 

   126     boid.gravityCenter = function(x) {

   127       if (!arguments.length) return gravityCenter;

   128       gravityCenter = x;

   129       return boid;

   130     }

   131 

   132     boid.neighborRadius = function(x) {

   133       if (!arguments.length) return neighborRadius;

   134       neighborRadius = x;

   135       return boid;

   136     }

   137 

   138     boid.maxForce = function(x) {

   139       if (!arguments.length) return maxForce;

   140       maxForce = x;

   141       return boid;

   142     }

   143 

   144     boid.maxSpeed = function(x) {

   145       if (!arguments.length) return maxSpeed;

   146       maxSpeed = x;

   147       return boid;

   148     }

   149 

   150     boid.separationWeight = function(x) {

   151       if (!arguments.length) return separationWeight;

   152       separationWeight = x;

   153       return boid;

   154     }

   155 

   156     boid.alignmentWeight = function(x) {

   157       if (!arguments.length) return alignmentWeight;

   158       alignmentWeight = x;

   159       return boid;

   160     }

   161 

   162     boid.cohesionWeight = function(x) {

   163       if (!arguments.length) return cohesionWeight;

   164       cohesionWeight = x;

   165       return boid;

   166     }

   167 

   168     boid.desiredSeparation = function(x) {

   169       if (!arguments.length) return desiredSeparation;

   170       desiredSeparation = x;

   171       return boid;

   172     }

   173 

   174     return boid;

   175   }

   176 

   177   function d3_ai_boidNormalize(a) {

   178     var m = d3_ai_boidMagnitude(a);

   179     if (m > 0) {

   180       a[0] /= m;

   181       a[1] /= m;

   182     }

   183     return a;

   184   }

   185 

   186   function d3_ai_boidWrap(position) {

   187     if (position[0] > w) position[0] = 0;

   188     else if (position[0] < 0) position[0] = w;

   189     if (position[1] > h) position[1] = 0;

   190     else if (position[1] < 0) position[1] = h;

   191   }

   192 

   193   function d3_ai_boidGravity(center, position, neighborRadius) {

   194     if (center[0] != null) {

   195       var m = d3_ai_boidSubtract(center.slice(), position),

   196           d = d3_ai_boidMagnitude(m) - 10;

   197       if (d > 0 && d < neighborRadius * 5) {

   198         d3_ai_boidNormalize(m);

   199         m[0] /= d;

   200         m[1] /= d;

   201         return m;

   202       }

   203     }

   204     return [0, 0];

   205   }

   206 

   207   function d3_ai_boidDistance(a, b) {

   208     var dx = a[0] - b[0],

   209         dy = a[1] - b[1];

   210     if (dx > w / 2) dx = w - dx;

   211     if (dy > h / 2) dy = h - dy;

   212     return Math.sqrt(dx * dx + dy * dy);

   213   }

   214 

   215   function d3_ai_boidSubtract(a, b) {

   216     a[0] -= b[0];

   217     a[1] -= b[1];

   218     return a;

   219   }

   220 

   221   function d3_ai_boidMagnitude(v) {

   222     return Math.sqrt(v[0] * v[0] + v[1] * v[1]);

   223   }

   224 

   225   function d3_ai_boidLimit(a, max) {

   226     if (d3_ai_boidMagnitude(a) > max) {

   227       d3_ai_boidNormalize(a);

   228       a[0] *= max;

   229       a[1] *= max;

   230     }

   231     return a;

   232   }

   233 

   234   return boid;

   235 })();