native_client_sdk/src/examples/demo/flock/goose.cc

   1   // Copyright 2013 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include "goose.h"
   6
   7 namespace {
   8 // The maximum speed of a goose.  Measured in meters/second.
   9 const double kMaxSpeed = 2.0;
  10
  11 // The maximum force that can be applied to turn a goose when computing the
  12 // aligment.  Measured in meters/second/second.
  13 const double kMaxTurningForce = 0.05;
  14
  15 // The neighbour radius of a goose.  Only geese within this radius will affect
  16 // the flocking computations of this goose.  Measured in pixels.
  17 const double kNeighbourRadius = 64.0;
  18
  19 // The minimum distance that a goose can be from this goose.  If another goose
  20 // comes within this distance of this goose, the flocking algorithm tries to
  21 // move the geese apart.  Measured in pixels.
  22 const double kPersonalSpace = 32.0;
  23
  24 // The distance at which attractors have effect on a goose's direction.
  25 const double kAttractorRadius = 320.0;
  26
  27 // The goose will try to turn towards geese within this distance (computed
  28 // during the cohesion phase).  Measured in pixels.
  29 const double kMaxTurningDistance = 100.0;
  30
  31 // The weights used when computing the weighted sum the three flocking
  32 // components.
  33 const double kSeparationWeight = 2.0;
  34 const double kAlignmentWeight = 1.0;
  35 const double kCohesionWeight = 1.0;
  36
  37 }  // namespace
  38
  39
  40 Goose::Goose() : location_(0, 0), velocity_(0, 0) {
  41 }
  42
  43 Goose::Goose(const Vector2& location, const Vector2& velocity)
  44   : location_(location),
  45     velocity_(velocity) {
  46 }
  47
  48 void Goose::SimulationTick(const std::vector<Goose>& geese,
  49                            const std::vector<Vector2>& attractors,
  50                            const pp::Rect& flock_box) {
  51
  52   Vector2 acceleration = DesiredVector(geese, attractors);
  53   velocity_.Add(acceleration);
  54
  55   // Limit the velocity to a maximum speed.
  56   velocity_.Clamp(kMaxSpeed);
  57
  58   location_.Add(velocity_);
  59
  60   // Wrap the goose location to the flock box.
  61   if (!flock_box.IsEmpty()) {
  62     while (location_.x() < flock_box.x())
  63       location_.set_x(location_.x() + flock_box.width());
  64
  65     while (location_.x() >= flock_box.right())
  66       location_.set_x(location_.x() - flock_box.width());
  67
  68     while (location_.y() < flock_box.y())
  69       location_.set_y(location_.y() + flock_box.height());
  70
  71     while  (location_.y() >= flock_box.bottom())
  72       location_.set_y(location_.y() - flock_box.height());
  73   }
  74 }
  75
  76 Vector2 Goose::DesiredVector(const std::vector<Goose>& geese,
  77                              const std::vector<Vector2>& attractors) {
  78   // Loop over all the neighbouring geese in the flock, accumulating
  79   // the separation mean, the alignment mean and the cohesion mean.
  80   int32_t separation_count = 0;
  81   Vector2 separation;
  82   int32_t align_count = 0;
  83   Vector2 alignment;
  84   int32_t cohesion_count = 0;
  85   Vector2 cohesion;
  86
  87   for (std::vector<Goose>::const_iterator goose_it = geese.begin();
  88        goose_it < geese.end();
  89        ++goose_it) {
  90     const Goose& goose = *goose_it;
  91
  92   // Compute the distance from this goose to its neighbour.
  93     Vector2 goose_delta = Vector2::Difference(
  94         location_, goose.location());
  95     double distance = goose_delta.Magnitude();
  96
  97     separation_count = AccumulateSeparation(
  98         distance, goose_delta, &separation, separation_count);
  99
 100     align_count = AccumulateAlignment(
 101         distance, goose, &alignment, align_count);
 102     cohesion_count = AccumulateCohesion(
 103         distance, goose, &cohesion, cohesion_count);
 104   }
 105
 106   // Compute the means and create a weighted sum.  This becomes the goose's new
 107   // acceleration.
 108   if (separation_count > 0) {
 109     separation.Scale(1.0 / static_cast<double>(separation_count));
 110   }
 111   if (align_count > 0) {
 112     alignment.Scale(1.0 / static_cast<double>(align_count));
 113     // Limit the effect that alignment has on the final acceleration.  The
 114     // alignment component can overpower the others if there is a big
 115     // difference between this goose's velocity and its neighbours'.
 116     alignment.Clamp(kMaxTurningForce);
 117   }
 118
 119   // Compute the effect of the attractors and blend this in with the flock
 120   // cohesion component.  An attractor has to be within kAttractorRadius to
 121   // effect the heading of a goose.
 122   for (size_t i = 0; i < attractors.size(); ++i) {
 123     Vector2 attractor_direction = Vector2::Difference(
 124         attractors[i], location_);
 125     double distance = attractor_direction.Magnitude();
 126     if (distance < kAttractorRadius) {
 127       attractor_direction.Scale(1000);  // Each attractor acts like 1000 geese.
 128       cohesion.Add(attractor_direction);
 129       cohesion_count++;
 130     }
 131   }
 132
 133   // If there is a non-0 cohesion component, steer the goose so that it tries
 134   // to follow the flock.
 135   if (cohesion_count > 0) {
 136     cohesion.Scale(1.0 / static_cast<double>(cohesion_count));
 137     cohesion = TurnTowardsTarget(cohesion);
 138   }
 139   // Compute the weighted sum.
 140   separation.Scale(kSeparationWeight);
 141   alignment.Scale(kAlignmentWeight);
 142   cohesion.Scale(kCohesionWeight);
 143   Vector2 weighted_sum = cohesion;
 144   weighted_sum.Add(alignment);
 145   weighted_sum.Add(separation);
 146   return weighted_sum;
 147 }
 148
 149 Vector2 Goose::TurnTowardsTarget(const Vector2& target) {
 150   Vector2 desired_direction = Vector2::Difference(target, location_);
 151   double distance = desired_direction.Magnitude();
 152   Vector2 new_direction;
 153   if (distance > 0.0) {
 154     desired_direction.Normalize();
 155     // If the target is within the turning affinity distance, then make the
 156     // desired direction based on distance to the target.  Otherwise, base
 157     // the desired direction on MAX_SPEED.
 158     if (distance < kMaxTurningDistance) {
 159       // Some pretty arbitrary dampening.
 160       desired_direction.Scale(kMaxSpeed * distance / 100.0);
 161     } else {
 162       desired_direction.Scale(kMaxSpeed);
 163     }
 164     new_direction = Vector2::Difference(desired_direction, velocity_);
 165     new_direction.Clamp(kMaxTurningForce);
 166   }
 167   return new_direction;
 168 }
 169
 170 int32_t Goose::AccumulateSeparation(double distance,
 171                                     const Vector2& goose_delta,
 172                                     Vector2* separation, /* inout */
 173                                     int32_t separation_count) {
 174   if (distance > 0.0 && distance < kPersonalSpace) {
 175     Vector2 weighted_direction = goose_delta;
 176     weighted_direction.Normalize();
 177     weighted_direction.Scale(1.0  / distance);
 178     separation->Add(weighted_direction);
 179     separation_count++;
 180   }
 181   return separation_count;
 182 }
 183
 184 int32_t Goose::AccumulateAlignment(double distance,
 185                                    const Goose& goose,
 186                                    Vector2* alignment, /* inout */
 187                                    int32_t align_count) {
 188   if (distance > 0.0 && distance < kNeighbourRadius) {
 189     alignment->Add(goose.velocity());
 190     align_count++;
 191   }
 192   return align_count;
 193 }
 194
 195 int32_t Goose::AccumulateCohesion(double distance,
 196                                   const Goose& goose,
 197                                   Vector2* cohesion, /* inout */
 198                                   int32_t cohesion_count) {
 199   if (distance > 0.0 && distance < kNeighbourRadius) {
 200     cohesion->Add(goose.location());
 201     cohesion_count++;
 202   }
 203   return cohesion_count;
 204 }