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 } 205
