FastSpatialSubdivision Class Reference

A basic square subdivision scheme for finding entities in range More efficient than SpatialSubdivision, but a bit less precise (so the querier will get more entities to perform tests on). More...

#include <Spatial.h>

Public Member Functions
	FastSpatialSubdivision ()
	FastSpatialSubdivision (const FastSpatialSubdivision &other)
	~FastSpatialSubdivision ()
void	Reset (size_t arrayWidth)
void	Reset (fixed w, fixed h)
FastSpatialSubdivision &	operator= (const FastSpatialSubdivision &other)
bool	operator== (const FastSpatialSubdivision &other) const
bool	operator!= (const FastSpatialSubdivision &rhs) const
void	Add (entity_id_t item, CFixedVector2D position, u32 size)
	Add an item. More...
void	Remove (entity_id_t item, CFixedVector2D position, u32 size)
	Remove an item. More...
void	Move (entity_id_t item, CFixedVector2D oldPosition, CFixedVector2D newPosition, u32 size)
	Equivalent to Remove() then Add(), but slightly faster. More...
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. More...
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. More...
size_t	GetDivisionSize () const
size_t	GetWidth () const

Private Member Functions
size_t	Index (fixed position) const
size_t	SubdivisionIdx (CFixedVector2D position) const
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. More...

Private Attributes
std::vector< entity_id_t >	m_OverSizedData
std::vector< entity_id_t > *	m_SpatialDivisionsData
size_t	m_ArrayWidth

Static Private Attributes
static const int	SUBDIVISION_SIZE = 20

Detailed Description

A basic square subdivision scheme for finding entities in range More efficient than SpatialSubdivision, but a bit less precise (so the querier will get more entities to perform tests on).

Items are stored in vectors in fixed-size divisions.

Items have a size (min/max values of their axis-aligned bounding box). If that size is higher than a subdivision's size, they're stored in the "general" vector This means that if too many objects have a size that's big, it'll end up being slow We want subdivisions to be as small as possible yet contain as many items as possible.

It is the caller's responsibility to ensure items are only added once, aren't removed unless they've been added, etc, and that Move/Remove are called with the same coordinates originally passed to Add (since this class doesn't remember which divisions an item occupies).

TODO: If a unit size were to change, it would need to be updated (that doesn't happen for now)

Constructor & Destructor Documentation

FastSpatialSubdivision() [1/2]

FastSpatialSubdivision::FastSpatialSubdivision ( )

inline

FastSpatialSubdivision() [2/2]

FastSpatialSubdivision::FastSpatialSubdivision ( const FastSpatialSubdivision &  other )

inline

~FastSpatialSubdivision()

FastSpatialSubdivision::~FastSpatialSubdivision ( )

inline

Member Function Documentation

Add()

void FastSpatialSubdivision::Add ( entity_id_t  item, CFixedVector2D  position, u32  size  )

inline

Add an item.

EraseFrom()

bool FastSpatialSubdivision::EraseFrom ( std::vector< entity_id_t > &  vector, entity_id_t  item  )

inlineprivate

Efficiently erase from a vector by swapping with the last element and popping it.

Returns true if the element was found and erased, else returns false.

GetDivisionSize()

size_t FastSpatialSubdivision::GetDivisionSize ( ) const

inline

GetInRange()

void FastSpatialSubdivision::GetInRange ( std::vector< entity_id_t > &  out, CFixedVector2D  posMin, CFixedVector2D  posMax  ) const

inline

Returns a (non sorted) list of items that are either in the square or close to it.

It's the responsibility of the querier to do proper distance checking and entity sorting.

GetNear()

void FastSpatialSubdivision::GetNear ( std::vector< entity_id_t > &  out, CFixedVector2D  pos, entity_pos_t  range  ) const

inline

Returns a (non sorted) list of items that are either in the circle or close to it.

It's the responsibility of the querier to do proper distance checking and entity sorting.

GetWidth()

size_t FastSpatialSubdivision::GetWidth ( ) const

inline

Index()

size_t FastSpatialSubdivision::Index ( fixed  position ) const

inlineprivate

Move()

void FastSpatialSubdivision::Move ( entity_id_t  item, CFixedVector2D  oldPosition, CFixedVector2D  newPosition, u32  size  )

inline

Equivalent to Remove() then Add(), but slightly faster.

In particular for big objects nothing needs to be done.

operator!=()

bool FastSpatialSubdivision::operator!= ( const FastSpatialSubdivision &  rhs ) const

inline

operator=()

FastSpatialSubdivision & FastSpatialSubdivision::operator= ( const FastSpatialSubdivision &  other )

inline

operator==()

bool FastSpatialSubdivision::operator== ( const FastSpatialSubdivision &  other ) const

inline

Remove()

void FastSpatialSubdivision::Remove ( entity_id_t  item, CFixedVector2D  position, u32  size  )

inline

Remove an item.

Position must be where we expect to find it, or we won't find it.

Reset() [1/2]

void FastSpatialSubdivision::Reset ( fixed  w, fixed  h  )

inline

Reset() [2/2]

void FastSpatialSubdivision::Reset ( size_t  arrayWidth )

inline

SubdivisionIdx()

size_t FastSpatialSubdivision::SubdivisionIdx ( CFixedVector2D  position ) const

inlineprivate

Member Data Documentation

m_ArrayWidth

size_t FastSpatialSubdivision::m_ArrayWidth

private

m_OverSizedData

std::vector<entity_id_t> FastSpatialSubdivision::m_OverSizedData

private

m_SpatialDivisionsData

std::vector<entity_id_t>* FastSpatialSubdivision::m_SpatialDivisionsData

private

SUBDIVISION_SIZE

const int FastSpatialSubdivision::SUBDIVISION_SIZE = 20

staticprivate

---

The documentation for this class was generated from the following file:

• /home/docker/jenkins/workspace/technical-docs/source/simulation2/helpers/Spatial.h