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