Pyrogenesis  trunk
Spatial.h
Go to the documentation of this file.
1 /* Copyright (C) 2016 Wildfire Games.
2  * This file is part of 0 A.D.
3  *
4  * 0 A.D. is free software: you can redistribute it and/or modify
5  * it under the terms of the GNU General Public License as published by
6  * the Free Software Foundation, either version 2 of the License, or
7  * (at your option) any later version.
8  *
9  * 0 A.D. is distributed in the hope that it will be useful,
10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12  * GNU General Public License for more details.
13  *
14  * You should have received a copy of the GNU General Public License
15  * along with 0 A.D. If not, see <http://www.gnu.org/licenses/>.
16  */
17 
18 #ifndef INCLUDED_SPATIAL
19 #define INCLUDED_SPATIAL
20 
22 
23 /**
24  * A very basic subdivision scheme for finding items in ranges.
25  * Items are stored in lists in dynamic-sized divisions.
26  * Items have a size (min/max values of their axis-aligned bounding box)
27  * and are stored in all divisions overlapping that area.
28  *
29  * It is the caller's responsibility to ensure items are only added
30  * once, aren't removed unless they've been added, etc, and that
31  * Move/Remove are called with the same coordinates originally passed
32  * to Add (since this class doesn't remember which divisions an item
33  * occupies).
34  */
36 {
38  {
39  std::vector<uint32_t> items;
40 
41  inline void push_back(uint32_t value)
42  {
43  items.push_back(value);
44  }
45 
46  inline void erase(int index)
47  {
48  // Delete by swapping with the last element then popping
49  if ((int)items.size() > 1) // but only if we have more than 1 elements
50  items[index] = items.back();
51  items.pop_back();
52  }
53 
54  void copy_items_at_end(std::vector<uint32_t>& out) const
55  {
56  out.insert(out.end(), items.begin(), items.end());
57  }
58  };
59 
60 
65 
67 
68 public:
69  SpatialSubdivision() : m_Divisions(NULL), m_DivisionsW(0), m_DivisionsH(0)
70  {
71  }
73  {
74  delete[] m_Divisions;
75  }
77  {
78  m_DivisionSize = rhs.m_DivisionSize;
79  m_DivisionsW = rhs.m_DivisionsW;
80  m_DivisionsH = rhs.m_DivisionsH;
81  size_t n = m_DivisionsW * m_DivisionsH;
82  m_Divisions = new SubDivisionGrid[n];
83  for (size_t i = 0; i < n; ++i)
84  m_Divisions[i] = rhs.m_Divisions[i]; // just fall back to piecemeal copy
85  }
87  {
88  if (this != &rhs)
89  {
90  m_DivisionSize = rhs.m_DivisionSize;
91  size_t n = rhs.m_DivisionsW * rhs.m_DivisionsH;
92  if (m_DivisionsW != rhs.m_DivisionsW || m_DivisionsH != rhs.m_DivisionsH)
93  Create(n); // size changed, recreate
94 
95  m_DivisionsW = rhs.m_DivisionsW;
96  m_DivisionsH = rhs.m_DivisionsH;
97  for (size_t i = 0; i < n; ++i)
98  m_Divisions[i] = rhs.m_Divisions[i]; // just fall back to piecemeal copy
99  }
100  return *this;
101  }
102 
103  inline entity_pos_t GetDivisionSize() const { return m_DivisionSize; }
104  inline uint32_t GetWidth() const { return m_DivisionsW; }
105  inline uint32_t GetHeight() const { return m_DivisionsH; }
106 
107  void Create(size_t count)
108  {
109  delete[] m_Divisions;
110  m_Divisions = new SubDivisionGrid[count];
111  }
112 
113  /**
114  * Equivalence test (ignoring order of items within each subdivision)
115  */
116  bool operator==(const SpatialSubdivision& rhs) const
117  {
118  if (m_DivisionSize != rhs.m_DivisionSize || m_DivisionsW != rhs.m_DivisionsW || m_DivisionsH != rhs.m_DivisionsH)
119  return false;
120 
121  uint32_t n = m_DivisionsH * m_DivisionsW;
122  for (uint32_t i = 0; i < n; ++i)
123  {
124  if (m_Divisions[i].items.size() != rhs.m_Divisions[i].items.size())
125  return false;
126 
127  // don't bother optimizing this, this is only used in the TESTING SUITE
128  std::vector<uint32_t> a = m_Divisions[i].items;
129  std::vector<uint32_t> b = rhs.m_Divisions[i].items;
130  std::sort(a.begin(), a.end());
131  std::sort(b.begin(), b.end());
132  if (a != b)
133  return false;
134  }
135  return true;
136  }
137 
138  inline bool operator!=(const SpatialSubdivision& rhs) const
139  {
140  return !(*this == rhs);
141  }
142 
143  void Reset(entity_pos_t maxX, entity_pos_t maxZ, entity_pos_t divisionSize)
144  {
145  m_DivisionSize = divisionSize;
146  m_DivisionsW = (maxX / m_DivisionSize).ToInt_RoundToInfinity();
147  m_DivisionsH = (maxZ / m_DivisionSize).ToInt_RoundToInfinity();
148 
149  Create(m_DivisionsW * m_DivisionsH);
150  }
151 
152 
153  /**
154  * Add an item with the given 'to' size.
155  * The item must not already be present.
156  */
157  void Add(uint32_t item, CFixedVector2D toMin, CFixedVector2D toMax)
158  {
159  ENSURE(toMin.X <= toMax.X && toMin.Y <= toMax.Y);
160 
161  u32 i0 = GetI0(toMin.X);
162  u32 j0 = GetJ0(toMin.Y);
163  u32 i1 = GetI1(toMax.X);
164  u32 j1 = GetJ1(toMax.Y);
165  for (u32 j = j0; j <= j1; ++j)
166  {
167  for (u32 i = i0; i <= i1; ++i)
168  {
169  m_Divisions[i + j*m_DivisionsW].push_back(item);
170  }
171  }
172  }
173 
174  /**
175  * Remove an item with the given 'from' size.
176  * The item should already be present.
177  * The size must match the size that was last used when adding the item.
178  */
179  void Remove(uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax)
180  {
181  ENSURE(fromMin.X <= fromMax.X && fromMin.Y <= fromMax.Y);
182 
183  u32 i0 = GetI0(fromMin.X);
184  u32 j0 = GetJ0(fromMin.Y);
185  u32 i1 = GetI1(fromMax.X);
186  u32 j1 = GetJ1(fromMax.Y);
187  for (u32 j = j0; j <= j1; ++j)
188  {
189  for (u32 i = i0; i <= i1; ++i)
190  {
191  SubDivisionGrid& div = m_Divisions[i + j*m_DivisionsW];
192  int size = div.items.size();
193  for (int n = 0; n < size; ++n)
194  {
195  if (div.items[n] == item)
196  {
197  div.erase(n);
198  break;
199  }
200  }
201  }
202  }
203  }
204 
205  /**
206  * Equivalent to Remove() then Add(), but potentially faster.
207  */
208  void Move(uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax, CFixedVector2D toMin, CFixedVector2D toMax)
209  {
210  // Skip the work if we're staying in the same divisions
211  if (GetIndex0(fromMin) == GetIndex0(toMin) && GetIndex1(fromMax) == GetIndex1(toMax))
212  return;
213 
214  Remove(item, fromMin, fromMax);
215  Add(item, toMin, toMax);
216  }
217 
218  /**
219  * Convenience function for Add() of individual points.
220  * (Note that points on a boundary may occupy multiple divisions.)
221  */
222  void Add(uint32_t item, CFixedVector2D to)
223  {
224  Add(item, to, to);
225  }
226 
227  /**
228  * Convenience function for Remove() of individual points.
229  */
230  void Remove(uint32_t item, CFixedVector2D from)
231  {
232  Remove(item, from, from);
233  }
234 
235  /**
236  * Convenience function for Move() of individual points.
237  */
239  {
240  Move(item, from, from, to, to);
241  }
242 
243  /**
244  * Returns a sorted list of unique items that includes all items
245  * within the given axis-aligned square range.
246  */
247  void GetInRange(std::vector<uint32_t>& out, CFixedVector2D posMin, CFixedVector2D posMax) const
248  {
249  out.clear();
250  ENSURE(posMin.X <= posMax.X && posMin.Y <= posMax.Y);
251 
252  u32 i0 = GetI0(posMin.X);
253  u32 j0 = GetJ0(posMin.Y);
254  u32 i1 = GetI1(posMax.X);
255  u32 j1 = GetJ1(posMax.Y);
256  for (u32 j = j0; j <= j1; ++j)
257  {
258  for (u32 i = i0; i <= i1; ++i)
259  {
260  m_Divisions[i + j*m_DivisionsW].copy_items_at_end(out);
261  }
262  }
263  // some buildings span several tiles, so we need to make it unique
264  std::sort(out.begin(), out.end());
265  out.erase(std::unique(out.begin(), out.end()), out.end());
266  }
267 
268  /**
269  * Returns a sorted list of unique items that includes all items
270  * within the given circular distance of the given point.
271  */
272  void GetNear(std::vector<uint32_t>& out, CFixedVector2D pos, entity_pos_t range) const
273  {
274  // TODO: be cleverer and return a circular pattern of divisions,
275  // not this square over-approximation
276  CFixedVector2D r(range, range);
277  GetInRange(out, pos - r, pos + r);
278  }
279 
280 private:
281  // Helper functions for translating coordinates into division indexes
282  // (avoiding out-of-bounds accesses, and rounding correctly so that
283  // points precisely between divisions are counted in both):
284 
286  {
287  return Clamp((x / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (int)m_DivisionsW-1);
288  }
289 
291  {
292  return Clamp((z / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (int)m_DivisionsH-1);
293  }
294 
296  {
297  return Clamp((x / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (int)m_DivisionsW-1);
298  }
299 
301  {
302  return Clamp((z / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (int)m_DivisionsH-1);
303  }
304 
306  {
307  return GetI0(pos.X) + GetJ0(pos.Y)*m_DivisionsW;
308  }
309 
311  {
312  return GetI1(pos.X) + GetJ1(pos.Y)*m_DivisionsW;
313  }
314 };
315 
316 /**
317  * Serialization helper template for SpatialSubdivision
318  */
319 template<>
321 {
322  void operator()(ISerializer& serialize, const char* UNUSED(name), SpatialSubdivision& value)
323  {
324  serialize.NumberFixed_Unbounded("div size", value.m_DivisionSize);
325  serialize.NumberU32_Unbounded("divs w", value.m_DivisionsW);
326  serialize.NumberU32_Unbounded("divs h", value.m_DivisionsH);
327 
328  size_t count = value.m_DivisionsH * value.m_DivisionsW;
329  for (size_t i = 0; i < count; ++i)
330  Serializer(serialize, "subdiv items", value.m_Divisions[i].items);
331  }
332 
333  void operator()(IDeserializer& serialize, const char* UNUSED(name), SpatialSubdivision& value)
334  {
335  serialize.NumberFixed_Unbounded("div size", value.m_DivisionSize);
336  serialize.NumberU32_Unbounded("divs w", value.m_DivisionsW);
337  serialize.NumberU32_Unbounded("divs h", value.m_DivisionsH);
338 
339  size_t count = value.m_DivisionsW * value.m_DivisionsH;
340  value.Create(count);
341  for (size_t i = 0; i < count; ++i)
342  Serializer(serialize, "subdiv items", value.m_Divisions[i].items);
343  }
344 };
345 
346 
347 /**
348  * A basic square subdivision scheme for finding entities in range
349  * More efficient than SpatialSubdivision, but a bit less precise
350  * (so the querier will get more entities to perform tests on).
351  *
352  * Items are stored in vectors in fixed-size divisions.
353  *
354  * Items have a size (min/max values of their axis-aligned bounding box).
355  * If that size is higher than a subdivision's size, they're stored in the "general" vector
356  * This means that if too many objects have a size that's big, it'll end up being slow
357  * We want subdivisions to be as small as possible yet contain as many items as possible.
358  *
359  * It is the caller's responsibility to ensure items are only added once, aren't removed
360  * unless they've been added, etc, and that Move/Remove are called with the same coordinates
361  * originally passed to Add (since this class doesn't remember which divisions an item
362  * occupies).
363  *
364  * TODO: If a unit size were to change, it would need to be updated (that doesn't happen for now)
365  */
367 {
368 private:
369  static const int SUBDIVISION_SIZE = 20; // bigger than most buildings and entities
370 
371  std::vector<entity_id_t> m_OverSizedData;
372  std::vector<entity_id_t>* m_SpatialDivisionsData; // fixed size array of subdivisions
373  size_t m_ArrayWidth; // number of columns in m_SpatialDivisionsData
374 
375  inline size_t Index(fixed position) const
376  {
377  return Clamp((position / SUBDIVISION_SIZE).ToInt_RoundToZero(), 0, (int)m_ArrayWidth-1);
378  }
379 
380  inline size_t SubdivisionIdx(CFixedVector2D position) const
381  {
382  return Index(position.X) + Index(position.Y)*m_ArrayWidth;
383  }
384 
385  /**
386  * Efficiently erase from a vector by swapping with the last element and popping it.
387  * Returns true if the element was found and erased, else returns false.
388  */
389  bool EraseFrom(std::vector<entity_id_t>& vector, entity_id_t item)
390  {
391  std::vector<entity_id_t>::iterator it = std::find(vector.begin(), vector.end(), item);
392  if (it == vector.end())
393  return false;
394 
395  *it = vector.back();
396  vector.pop_back();
397  return true;
398  }
399 
400 public:
402  m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
403  {
404  }
405 
407  m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
408  {
409  Reset(other.m_ArrayWidth);
410  std::copy(&other.m_SpatialDivisionsData[0], &other.m_SpatialDivisionsData[m_ArrayWidth*m_ArrayWidth], m_SpatialDivisionsData);
411  }
412 
414  {
415  delete[] m_SpatialDivisionsData;
416  }
417 
418  void Reset(size_t arrayWidth)
419  {
420  delete[] m_SpatialDivisionsData;
421 
422  m_ArrayWidth = arrayWidth;
423  m_SpatialDivisionsData = new std::vector<entity_id_t>[m_ArrayWidth*m_ArrayWidth];
424  m_OverSizedData.clear();
425  }
426 
427  void Reset(fixed w, fixed h)
428  {
429  ENSURE(w >= fixed::Zero() && h >= fixed::Zero());
430  size_t arrayWidth = std::max((w / SUBDIVISION_SIZE).ToInt_RoundToZero(), (h / SUBDIVISION_SIZE).ToInt_RoundToZero()) + 1;
431  Reset(arrayWidth);
432  }
433 
435  {
436  if (this != &other)
437  {
438  Reset(other.m_ArrayWidth);
439  std::copy(&other.m_SpatialDivisionsData[0], &other.m_SpatialDivisionsData[m_ArrayWidth*m_ArrayWidth], m_SpatialDivisionsData);
440  }
441  return *this;
442  }
443 
444  bool operator==(const FastSpatialSubdivision& other) const
445  {
446  if (m_ArrayWidth != other.m_ArrayWidth)
447  return false;
448  if (m_OverSizedData != other.m_OverSizedData)
449  return false;
450  for (size_t idx = 0; idx < m_ArrayWidth*m_ArrayWidth; ++idx)
451  if (m_SpatialDivisionsData[idx] != other.m_SpatialDivisionsData[idx])
452  return false;
453  return true;
454  }
455 
456  inline bool operator!=(const FastSpatialSubdivision& rhs) const
457  {
458  return !(*this == rhs);
459  }
460 
461  /**
462  * Add an item.
463  */
464  void Add(entity_id_t item, CFixedVector2D position, u32 size)
465  {
466  if (size > SUBDIVISION_SIZE)
467  {
468  if (std::find(m_OverSizedData.begin(), m_OverSizedData.end(), item) == m_OverSizedData.end())
469  m_OverSizedData.push_back(item);
470  }
471  else
472  {
473  std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[SubdivisionIdx(position)];
474  if (std::find(subdivision.begin(), subdivision.end(), item) == subdivision.end())
475  subdivision.push_back(item);
476  }
477  }
478 
479  /**
480  * Remove an item.
481  * Position must be where we expect to find it, or we won't find it.
482  */
483  void Remove(entity_id_t item, CFixedVector2D position, u32 size)
484  {
485  if (size > SUBDIVISION_SIZE)
486  EraseFrom(m_OverSizedData, item);
487  else
488  {
489  std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[SubdivisionIdx(position)];
490  EraseFrom(subdivision, item);
491  }
492  }
493 
494  /**
495  * Equivalent to Remove() then Add(), but slightly faster.
496  * In particular for big objects nothing needs to be done.
497  */
498  void Move(entity_id_t item, CFixedVector2D oldPosition, CFixedVector2D newPosition, u32 size)
499  {
500  if (size > SUBDIVISION_SIZE)
501  return;
502  if (SubdivisionIdx(newPosition) == SubdivisionIdx(oldPosition))
503  return;
504 
505  std::vector<entity_id_t>& oldSubdivision = m_SpatialDivisionsData[SubdivisionIdx(oldPosition)];
506  if (EraseFrom(oldSubdivision, item))
507  {
508  std::vector<entity_id_t>& newSubdivision = m_SpatialDivisionsData[SubdivisionIdx(newPosition)];
509  newSubdivision.push_back(item);
510  }
511  }
512 
513  /**
514  * Returns a (non sorted) list of items that are either in the square or close to it.
515  * It's the responsibility of the querier to do proper distance checking and entity sorting.
516  */
517  void GetInRange(std::vector<entity_id_t>& out, CFixedVector2D posMin, CFixedVector2D posMax) const
518  {
519  size_t minX = Index(posMin.X);
520  size_t minY = Index(posMin.Y);
521  size_t maxX = Index(posMax.X) + 1;
522  size_t maxY = Index(posMax.Y) + 1;
523 
524  // Now expand the subdivisions by one so we make sure we've got all elements potentially in range.
525  // Also make sure min >= 0 and max <= width
526  minX = minX > 0 ? minX-1 : 0;
527  minY = minY > 0 ? minY-1 : 0;
528  maxX = maxX < m_ArrayWidth ? maxX+1 : m_ArrayWidth;
529  maxY = maxY < m_ArrayWidth ? maxY+1 : m_ArrayWidth;
530 
531  ENSURE(out.empty() && "GetInRange: out is not clean");
532 
533  // Add oversized items, they can be anywhere
534  out.insert(out.end(), m_OverSizedData.begin(), m_OverSizedData.end());
535 
536  for (size_t Y = minY; Y < maxY; ++Y)
537  {
538  for (size_t X = minX; X < maxX; ++X)
539  {
540  std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[X + Y*m_ArrayWidth];
541  if (!subdivision.empty())
542  out.insert(out.end(), subdivision.begin(), subdivision.end());
543  }
544  }
545  }
546 
547  /**
548  * Returns a (non sorted) list of items that are either in the circle or close to it.
549  * It's the responsibility of the querier to do proper distance checking and entity sorting.
550  */
551  void GetNear(std::vector<entity_id_t>& out, CFixedVector2D pos, entity_pos_t range) const
552  {
553  // Because the subdivision size is rather big wrt typical ranges,
554  // this square over-approximation is hopefully not too bad.
555  CFixedVector2D r(range, range);
556  GetInRange(out, pos - r, pos + r);
557  }
558 
559  size_t GetDivisionSize() const
560  {
561  return SUBDIVISION_SIZE;
562  }
563 
564  size_t GetWidth() const
565  {
566  return m_ArrayWidth;
567  }
568 };
569 
570 #endif // INCLUDED_SPATIAL
uint32_t GetHeight() const
Definition: Spatial.h:105
A simple fixed-point number class.
Definition: Fixed.h:119
Definition: Decompose.h:22
void NumberFixed_Unbounded(const char *name, fixed value)
Serialize a number.
Definition: ISerializer.h:191
Helper templates definitions for serializing/deserializing common objects.
Definition: FixedVector2D.h:24
#define UNUSED(param)
mark a function parameter as unused and avoid the corresponding compiler warning. ...
Definition: code_annotation.h:38
void operator()(IDeserializer &serialize, const char *name, SpatialSubdivision &value)
Definition: Spatial.h:333
T Clamp(T value, T min, T max)
Definition: MathUtil.h:32
static CFixed Zero()
Definition: Fixed.h:131
size_t GetWidth() const
Definition: Spatial.h:564
void Remove(uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax)
Remove an item with the given &#39;from&#39; size.
Definition: Spatial.h:179
void Reset(entity_pos_t maxX, entity_pos_t maxZ, entity_pos_t divisionSize)
Definition: Spatial.h:143
uint32_t m_DivisionsH
Definition: Spatial.h:64
Serialization interface; see serialization overview.
Definition: ISerializer.h:120
SpatialSubdivision & operator=(const SpatialSubdivision &rhs)
Definition: Spatial.h:86
void GetNear(std::vector< uint32_t > &out, CFixedVector2D pos, entity_pos_t range) const
Returns a sorted list of unique items that includes all items within the given circular distance of t...
Definition: Spatial.h:272
static void out(const wchar_t *fmt,...)
Definition: wdbg_sym.cpp:421
void Create(size_t count)
Definition: Spatial.h:107
void Serializer(S &serialize, const char *name, Args &&... args)
Definition: SerializeTemplates.h:51
FastSpatialSubdivision & operator=(const FastSpatialSubdivision &other)
Definition: Spatial.h:434
void Remove(entity_id_t item, CFixedVector2D position, u32 size)
Remove an item.
Definition: Spatial.h:483
~FastSpatialSubdivision()
Definition: Spatial.h:413
bool operator==(const FastSpatialSubdivision &other) const
Definition: Spatial.h:444
void Add(entity_id_t item, CFixedVector2D position, u32 size)
Add an item.
Definition: Spatial.h:464
virtual void NumberU32_Unbounded(const char *name, uint32_t &out)
Definition: IDeserializer.cpp:124
void Reset(size_t arrayWidth)
Definition: Spatial.h:418
virtual void NumberFixed_Unbounded(const char *name, fixed &out)
Definition: IDeserializer.cpp:148
entity_pos_t m_DivisionSize
Definition: Spatial.h:61
uint32_t GetJ0(entity_pos_t z) const
Definition: Spatial.h:290
std::vector< entity_id_t > m_OverSizedData
Definition: Spatial.h:371
void operator()(ISerializer &serialize, const char *name, SpatialSubdivision &value)
Definition: Spatial.h:322
uint32_t GetI0(entity_pos_t x) const
Definition: Spatial.h:285
bool operator==(const SpatialSubdivision &rhs) const
Equivalence test (ignoring order of items within each subdivision)
Definition: Spatial.h:116
size_t GetDivisionSize() const
Definition: Spatial.h:559
bool operator!=(const FastSpatialSubdivision &rhs) const
Definition: Spatial.h:456
void Remove(uint32_t item, CFixedVector2D from)
Convenience function for Remove() of individual points.
Definition: Spatial.h:230
fixed Y
Definition: FixedVector2D.h:27
void copy_items_at_end(std::vector< uint32_t > &out) const
Definition: Spatial.h:54
bool EraseFrom(std::vector< entity_id_t > &vector, entity_id_t item)
Efficiently erase from a vector by swapping with the last element and popping it. ...
Definition: Spatial.h:389
entity_pos_t GetDivisionSize() const
Definition: Spatial.h:103
#define ENSURE(expr)
ensure the expression <expr> evaluates to non-zero.
Definition: debug.h:290
uint32_t u32
Definition: types.h:39
uint32_t GetIndex0(CFixedVector2D pos) const
Definition: Spatial.h:305
void Move(entity_id_t item, CFixedVector2D oldPosition, CFixedVector2D newPosition, u32 size)
Equivalent to Remove() then Add(), but slightly faster.
Definition: Spatial.h:498
void GetInRange(std::vector< entity_id_t > &out, CFixedVector2D posMin, CFixedVector2D posMax) const
Returns a (non sorted) list of items that are either in the square or close to it.
Definition: Spatial.h:517
uint32_t GetIndex1(CFixedVector2D pos) const
Definition: Spatial.h:310
bool operator!=(const SpatialSubdivision &rhs) const
Definition: Spatial.h:138
A basic square subdivision scheme for finding entities in range More efficient than SpatialSubdivisio...
Definition: Spatial.h:366
uint32_t GetWidth() const
Definition: Spatial.h:104
void Reset(fixed w, fixed h)
Definition: Spatial.h:427
void GetNear(std::vector< entity_id_t > &out, CFixedVector2D pos, entity_pos_t range) const
Returns a (non sorted) list of items that are either in the circle or close to it.
Definition: Spatial.h:551
size_t Index(fixed position) const
Definition: Spatial.h:375
size_t m_ArrayWidth
Definition: Spatial.h:373
void push_back(uint32_t value)
Definition: Spatial.h:41
void NumberU32_Unbounded(const char *name, uint32_t value)
Serialize a number.
Definition: ISerializer.h:171
Definition: SerializeTemplates.h:41
void Add(uint32_t item, CFixedVector2D to)
Convenience function for Add() of individual points.
Definition: Spatial.h:222
FastSpatialSubdivision()
Definition: Spatial.h:401
A very basic subdivision scheme for finding items in ranges.
Definition: Spatial.h:35
void erase(int index)
Definition: Spatial.h:46
#define X(id)
Definition: CStrIntern.cpp:90
~SpatialSubdivision()
Definition: Spatial.h:72
SubDivisionGrid * m_Divisions
Definition: Spatial.h:62
unsigned int uint32_t
Definition: wposix_types.h:53
FastSpatialSubdivision(const FastSpatialSubdivision &other)
Definition: Spatial.h:406
void Move(uint32_t item, CFixedVector2D from, CFixedVector2D to)
Convenience function for Move() of individual points.
Definition: Spatial.h:238
SpatialSubdivision(const SpatialSubdivision &rhs)
Definition: Spatial.h:76
fixed X
Definition: FixedVector2D.h:27
size_t SubdivisionIdx(CFixedVector2D position) const
Definition: Spatial.h:380
uint32_t m_DivisionsW
Definition: Spatial.h:63
void Move(uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax, CFixedVector2D toMin, CFixedVector2D toMax)
Equivalent to Remove() then Add(), but potentially faster.
Definition: Spatial.h:208
void GetInRange(std::vector< uint32_t > &out, CFixedVector2D posMin, CFixedVector2D posMax) const
Returns a sorted list of unique items that includes all items within the given axis-aligned square ra...
Definition: Spatial.h:247
uint32_t GetI1(entity_pos_t x) const
Definition: Spatial.h:295
void Add(uint32_t item, CFixedVector2D toMin, CFixedVector2D toMax)
Add an item with the given &#39;to&#39; size.
Definition: Spatial.h:157
u32 entity_id_t
Entity ID type.
Definition: Entity.h:23
std::vector< uint32_t > items
Definition: Spatial.h:39
SpatialSubdivision()
Definition: Spatial.h:69
std::vector< entity_id_t > * m_SpatialDivisionsData
Definition: Spatial.h:372
Definition: Spatial.h:37
uint32_t GetJ1(entity_pos_t z) const
Definition: Spatial.h:300
Deserialization interface; see serialization overview.
Definition: IDeserializer.h:34