Line data Source code
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 :
21 : #include "simulation2/serialization/SerializeTemplates.h"
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 : */
35 : class SpatialSubdivision
36 : {
37 86016 : struct SubDivisionGrid
38 : {
39 : std::vector<uint32_t> items;
40 :
41 30 : inline void push_back(uint32_t value)
42 : {
43 30 : items.push_back(value);
44 30 : }
45 :
46 0 : inline void erase(int index)
47 : {
48 : // Delete by swapping with the last element then popping
49 0 : if ((int)items.size() > 1) // but only if we have more than 1 elements
50 0 : items[index] = items.back();
51 0 : items.pop_back();
52 0 : }
53 :
54 102 : void copy_items_at_end(std::vector<uint32_t>& out) const
55 : {
56 102 : out.insert(out.end(), items.begin(), items.end());
57 102 : }
58 : };
59 :
60 :
61 : entity_pos_t m_DivisionSize;
62 : SubDivisionGrid* m_Divisions;
63 : uint32_t m_DivisionsW;
64 : uint32_t m_DivisionsH;
65 :
66 : friend struct SerializeHelper<SpatialSubdivision>;
67 :
68 : public:
69 24 : SpatialSubdivision() : m_Divisions(NULL), m_DivisionsW(0), m_DivisionsH(0)
70 : {
71 24 : }
72 24 : ~SpatialSubdivision()
73 24 : {
74 24 : delete[] m_Divisions;
75 24 : }
76 : SpatialSubdivision(const SpatialSubdivision& rhs)
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 : }
86 : SpatialSubdivision& operator=(const SpatialSubdivision& rhs)
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 42 : void Create(size_t count)
108 : {
109 42 : delete[] m_Divisions;
110 42 : m_Divisions = new SubDivisionGrid[count];
111 42 : }
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 42 : void Reset(entity_pos_t maxX, entity_pos_t maxZ, entity_pos_t divisionSize)
144 : {
145 42 : m_DivisionSize = divisionSize;
146 42 : m_DivisionsW = (maxX / m_DivisionSize).ToInt_RoundToInfinity();
147 42 : m_DivisionsH = (maxZ / m_DivisionSize).ToInt_RoundToInfinity();
148 :
149 42 : Create(m_DivisionsW * m_DivisionsH);
150 42 : }
151 :
152 :
153 : /**
154 : * Add an item with the given 'to' size.
155 : * The item must not already be present.
156 : */
157 30 : void Add(uint32_t item, CFixedVector2D toMin, CFixedVector2D toMax)
158 : {
159 30 : ENSURE(toMin.X <= toMax.X && toMin.Y <= toMax.Y);
160 :
161 30 : u32 i0 = GetI0(toMin.X);
162 30 : u32 j0 = GetJ0(toMin.Y);
163 30 : u32 i1 = GetI1(toMax.X);
164 30 : u32 j1 = GetJ1(toMax.Y);
165 60 : for (u32 j = j0; j <= j1; ++j)
166 : {
167 60 : for (u32 i = i0; i <= i1; ++i)
168 : {
169 30 : m_Divisions[i + j*m_DivisionsW].push_back(item);
170 : }
171 : }
172 30 : }
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 0 : void Remove(uint32_t item, CFixedVector2D fromMin, CFixedVector2D fromMax)
180 : {
181 0 : ENSURE(fromMin.X <= fromMax.X && fromMin.Y <= fromMax.Y);
182 :
183 0 : u32 i0 = GetI0(fromMin.X);
184 0 : u32 j0 = GetJ0(fromMin.Y);
185 0 : u32 i1 = GetI1(fromMax.X);
186 0 : u32 j1 = GetJ1(fromMax.Y);
187 0 : for (u32 j = j0; j <= j1; ++j)
188 : {
189 0 : for (u32 i = i0; i <= i1; ++i)
190 : {
191 0 : SubDivisionGrid& div = m_Divisions[i + j*m_DivisionsW];
192 0 : int size = div.items.size();
193 0 : for (int n = 0; n < size; ++n)
194 : {
195 0 : if (div.items[n] == item)
196 : {
197 0 : div.erase(n);
198 0 : break;
199 : }
200 : }
201 : }
202 : }
203 0 : }
204 :
205 : /**
206 : * Equivalent to Remove() then Add(), but potentially faster.
207 : */
208 0 : 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 0 : if (GetIndex0(fromMin) == GetIndex0(toMin) && GetIndex1(fromMax) == GetIndex1(toMax))
212 0 : return;
213 :
214 0 : Remove(item, fromMin, fromMax);
215 0 : 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 : */
238 : void Move(uint32_t item, CFixedVector2D from, CFixedVector2D to)
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 102 : void GetInRange(std::vector<uint32_t>& out, CFixedVector2D posMin, CFixedVector2D posMax) const
248 : {
249 102 : out.clear();
250 102 : ENSURE(posMin.X <= posMax.X && posMin.Y <= posMax.Y);
251 :
252 102 : u32 i0 = GetI0(posMin.X);
253 102 : u32 j0 = GetJ0(posMin.Y);
254 102 : u32 i1 = GetI1(posMax.X);
255 102 : u32 j1 = GetJ1(posMax.Y);
256 204 : for (u32 j = j0; j <= j1; ++j)
257 : {
258 204 : for (u32 i = i0; i <= i1; ++i)
259 : {
260 102 : 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 102 : std::sort(out.begin(), out.end());
265 102 : out.erase(std::unique(out.begin(), out.end()), out.end());
266 102 : }
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 36 : 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 36 : CFixedVector2D r(range, range);
277 36 : GetInRange(out, pos - r, pos + r);
278 36 : }
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 :
285 132 : uint32_t GetI0(entity_pos_t x) const
286 : {
287 132 : return Clamp((x / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (int)m_DivisionsW-1);
288 : }
289 :
290 132 : uint32_t GetJ0(entity_pos_t z) const
291 : {
292 132 : return Clamp((z / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (int)m_DivisionsH-1);
293 : }
294 :
295 132 : uint32_t GetI1(entity_pos_t x) const
296 : {
297 132 : return Clamp((x / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (int)m_DivisionsW-1);
298 : }
299 :
300 132 : uint32_t GetJ1(entity_pos_t z) const
301 : {
302 132 : return Clamp((z / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (int)m_DivisionsH-1);
303 : }
304 :
305 0 : uint32_t GetIndex0(CFixedVector2D pos) const
306 : {
307 0 : return GetI0(pos.X) + GetJ0(pos.Y)*m_DivisionsW;
308 : }
309 :
310 0 : uint32_t GetIndex1(CFixedVector2D pos) const
311 : {
312 0 : return GetI1(pos.X) + GetJ1(pos.Y)*m_DivisionsW;
313 : }
314 : };
315 :
316 : /**
317 : * Serialization helper template for SpatialSubdivision
318 : */
319 : template<>
320 : struct SerializeHelper<SpatialSubdivision>
321 : {
322 0 : void operator()(ISerializer& serialize, const char* UNUSED(name), SpatialSubdivision& value)
323 : {
324 0 : serialize.NumberFixed_Unbounded("div size", value.m_DivisionSize);
325 0 : serialize.NumberU32_Unbounded("divs w", value.m_DivisionsW);
326 0 : serialize.NumberU32_Unbounded("divs h", value.m_DivisionsH);
327 :
328 0 : size_t count = value.m_DivisionsH * value.m_DivisionsW;
329 0 : for (size_t i = 0; i < count; ++i)
330 0 : Serializer(serialize, "subdiv items", value.m_Divisions[i].items);
331 0 : }
332 :
333 0 : void operator()(IDeserializer& serialize, const char* UNUSED(name), SpatialSubdivision& value)
334 : {
335 0 : serialize.NumberFixed_Unbounded("div size", value.m_DivisionSize);
336 0 : serialize.NumberU32_Unbounded("divs w", value.m_DivisionsW);
337 0 : serialize.NumberU32_Unbounded("divs h", value.m_DivisionsH);
338 :
339 0 : size_t count = value.m_DivisionsW * value.m_DivisionsH;
340 0 : value.Create(count);
341 0 : for (size_t i = 0; i < count; ++i)
342 0 : Serializer(serialize, "subdiv items", value.m_Divisions[i].items);
343 0 : }
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 : */
366 : class FastSpatialSubdivision
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 10360 : inline size_t Index(fixed position) const
376 : {
377 10360 : return Clamp((position / SUBDIVISION_SIZE).ToInt_RoundToZero(), 0, (int)m_ArrayWidth-1);
378 : }
379 :
380 5154 : inline size_t SubdivisionIdx(CFixedVector2D position) const
381 : {
382 5154 : 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 1024 : bool EraseFrom(std::vector<entity_id_t>& vector, entity_id_t item)
390 : {
391 1024 : std::vector<entity_id_t>::iterator it = std::find(vector.begin(), vector.end(), item);
392 1024 : if (it == vector.end())
393 0 : return false;
394 :
395 1024 : *it = vector.back();
396 1024 : vector.pop_back();
397 1024 : return true;
398 : }
399 :
400 : public:
401 6 : FastSpatialSubdivision() :
402 6 : m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
403 : {
404 6 : }
405 :
406 1037 : FastSpatialSubdivision(const FastSpatialSubdivision& other) :
407 1037 : m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
408 : {
409 1037 : Reset(other.m_ArrayWidth);
410 1037 : std::copy(&other.m_SpatialDivisionsData[0], &other.m_SpatialDivisionsData[m_ArrayWidth*m_ArrayWidth], m_SpatialDivisionsData);
411 1037 : }
412 :
413 1043 : ~FastSpatialSubdivision()
414 1043 : {
415 1043 : delete[] m_SpatialDivisionsData;
416 1043 : }
417 :
418 2082 : void Reset(size_t arrayWidth)
419 : {
420 2082 : delete[] m_SpatialDivisionsData;
421 :
422 2082 : m_ArrayWidth = arrayWidth;
423 2082 : m_SpatialDivisionsData = new std::vector<entity_id_t>[m_ArrayWidth*m_ArrayWidth];
424 2082 : m_OverSizedData.clear();
425 2082 : }
426 :
427 1045 : void Reset(fixed w, fixed h)
428 : {
429 1045 : ENSURE(w >= fixed::Zero() && h >= fixed::Zero());
430 1045 : size_t arrayWidth = std::max((w / SUBDIVISION_SIZE).ToInt_RoundToZero(), (h / SUBDIVISION_SIZE).ToInt_RoundToZero()) + 1;
431 1045 : Reset(arrayWidth);
432 1045 : }
433 :
434 : FastSpatialSubdivision& operator=(const FastSpatialSubdivision& other)
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 1037 : bool operator==(const FastSpatialSubdivision& other) const
445 : {
446 1037 : if (m_ArrayWidth != other.m_ArrayWidth)
447 0 : return false;
448 1037 : if (m_OverSizedData != other.m_OverSizedData)
449 0 : return false;
450 702049 : for (size_t idx = 0; idx < m_ArrayWidth*m_ArrayWidth; ++idx)
451 701012 : if (m_SpatialDivisionsData[idx] != other.m_SpatialDivisionsData[idx])
452 0 : return false;
453 1037 : return true;
454 : }
455 :
456 1037 : inline bool operator!=(const FastSpatialSubdivision& rhs) const
457 : {
458 1037 : return !(*this == rhs);
459 : }
460 :
461 : /**
462 : * Add an item.
463 : */
464 1036 : void Add(entity_id_t item, CFixedVector2D position, u32 size)
465 : {
466 1036 : if (size > SUBDIVISION_SIZE)
467 : {
468 0 : if (std::find(m_OverSizedData.begin(), m_OverSizedData.end(), item) == m_OverSizedData.end())
469 0 : m_OverSizedData.push_back(item);
470 : }
471 : else
472 : {
473 1036 : std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[SubdivisionIdx(position)];
474 1036 : if (std::find(subdivision.begin(), subdivision.end(), item) == subdivision.end())
475 1036 : subdivision.push_back(item);
476 : }
477 1036 : }
478 :
479 : /**
480 : * Remove an item.
481 : * Position must be where we expect to find it, or we won't find it.
482 : */
483 0 : void Remove(entity_id_t item, CFixedVector2D position, u32 size)
484 : {
485 0 : if (size > SUBDIVISION_SIZE)
486 0 : EraseFrom(m_OverSizedData, item);
487 : else
488 : {
489 0 : std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[SubdivisionIdx(position)];
490 0 : EraseFrom(subdivision, item);
491 : }
492 0 : }
493 :
494 : /**
495 : * Equivalent to Remove() then Add(), but slightly faster.
496 : * In particular for big objects nothing needs to be done.
497 : */
498 1035 : void Move(entity_id_t item, CFixedVector2D oldPosition, CFixedVector2D newPosition, u32 size)
499 : {
500 1035 : if (size > SUBDIVISION_SIZE)
501 0 : return;
502 1035 : if (SubdivisionIdx(newPosition) == SubdivisionIdx(oldPosition))
503 11 : return;
504 :
505 1024 : std::vector<entity_id_t>& oldSubdivision = m_SpatialDivisionsData[SubdivisionIdx(oldPosition)];
506 1024 : if (EraseFrom(oldSubdivision, item))
507 : {
508 1024 : std::vector<entity_id_t>& newSubdivision = m_SpatialDivisionsData[SubdivisionIdx(newPosition)];
509 1024 : 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 13 : void GetInRange(std::vector<entity_id_t>& out, CFixedVector2D posMin, CFixedVector2D posMax) const
518 : {
519 13 : size_t minX = Index(posMin.X);
520 13 : size_t minY = Index(posMin.Y);
521 13 : size_t maxX = Index(posMax.X) + 1;
522 13 : 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 13 : minX = minX > 0 ? minX-1 : 0;
527 13 : minY = minY > 0 ? minY-1 : 0;
528 13 : maxX = maxX < m_ArrayWidth ? maxX+1 : m_ArrayWidth;
529 13 : maxY = maxY < m_ArrayWidth ? maxY+1 : m_ArrayWidth;
530 :
531 13 : ENSURE(out.empty() && "GetInRange: out is not clean");
532 :
533 : // Add oversized items, they can be anywhere
534 13 : out.insert(out.end(), m_OverSizedData.begin(), m_OverSizedData.end());
535 :
536 63 : for (size_t Y = minY; Y < maxY; ++Y)
537 : {
538 270 : for (size_t X = minX; X < maxX; ++X)
539 : {
540 220 : std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[X + Y*m_ArrayWidth];
541 220 : if (!subdivision.empty())
542 15 : out.insert(out.end(), subdivision.begin(), subdivision.end());
543 : }
544 : }
545 13 : }
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 13 : 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 13 : CFixedVector2D r(range, range);
556 13 : GetInRange(out, pos - r, pos + r);
557 13 : }
558 :
559 0 : size_t GetDivisionSize() const
560 : {
561 0 : return SUBDIVISION_SIZE;
562 : }
563 :
564 0 : size_t GetWidth() const
565 : {
566 0 : return m_ArrayWidth;
567 : }
568 : };
569 :
570 : #endif // INCLUDED_SPATIAL
|
