1. Epic GamesDeveloper
  3. THierarchicalHashGrid2D

THierarchicalHashGrid2D

Hierarchical Hash Grid in 2D.

API > API/Runtime > API/Runtime/AIModule

References

   
Module AIModule
Header /Engine/Source/Runtime/AIModule/Public/HierarchicalHashGrid2D.h
Include #include "HierarchicalHashGrid2D.h"

Syntax

template<int32 InNumLevels, int32 InLevelRatio, typename InItemIDType>  
class THierarchicalHashGrid2D

Remarks

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 largeLWC_TODO_AI Note we are using int32 here for X and Y which does mean that we could overflow the limit of an int for LWCoords unless fairly large grid cell sizes are used.As WORLD_MAX is currently in flux until we have a better idea of what we are going to be able to support its probably not worth investing time in this potential issue right now.

Variables

  Type Name Description
Protected variable TSet< FCell > Cells Number items per level, can be used to skip certain levels.
Protected variable TStaticArray< float, NumLevels > CellSize  
Protected variable TStaticArray< float, NumLevels > InvCellSize Lowest level cell size
Protected variable TSparseArray< FItem > Items TSet uses hash buckets to locate items.
Protected variable TStaticArray< int32, NumLevels > LevelItemCount 1 / CellSize
Protected variable int32 SpillList TSparseArray uses freelist to recycled used items.

Constructors

  Type Name Description
Public function  

THierarchicalHashGrid2D ( const float InCellSize
)

 Constructor, initializes the grid for specific cell size.

Functions

  Type Name Description
Public function void

Add ( const ItemIDType ID,
const FCellLocation& Location
)

 Adds item to the grid.
Public function FCellLocation

Add ( const ItemIDType ID,
const FBox& Bounds
)

 Adds item to the grid.
Public function Const FBox

CalcCellBounds ( const FCellLocation& CellLocation
)

 Finds the world box from a cell. CellLocation - Cell location.
Public function Const FCellLocation

CalcCellLocation ( const FBox& Bounds
)

 Finds grid level where the bounds fit inside a cell.
Public function Const FCellRect

CalcQueryBounds ( const FBox& Bounds,
const int32 Level
)

 Calculates cell based query rectangle.
Public function Const const FCell *

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

 Returns a cell for specific location and level.
Public function FCell *

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

 Returns a cell for specific location and level.
Public function FCell &

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

 Returns a cell for specific location and level, creates new cell if it does not exist.
Public function Const const TSet< FCell > &  
Public function Const float

GetCellSize ( const int32 Level
)

  
Public function Const int32  
Public function Const float

GetInvCellSize ( const int32 Level
)

  
Public function Const const TSparseArray< FItem > &  
Public function Const int32

GetLevelItemCount ( const int32 Level
)

  
Public function void

Initialize ( const float InCellSize
)

 Resets and initializes the grid for specific cell size.
Public function Const FCellRect

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

 Returns intersection of the two cell bounding rectangles.
Public function Static int32

LevelDown ( int32 X
)

 Levels down a coordinate using floor rounding.
Public function FCellLocation

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

 Moves item based on previous bounding box and new bounding box.
Public function FCellLocation

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

 Moves item based on previous bounding box and new bounding box.
Public function Const void

Query ( const FBox& Bounds,
TArray< ItemIDType >& OutResults
)

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

QuerySmall ( const FBox& Bounds,
TArray< ItemIDType >& OutResults
)

 Returns items that potentially touch the bounds.
Public function void

Remove ( const ItemIDType ID,
const FBox& OldBounds
)

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

Remove ( const ItemIDType ID,
const FCellLocation& OldLocation
)

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

Reset ()

 Reset the grid to empty.

Classes

  Type Name Description
Public struct FCell Ratio in cells between consecutive levels.  
Public struct FCellLocation Specifies cell location within the grid at specific level.  
Public struct FCellRect Rectangle bounds, coordinates inclusive.  
Public struct FCellRectIterator Iterator state over a rectangle  
Public struct FItem Item stored in a grid cell.  

Typedefs

Name Description
ItemIDType  

Constants

Name Description
LevelRatio Number of grid levels in the grid.
NumLevels  

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page