1. Epic GamesDeveloper
  3. THierarchicalHashGrid2D

THierarchicalHashGrid2D

Hierarchical Hash Grid in 2D.

API > API/Runtime > API/Runtime/AIModule

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 LWC_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.
   
Name THierarchicalHashGrid2D
Type class
Header File /Engine/Source/Runtime/AIModule/Public/HierarchicalHashGrid2D.h
Include Path #include "HierarchicalHashGrid2D.h"

Syntax

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

Constructors

Name Remarks Include Path Unreal Specifiers

THierarchicalHashGrid2D ( const float InCellSize
)

 Constructor, initializes the grid for specific cell size. HierarchicalHashGrid2D.h  

Structs

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

Typedefs

Name Type Remarks Include Path
ItemIDType InItemIDType   HierarchicalHashGrid2D.h

Constants

Name Type Remarks Include Path
LevelRatio const int32 Number of grid levels in the grid. HierarchicalHashGrid2D.h
NumLevels const int32   HierarchicalHashGrid2D.h

Functions

Public

Name Remarks Include Path Unreal Specifiers

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

 Adds item to the grid. HierarchicalHashGrid2D.h  

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

 Adds item to the grid. HierarchicalHashGrid2D.h  

FBox CalcCellBounds ( const FCellLocation& CellLocation
) const

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

FCellLocation CalcCellLocation ( const FBox& Bounds
) const

 Finds grid level where the bounds fit inside a cell. HierarchicalHashGrid2D.h  

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

 Calculates cell based query rectangle. HierarchicalHashGrid2D.h  

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

 Returns a cell for specific location and level. HierarchicalHashGrid2D.h  

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

 Returns a cell for specific location and level. HierarchicalHashGrid2D.h  

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. HierarchicalHashGrid2D.h  

const TSet< FCell > & GetCells()

   HierarchicalHashGrid2D.h  

float GetCellSize ( const int32 Level
) const

   HierarchicalHashGrid2D.h  

int32 GetFirstSpillListItem()

   HierarchicalHashGrid2D.h  

float GetInvCellSize ( const int32 Level
) const

   HierarchicalHashGrid2D.h  

const TSparseArray< FItem > & GetItems()

   HierarchicalHashGrid2D.h  

int32 GetLevelItemCount ( const int32 Level
) const

   HierarchicalHashGrid2D.h  

void Initialize ( const float InCellSize
)

 Resets and initializes the grid for specific cell size. HierarchicalHashGrid2D.h  

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

 Returns intersection of the two cell bounding rectangles. HierarchicalHashGrid2D.h  

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

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

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

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

void Query ( const FBox& Bounds,
OutT& OutResults
) const

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

void QuerySmall ( const FBox& Bounds,
OutT& OutResults
) const

 Returns items that potentially touch the bounds. HierarchicalHashGrid2D.h  

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

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

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

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

void Reset()

 Reset the grid to empty. HierarchicalHashGrid2D.h  

Static

Name Remarks Include Path Unreal Specifiers

static int32 ClampInt32 ( const int64 Value
)

   HierarchicalHashGrid2D.h  

static int32 LevelDown ( int32 X
)

 Levels down a coordinate using floor rounding. HierarchicalHashGrid2D.h  

Ask questions and help your peers Developer Forums

Write your own tutorials or read those from others Learning Library

On this page