#include <HierarchicalHashGrid2D.h>

Classes
struct	FCell

struct	FCellLocation

struct	FCellRect

struct	FCellRectIterator

struct	FItem

Public Types
typedef InItemIDType	ItemIDType

Public Member Functions
	THierarchicalHashGrid2D (const float InCellSize=500.f)

void	Initialize (const float InCellSize)

void	Reset ()

FCellLocation	Add (const ItemIDType ID, const FBox &Bounds)

void	Add (const ItemIDType ID, const FCellLocation &Location)

void	Remove (const ItemIDType ID, const FBox &OldBounds)

void	Remove (const ItemIDType ID, const FCellLocation &OldLocation)

FCellLocation	Move (const ItemIDType ID, const FBox &OldBounds, const FBox &NewBounds)

FCellLocation	Move (const ItemIDType ID, const FCellLocation &OldLocation, const FBox &NewBounds)

template<typename OutT >
void	QuerySmall (const FBox &Bounds, OutT &OutResults) const

template<typename OutT >
void	Query (const FBox &Bounds, OutT &OutResults) const

FCellRect	CalcQueryBounds (const FBox &Bounds, const int32 Level) const

FCellRect	IntersectRect (const FCellRect &Left, const FCellRect &Right) const

FCellLocation	CalcCellLocation (const FBox &Bounds) const

FBox	CalcCellBounds (const FCellLocation &CellLocation) const

FCell &	FindOrAddCell (const int X, const int Y, const int Level)

FCell *	FindCellMutable (const int X, const int Y, const int Level)

const FCell *	FindCell (const int X, const int Y, const int Level) const

float	GetCellSize (const int32 Level) const

float	GetInvCellSize (const int32 Level) const

int32	GetLevelItemCount (const int32 Level) const

const TSet< FCell > &	GetCells () const

const TSparseArray< FItem > &	GetItems () const

int32	GetFirstSpillListItem () const

Static Public Member Functions
static int32	LevelDown (int32 X)

Static Public Attributes
static const int32	NumLevels = InNumLevels

static const int32	LevelRatio = InLevelRatio

Static Protected Member Functions
static constexpr int32	ClampInt32 (const int64 Value)

Protected Attributes
TStaticArray< float, NumLevels >	CellSize

TStaticArray< float, NumLevels >	InvCellSize

TStaticArray< int32, NumLevels >	LevelItemCount

TSet< FCell >	Cells

TSparseArray< FItem >	Items

int32	SpillList = INDEX_NONE

Detailed Description

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>
class THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >

Hierarchical Hash Grid in 2D.

Items are added to the "infinite" grid at specific level based on their size. The grid size, and size ratio between levels are defined as the template parameter. This allows some computation to be optimized based on the values.

Items that cannot be fitted in the grid are added to a spill list, which contents are included in all queries. Each item is added to just one grid cell and thus can overlap some neighbour cells up to half cell size at that grid level. This is compensated during the query by expanding the query box.

Potential optimizations:

(X, Y, Level) could probably be int16.
Level ratio could be a shift so LevelDown() could become just shift.
FloorToInt ends up calling floorf, which will be a function call. int FloorToInt(float a) { return (int)a + ((int)a > a ? -1 : 0); } auto vectorizes nicely on clang, but not on VC.
Add helper function to allow to tweak the cell size to reset the grid when spill list gets too large

Member Typedef Documentation

◆ ItemIDType

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

typedef InItemIDType THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::ItemIDType

Constructor & Destructor Documentation

◆ THierarchicalHashGrid2D()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::THierarchicalHashGrid2D ( const float InCellSize = 500.f )

inline

Constructor, initializes the grid for specific cell size.

Parameters

InCellSize - new finest level cell size of the grid

Member Function Documentation

