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#ifndef GOOSE_H_
6#define GOOSE_H_
7
8#include <vector>
9#include "ppapi/cpp/rect.h"
10
11#include "vector2.h"
12
13// A Goose.  Each goose has a location and a velocity.  Implements the
14// flocking algortihm described here:
15// http://processingjs.org/learning/topic/flocking with references to
16// http://harry.me/2011/02/17/neat-algorithms---flocking.
17class Goose {
18 public:
19  // Initialize a Goose at location (0, 0) no velocity.
20  Goose();
21
22  // Initialize a Goose at the given location with the specified velocity.
23  Goose(const Vector2& location, const Vector2& velocity);
24
25  // Run one tick of the simulation.  Compute a new acceleration based on the
26  // flocking algorithm (see Goose.flock()) and update the goose's location
27  // by integrating acceleration and velocity.
28  // @param geese The list of all the geese in the flock.
29  // @param  attractors The list of attractors.  Geese have affinity for these
30  //     points.
31  // @param flockBox The geese will stay inside of this box.  If the flock_box
32  //     is empty, the geese don't have boundaries.
33  void SimulationTick(const std::vector<Goose>& geese,
34                      const std::vector<Vector2>& attractors,
35                      const pp::Rect& flock_box);
36
37  // Implement the flocking algorithm in five steps:
38  //  1. Compute the separation component,
39  //  2. Compute the alignment component,
40  //  3. Compute the cohesion component.
41  //  4. Compute the effect of the attractors and blend this in with the
42  //     cohesion component.
43  //  5. Create a weighted sum of the three components and use this as the
44  //     new acceleration for the goose.
45  // This is an O(n^2) version of the algorithm.  There are ways to speed this
46  // up using spatial coherence techniques, but this version is much simpler.
47  // @param geese The list of all the neighbouring geese (in this
48  //     implementation, this is all the geese in the flock).
49  // @param  attractors The list of attractors.  Geese have affinity for these
50  //     points.
51  // @return The acceleration vector for this goose based on the flocking
52  //     algorithm.
53  Vector2 DesiredVector(const std::vector<Goose>& geese,
54                        const std::vector<Vector2>& attractors);
55
56  // Turn the goose towards a target.  The amount of turning force is clamped
57  // to |kMaxTurningForce|.
58  // @param target Turn the goose towards this target.
59  // @return A vector representing the new direction of the goose.
60  Vector2 TurnTowardsTarget(const Vector2& target);
61
62  // Accessors for location and velocoity.
63  Vector2 location() const {
64    return location_;
65  }
66  Vector2 velocity() const {
67    return velocity_;
68  }
69
70 private:
71  // Add a neighbouring goose's contribution to the separation mean.  Only
72  // consider geese that have moved inside of this goose's personal space.
73  // Modifies the separation accumulator |separation| in-place.
74  // @param distance The distance from this goose to the neighbouring goose.
75  // @param gooseDirection The direction vector from this goose to the
76  //     neighbour.
77  // @param separation The accumulated separation from all the neighbouring
78  //     geese.
79  // @param separationCount The current number of geese that have contributed to
80  //     the separation component so far.
81  // @return The new count of geese that contribute to the separation component.
82  //     If the goose under consideration does not contribute, this value is the
83  //     same as |separationCount|.
84  int32_t AccumulateSeparation(double distance,
85                               const Vector2& goose_direction,
86                               Vector2* separation, /* inout */
87                               int32_t separation_count);
88
89  // Add a neighbouring goose's contribution to the alignment mean.  Alignment
90  // is the average velocity of the neighbours. Only consider geese that are
91  // within |kNeighbourRadius|.  Modifies the alignment accumulator |alignment|
92  // in-place.
93  // @param distance The distance from this goose to the neighbouring goose.
94  // @param goose The neighbouring goose under consideration.
95  // @param alignment The accumulated alignment from all the neighbouring geese.
96  // @param alignCount The current number of geese that have contributed to the
97  //     alignment component so far.
98  // @return The new count of geese that contribute to the alignment component.
99  // If the goose under consideration does not contribute, this value is the
100  //     same as |alignCount|.
101  int32_t AccumulateAlignment(double distance,
102                              const Goose& goose,
103                              Vector2* alignment, /* inout */
104                              int32_t align_count);
105
106  // Add a neighbouring goose's contribution to the cohesion mean.  Cohesion is
107  // based on the average location of the neighbours.  The goose attempts to
108  // point to this average location.  Only consider geese that are within
109  // |kNeighbourRadius|.  Modifies the cohesion accumulator |cohesion| in-place.
110  // @param {!number} distance The distance from this goose to the neighbouring
111  //     goose.
112  // @param {!Goose} goose The neighbouring goose under consideration.
113  // @param {!goog.math.Vec2} cohesion The accumulated cohesion from all the
114  //     neighbouring geese.
115  // @param {!number} cohesionCount The current number of geese that have
116  //     contributed to the cohesion component so far.
117  // @return {!number} The new count of geese that contribute to the cohesion
118  //     component.  If the goose under consideration does not contribute, this
119  //     value is the same as |cohesionCount|.
120  int32_t AccumulateCohesion(double distance,
121                             const Goose& goose,
122                             Vector2* cohesion, /* inout */
123                             int32_t cohesion_count);
124
125  Vector2 location_;
126  Vector2 velocity_;
127};
128
129#endif  // GOOSE_H_
130