Gamedev Framework (gf)  0.6.0
A C++11 framework for 2D games
Public Types | Public Member Functions | List of all members
gf::SpaceTree Class Reference

Binary space random partionning tree. More...

#include <gf/SpaceTree.h>

Public Types

using Callback = std::function< bool(const SpaceTree &)>
 A callback function for traversing the tree. More...
 

Public Member Functions

 SpaceTree (const RectI &area)
 Constructor. More...
 
const RectIgetArea () const
 Get the area of the node. More...
 
int getLevel () const
 Get the level of the node in the tree. More...
 
void removeChildren ()
 Remove the children of the node. More...
 
bool splitOnce (Random &random, Vector2i minSize, float maxRatio=1.5f)
 Split the node once. More...
 
void splitRecursive (Random &random, int levelMax, Vector2i minSize, Vector2i maxSize, float maxRatio=1.5f)
 Split a node recursively. More...
 
bool isLeaf () const
 Check if a node is a leaf. More...
 
const SpaceTreegetLeftChild () const
 Get the left child. More...
 
const SpaceTreegetRightChild () const
 Get the right child. More...
 
const SpaceTreegetFather () const
 Get the father of the node. More...
 
bool contains (Vector2i position) const
 Check if the area of the node contains a position. More...
 
const SpaceTreefind (Vector2i position) const
 Find the deepest node containing a position. More...
 
bool traversePreOrder (Callback callback) const
 Traverse the nodes in pre-order. More...
 
bool traverseInOrder (Callback callback) const
 Traverse the nodes in in-order. More...
 
bool traversePostOrder (Callback callback) const
 Traverse the nodes in post-order. More...
 
bool traverseLevelOrder (Callback callback) const
 Traverse the nodes in level-order. More...
 
bool traverseInvertedLevelOrder (Callback callback) const
 Traverse the nodes in inverted level-order. More...
 

Detailed Description

Binary space random partionning tree.

This class implements a random binary space partitioning tree. More precisely, this class is a node in the tree.

Member Typedef Documentation

◆ Callback

using gf::SpaceTree::Callback = std::function<bool(const SpaceTree&)>

A callback function for traversing the tree.

The function returns a boolean indicating if the traversal can continue.

Constructor & Destructor Documentation

◆ SpaceTree()

gf::SpaceTree::SpaceTree ( const RectI area)

Constructor.

Parameters
areaThe area to split for this node

Member Function Documentation

◆ contains()

bool gf::SpaceTree::contains ( Vector2i  position) const

Check if the area of the node contains a position.

Parameters
positionThe position to check

◆ find()

const SpaceTree* gf::SpaceTree::find ( Vector2i  position) const

Find the deepest node containing a position.

Parameters
positionThe position to find
Returns
A node or nullptr if the position is outside the tree

◆ getArea()

const RectI& gf::SpaceTree::getArea ( ) const
inline

Get the area of the node.

Returns
The area of the node

◆ getFather()

const SpaceTree* gf::SpaceTree::getFather ( ) const
inline

Get the father of the node.

The root of the tree has no father.

Returns
The father of the node

◆ getLeftChild()

const SpaceTree* gf::SpaceTree::getLeftChild ( ) const
inline

Get the left child.

Returns
The left child if it exists or nullptr

◆ getLevel()

int gf::SpaceTree::getLevel ( ) const
inline

Get the level of the node in the tree.

The root of the tree is at level 0, its children at level 1, etc.

Returns
The level of the node

◆ getRightChild()

const SpaceTree* gf::SpaceTree::getRightChild ( ) const
inline

Get the right child.

Returns
The right child if it exists or nullptr

◆ isLeaf()

bool gf::SpaceTree::isLeaf ( ) const
inline

Check if a node is a leaf.

A leaf has no children.

Returns
True if the node is a leaf

◆ removeChildren()

void gf::SpaceTree::removeChildren ( )

Remove the children of the node.

◆ splitOnce()

bool gf::SpaceTree::splitOnce ( Random random,
Vector2i  minSize,
float  maxRatio = 1.5f 
)

Split the node once.

This function may create two children if the conditions are met.

Parameters
randomA random generator
minSizeThe minimum size under which a node cannot be split
maxRatioThe maximum ratio between the width and height
Returns
True if the node has actually been split

◆ splitRecursive()

void gf::SpaceTree::splitRecursive ( Random random,
int  levelMax,
Vector2i  minSize,
Vector2i  maxSize,
float  maxRatio = 1.5f 
)

Split a node recursively.

Parameters
randomA random generator
levelMaxThe maximum level of a node
minSizeThe minimum size under which a node cannot be split
maxSizeThe maximum size over which a node must be split
maxRatioThe maximum ratio between the width and height

◆ traverseInOrder()

bool gf::SpaceTree::traverseInOrder ( Callback  callback) const

Traverse the nodes in in-order.

Parameters
callbackA function to call on each node
See also
Tree traversal - Wikipedia

◆ traverseInvertedLevelOrder()

bool gf::SpaceTree::traverseInvertedLevelOrder ( Callback  callback) const

Traverse the nodes in inverted level-order.

Parameters
callbackA function to call on each node
See also
Tree traversal - Wikipedia

◆ traverseLevelOrder()

bool gf::SpaceTree::traverseLevelOrder ( Callback  callback) const

Traverse the nodes in level-order.

Level-order is also known as breadth first search

Parameters
callbackA function to call on each node
See also
Tree traversal - Wikipedia

◆ traversePostOrder()

bool gf::SpaceTree::traversePostOrder ( Callback  callback) const

Traverse the nodes in post-order.

Parameters
callbackA function to call on each node
See also
Tree traversal - Wikipedia

◆ traversePreOrder()

bool gf::SpaceTree::traversePreOrder ( Callback  callback) const

Traverse the nodes in pre-order.

Parameters
callbackA function to call on each node
See also
Tree traversal - Wikipedia