LCOV - code coverage report
Current view: top level - source/simulation2/helpers - Spatial.h (source / functions) Hit Total Coverage
Test: 0 A.D. test coverage report Lines: 134 197 68.0 %
Date: 2023-01-19 00:18:29 Functions: 29 39 74.4 %

          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

Generated by: LCOV version 1.13