◆ Add() [1/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellLocation THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Add	(	const ItemIDType	ID,
		const FBox &	Bounds
	)

inline

Adds item to the grid.

Parameters

ID	- External ID used to identify the item.
Bounds	- Bounding box of the item.

Returns: Cell location of the item, can be used later to remove the item.

◆ Add() [2/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Add	(	const ItemIDType	ID,
		const FCellLocation &	Location
	)

inline

Adds item to the grid.

Parameters

ID	- External ID used to identify the item.
Location	- Cell location where the item should be added.

Returns: Cell location of the item, can be used later to remove the item.

◆ CalcCellBounds()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FBox THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::CalcCellBounds ( const FCellLocation & CellLocation ) const

inline

Finds the world box from a cell. @params CellLocation - Cell location.

Returns: Returns the bounds of the cell.

◆ CalcCellLocation()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellLocation THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::CalcCellLocation ( const FBox & Bounds ) const

inline

Finds grid level where the bounds fit inside a cell.

Parameters

Bounds - Bounding box of the item.

Returns: Returns cell location of the item, or location at Level == INDEX_NONE if the item cannot fit in the grid.

◆ CalcQueryBounds()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellRect THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::CalcQueryBounds	(	const FBox &	Bounds,
		const int32	Level
	)		const

inline

Calculates cell based query rectangle. The bounds are expanded by half grid cell size because the items are stored for only one cell based on their center and side. For that reason the items can overlap the neighbor cells by half the cell size.

Parameters

Bounds	- Query bounding box to quantize.
Level	- Which level of the tree the to calculate the bounds for

Returns: Quantized rectangle representing the cell bounds at specific level of the tree, coordinates inclusive.

◆ ClampInt32()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

static constexpr int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::ClampInt32 ( const int64 Value )

inlinestaticconstexprprotected

Returns: given int64 clamped in int32 range.

◆ FindCell()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

const FCell * THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::FindCell	(	const int	X,
		const int	Y,
		const int	Level
	)		const

inline

Returns a cell for specific location and level.

Parameters

X	- Cell X coordinate.
Y	- Cell Y coordinate.
Level	- Grid Level.

Returns: Pointer to cell at specified location, or return nullptr if the cell does not exist.

◆ FindCellMutable()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCell * THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::FindCellMutable	(	const int	X,
		const int	Y,
		const int	Level
	)

inline

Returns a cell for specific location and level.

Parameters

X	- Cell X coordinate.
Y	- Cell Y coordinate.
Level	- Grid Level.

Returns: Pointer to cell at specified location, or return nullptr if the cell does not exist.

◆ FindOrAddCell()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCell & THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::FindOrAddCell	(	const int	X,
		const int	Y,
		const int	Level
	)

inline

Returns a cell for specific location and level, creates new cell if it does not exist.

Parameters

X	- Cell X coordinate.
Y	- Cell Y coordinate.
Level	- Grid Level.

Returns: Reference to cell at specified location.

◆ GetCells()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

const TSet< FCell > & THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetCells ( ) const

inline

Returns: Set containing all the cells.

◆ GetCellSize()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

float THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetCellSize ( const int32 Level ) const

inline

Returns: Cell size at specific grid level.

◆ GetFirstSpillListItem()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetFirstSpillListItem ( ) const

inline

Returns: Index in items of the first item on the spill list.

◆ GetInvCellSize()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

float THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetInvCellSize ( const int32 Level ) const

inline

Returns: 1/cellSize at specific grid level.

◆ GetItems()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

const TSparseArray< FItem > & THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetItems ( ) const

inline

Returns: Sparse array containing all the items.

◆ GetLevelItemCount()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::GetLevelItemCount ( const int32 Level ) const

inline

Returns: Array containing all the items.

◆ Initialize()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Initialize ( const float InCellSize )

inline

Resets and initializes the grid for specific cell size.

Parameters

InCellSize - new finest level cell size of the grid

◆ IntersectRect()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellRect THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::IntersectRect	(	const FCellRect &	Left,
		const FCellRect &	Right
	)		const

inline

Returns intersection of the two cell bounding rectangles.

Parameters

Left	- left hand side rectangle
Right	- right hand side rectangle

Returns: Intersecting are between left and right.

◆ LevelDown()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

static int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::LevelDown ( int32 X )

inlinestatic

Levels down a coordinate using floor rounding.

Parameters

X	- Coordinate to level down

Returns: Coordinate at coarser level.

◆ Move() [1/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellLocation THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Move	(	const ItemIDType	ID,
		const FBox &	OldBounds,
		const FBox &	NewBounds
	)

inline

Moves item based on previous bounding box and new bounding box.

Parameters

ID	- External ID used to identify the item.
OldBounds	- The same bounding box the item was previously added or moved with.
NewBounds	- New bounds of the item

Returns: The cell location where the item was added to.

◆ Move() [2/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

FCellLocation THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Move	(	const ItemIDType	ID,
		const FCellLocation &	OldLocation,
		const FBox &	NewBounds
	)

inline

Moves item based on previous cell location and new bounding box.

Parameters

ID	- External ID used to identify the item.
OldLocation	- The same cell location the item was previously added or moved with.
NewBounds	- New bounds of the item

Returns: The cell location where the item was added to.

◆ Query()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

template<typename OutT >

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Query	(	const FBox &	Bounds,
		OutT &	OutResults
	)		const

inline

Returns items that potentially touch the bounds. Operates on grid level, can have false positives.

Parameters

Bounds	- Query bounding box.
OutResults	- Result of the query, IDs of potentially overlapping items.

◆ QuerySmall()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

template<typename OutT >

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::QuerySmall	(	const FBox &	Bounds,
		OutT &	OutResults
	)		const

inline

Returns items that potentially touch the bounds. Operates on grid level, can have false positives. This can be faster than Query() for small query box sizes (i.e. max dimension CellSize*4) due to simpler logic.

Parameters

Bounds	- Query bounding box.
OutResults	- Result of the query, IDs of potentially overlapping items.

◆ Remove() [1/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Remove	(	const ItemIDType	ID,
		const FBox &	OldBounds
	)

inline

Removes item based on the bounding box it was added with.

Parameters

ID	- External ID used to identify the item.
OldBounds	- The same bounding box the item was previously added or moved with.

◆ Remove() [2/2]

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Remove	(	const ItemIDType	ID,
		const FCellLocation &	OldLocation
	)

inline

Removes item based on the cell location it was added with.

Parameters

ID	- External ID used to identify the item.
OldLocation	- The same cell location the item was previously added or moved with.

◆ Reset()

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

void THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Reset ( )

inline

Reset the grid to empty.

Member Data Documentation

◆ Cells

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

TSet<FCell> THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Cells

protected

Number items per level, can be used to skip certain levels.

◆ CellSize

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

TStaticArray<float, NumLevels> THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::CellSize

protected

◆ InvCellSize

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

TStaticArray<float, NumLevels> THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::InvCellSize

protected

Lowest level cell size

◆ Items

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

TSparseArray<FItem> THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::Items

protected

TSet uses hash buckets to locate items.

◆ LevelItemCount

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

TStaticArray<int32, NumLevels> THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::LevelItemCount

protected

1 / CellSize

◆ LevelRatio

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

const int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::LevelRatio = InLevelRatio

static

Number of grid levels in the grid.

◆ NumLevels

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

const int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::NumLevels = InNumLevels

static

◆ SpillList

template<int32 InNumLevels = 3, int32 InLevelRatio = 4, typename InItemIDType = uint32>

int32 THierarchicalHashGrid2D< InNumLevels, InLevelRatio, InItemIDType >::SpillList = INDEX_NONE

protected

TSparseArray uses freelist to recycled used items.

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

Engine/Source/Runtime/AIModule/Public/HierarchicalHashGrid2D.h

Classes

Public Types

Public Member Functions

Static Public Member Functions

Static Public Attributes

Static Protected Member Functions

Protected Attributes

Detailed Description

Member Typedef Documentation

◆ ItemIDType

Constructor & Destructor Documentation

◆ THierarchicalHashGrid2D()

Member Function Documentation

◆ Add() [1/2]

◆ Add() [2/2]

◆ CalcCellBounds()

◆ CalcCellLocation()

◆ CalcQueryBounds()

◆ ClampInt32()

◆ FindCell()

◆ FindCellMutable()

◆ FindOrAddCell()

◆ GetCells()

◆ GetCellSize()

◆ GetFirstSpillListItem()

◆ GetInvCellSize()

◆ GetItems()

◆ GetLevelItemCount()

◆ Initialize()

◆ IntersectRect()

◆ LevelDown()

◆ Move() [1/2]

◆ Move() [2/2]

◆ Query()

◆ QuerySmall()

◆ Remove() [1/2]

◆ Remove() [2/2]

◆ Reset()

Member Data Documentation

◆ Cells

◆ CellSize

◆ InvCellSize

◆ Items

◆ LevelItemCount

◆ LevelRatio

◆ NumLevels

◆ SpillList