Empirical
Surface2D.h
Go to the documentation of this file.
1 // This file is part of Empirical, https://github.com/devosoft/Empirical
2 // Copyright (C) Michigan State University, 2016-2018.
3 // Released under the MIT Software license; see doc/LICENSE
4 //
5 //
6 // This file defines a templated class to represent a 2D suface capable of maintaining data
7 // about which 2D bodies are currently on that surface and rapidly identifying if they are
8 // overlapping.
9 //
10 // BODY_TYPE is the class that represents the body geometry.
11 // BODY_INFO represents the internal infomation about the body, including the controller.
12 //
13 // Member functions include:
14 // Surface2D(double _width, double _height);
15 // const Point & GetMaxPosition() const;
16 // emp::vector<BODY_TYPE *> & GetBodySet();
17 // const emp::vector<BODY_TYPE *> & GetConstBodySet() const;
18 // Surface2D<BODY_TYPE, BODY_INFO> & AddBody(BODY_TYPE * new_body);
19 // void TestCollisions(std::function<bool(BODY_TYPE &, BODY_TYPE &)> collide_fun);
20 //
21 //
22 // Development notes:
23 // * Need a good function to remove a body; now we have to use GetBodySet() and modify it.
24 
25 
26 #ifndef EMP_SURFACE_2D_H
27 #define EMP_SURFACE_2D_H
28 
29 #include "../base/Ptr.h"
30 #include "../tools/functions.h"
31 #include "Body2D.h"
32 
33 #include <functional>
34 
35 namespace emp {
36 
37  template <typename BODY_TYPE>
38  class Surface2D {
39  private:
40  const Point max_pos; // Lower-left corner of the surface.
41  emp::vector<Ptr<BODY_TYPE>> body_set; // Set of all bodies on surface
42 
43  public:
44  Surface2D(double _width, double _height)
45  : max_pos(_width, _height), body_set() { ; }
46  ~Surface2D() { Clear(); }
47 
48  double GetWidth() const { return max_pos.GetX(); }
49  double GetHeight() const { return max_pos.GetY(); }
50  const Point & GetMaxPosition() const { return max_pos; }
51 
52  emp::vector<Ptr<BODY_TYPE>> & GetBodySet() { return body_set; }
53  const emp::vector<Ptr<BODY_TYPE>> & GetConstBodySet() const { return body_set; }
54 
55  // Add a single body. Surface now controls this body and must delete it.
57  body_set.push_back(new_body); // Add body to master list
58  return *this;
59  }
60 
61  // Clear all bodies on the surface.
63  for (auto body : body_set) body.Delete();
64  body_set.resize(0);
65  return *this;
66  }
67 
68  // The following function will test pairs of collisions and run the passed-in function
69  // on pairs of objects that *may* collide.
70 
71  void TestCollisions(std::function<bool(BODY_TYPE &, BODY_TYPE &)> collide_fun) {
72  emp_assert(collide_fun);
73 
74  // Find the size of the largest body to determine minimum sector size.
75  double max_radius = 0.0;
76  for (auto body : body_set) {
77  if (body->GetRadius() > max_radius) max_radius = body->GetRadius();
78  }
79 
80  // Figure out the actual number of sectors to use (currently no more than 1024).
81  const int num_cols = std::min<int>((int)(max_pos.GetX() / (max_radius * 2.0)), 32);
82  const int num_rows = std::min<int>((int)(max_pos.GetY() / (max_radius * 2.0)), 32);
83  const int max_col = num_cols-1;
84  const int max_row = num_rows-1;
85 
86  const int num_sectors = num_cols * num_rows;
87  const double sector_width = max_pos.GetX() / (double) num_cols;
88  const double sector_height = max_pos.GetY() / (double) num_rows;
89 
90  emp::vector< emp::vector<Ptr<BODY_TYPE>> > sector_set(num_sectors);
91 
92 
93  int hit_count = 0;
94  int test_count = 0;
95 
96  // Loop through all of the bodies on this surface placing them in sectors and testing for
97  // collisions with other bodies already in nearby sectors.
98  for (auto body : body_set) {
99  emp_assert(body);
100  // Determine which sector the current body is in.
101  const int cur_col = emp::ToRange<int>((int)(body->GetCenter().GetX()/sector_width), 0, max_col);
102  const int cur_row = emp::ToRange<int>((int)(body->GetCenter().GetY()/sector_height), 0, max_row);
103 
104  // See if this body may collide with any of the bodies previously put into sectors.
105  for (int i = std::max(0, cur_col-1); i <= std::min(cur_col+1, num_cols-1); i++) {
106  for (int j = std::max(0, cur_row-1); j <= std::min(cur_row+1, num_rows-1); j++) {
107  const int sector_id = i + num_cols * j;
108  if (sector_set[sector_id].size() == 0) continue;
109 
110  for (auto body2 : sector_set[sector_id]) {
111  test_count++;
112  if (collide_fun(*body, *body2)) hit_count++;
113  }
114 
115  }
116  }
117 
118  // Add this body to the current sector for future tests to compare with.
119  const int cur_sector = cur_col + cur_row * num_cols;
120  emp_assert(cur_sector < (int) sector_set.size());
121 
122  sector_set[cur_sector].push_back(body);
123  }
124 
125  // Make sure all bodies are in a legal position on the surface.
126  for (Ptr<BODY_TYPE> cur_body : body_set) {
127  cur_body->FinalizePosition(max_pos);
128  }
129  }
130 
131  };
132 
133 
134 }
135 
136 #endif
emp::vector< Ptr< BODY_TYPE > > & GetBodySet()
Definition: Surface2D.h:52
constexpr TYPE GetX() const
Definition: Point2D.h:39
Surface2D & Clear()
Definition: Surface2D.h:62
const emp::vector< Ptr< BODY_TYPE > > & GetConstBodySet() const
Definition: Surface2D.h:53
Definition: Surface2D.h:38
void push_back(PB_Ts &&...args)
Definition: vector.h:189
Surface2D & AddBody(Ptr< BODY_TYPE > new_body)
Definition: Surface2D.h:56
double GetWidth() const
Definition: Surface2D.h:48
size_t size() const
Definition: vector.h:151
void TestCollisions(std::function< bool(BODY_TYPE &, BODY_TYPE &)> collide_fun)
Definition: Surface2D.h:71
~Surface2D()
Definition: Surface2D.h:46
double GetHeight() const
Definition: Surface2D.h:49
const Point & GetMaxPosition() const
Definition: Surface2D.h:50
If we are in emscripten, make sure to include the header.
Definition: array.h:37
Build a debug wrapper emp::vector around std::vector.
Definition: vector.h:42
#define emp_assert(...)
Definition: assert.h:199
constexpr TYPE GetY() const
Definition: Point2D.h:40
Surface2D(double _width, double _height)
Definition: Surface2D.h:44