18 #ifndef INCLUDED_SPATIAL 19 #define INCLUDED_SPATIAL 43 items.push_back(value);
49 if ((
int)items.size() > 1)
50 items[index] = items.back();
56 out.insert(out.end(), items.begin(), items.end());
83 for (
size_t i = 0; i < n; ++i)
97 for (
size_t i = 0; i < n; ++i)
128 std::vector<uint32_t> a = m_Divisions[i].
items;
130 std::sort(a.begin(), a.end());
131 std::sort(b.begin(), b.end());
140 return !(*
this == rhs);
145 m_DivisionSize = divisionSize;
149 Create(m_DivisionsW * m_DivisionsH);
159 ENSURE(toMin.
X <= toMax.
X && toMin.
Y <= toMax.
Y);
165 for (
u32 j = j0; j <= j1; ++j)
167 for (
u32 i = i0; i <= i1; ++i)
181 ENSURE(fromMin.
X <= fromMax.
X && fromMin.
Y <= fromMax.
Y);
187 for (
u32 j = j0; j <= j1; ++j)
189 for (
u32 i = i0; i <= i1; ++i)
192 int size = div.
items.size();
193 for (
int n = 0; n < size; ++n)
195 if (div.
items[n] == item)
214 Remove(item, fromMin, fromMax);
215 Add(item, toMin, toMax);
240 Move(item, from, from, to, to);
250 ENSURE(posMin.
X <= posMax.
X && posMin.
Y <= posMax.
Y);
256 for (
u32 j = j0; j <= j1; ++j)
258 for (
u32 i = i0; i <= i1; ++i)
264 std::sort(out.begin(), out.end());
265 out.erase(std::unique(out.begin(), out.end()), out.end());
287 return Clamp((x / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (
int)m_DivisionsW-1);
292 return Clamp((z / m_DivisionSize).ToInt_RoundToInfinity()-1, 0, (
int)m_DivisionsH-1);
297 return Clamp((x / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (
int)m_DivisionsW-1);
302 return Clamp((z / m_DivisionSize).ToInt_RoundToNegInfinity(), 0, (
int)m_DivisionsH-1);
329 for (
size_t i = 0; i < count; ++i)
341 for (
size_t i = 0; i < count; ++i)
369 static const int SUBDIVISION_SIZE = 20;
377 return Clamp((position / SUBDIVISION_SIZE).ToInt_RoundToZero(), 0, (
int)m_ArrayWidth-1);
382 return Index(position.
X) + Index(position.
Y)*m_ArrayWidth;
391 std::vector<entity_id_t>::iterator it = std::find(vector.begin(), vector.end(), item);
392 if (it == vector.end())
402 m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
407 m_SpatialDivisionsData(NULL), m_ArrayWidth(0)
415 delete[] m_SpatialDivisionsData;
420 delete[] m_SpatialDivisionsData;
422 m_ArrayWidth = arrayWidth;
423 m_SpatialDivisionsData =
new std::vector<entity_id_t>[m_ArrayWidth*m_ArrayWidth];
424 m_OverSizedData.clear();
430 size_t arrayWidth = std::max((w / SUBDIVISION_SIZE).ToInt_RoundToZero(), (h / SUBDIVISION_SIZE).ToInt_RoundToZero()) + 1;
450 for (
size_t idx = 0; idx < m_ArrayWidth*m_ArrayWidth; ++idx)
458 return !(*
this == rhs);
466 if (size > SUBDIVISION_SIZE)
468 if (std::find(m_OverSizedData.begin(), m_OverSizedData.end(), item) == m_OverSizedData.end())
469 m_OverSizedData.push_back(item);
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);
485 if (size > SUBDIVISION_SIZE)
486 EraseFrom(m_OverSizedData, item);
489 std::vector<entity_id_t>& subdivision = m_SpatialDivisionsData[SubdivisionIdx(position)];
490 EraseFrom(subdivision, item);
500 if (size > SUBDIVISION_SIZE)
502 if (SubdivisionIdx(newPosition) == SubdivisionIdx(oldPosition))
505 std::vector<entity_id_t>& oldSubdivision = m_SpatialDivisionsData[SubdivisionIdx(oldPosition)];
506 if (EraseFrom(oldSubdivision, item))
508 std::vector<entity_id_t>& newSubdivision = m_SpatialDivisionsData[SubdivisionIdx(newPosition)];
509 newSubdivision.push_back(item);
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;
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;
531 ENSURE(out.empty() &&
"GetInRange: out is not clean");
534 out.insert(out.end(), m_OverSizedData.begin(), m_OverSizedData.end());
536 for (
size_t Y = minY;
Y < maxY; ++
Y)
538 for (
size_t X = minX;
X < maxX; ++
X)
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());
561 return SUBDIVISION_SIZE;
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 'from' 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 'to' 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
uint32_t GetJ1(entity_pos_t z) const
Definition: Spatial.h:300
Deserialization interface; see serialization overview.
Definition: IDeserializer.h:34