Bare-bones QuadTree class.

QuadTree.hpp

// See this here: https://gist.github.com/Ruskiy69/5257421
#include "gists/QTreeNode.hpp"

class CQuadTree
{
public:
  // Provide the starting dimensions to the root node.
  // This will likely be something like Window::GetWidth()
  // and Window::GetHeight() in a game.
  CQuadTree(const uint16_t w, const uint16_t h);

  // Inserts an object into the tree. 
  // This will call RInsert() on the head. 
  // It returns TRUE if it found a node to put it in.
  // The only time it would return false is if the pBody's
  // location is outside of the root node (e.g. offscreen).
  bool Insert(CEntity* pBody);

  // This will remove the pBody from the tree.
  inline bool Remove(obj::CRigidBody* pBody)
  { return this->RRemove(pBody, &m_Root); }

  // This checks if a pBody collides with any object (other than itself)
  // in the tree. It returns the object it collided with (or NULL if none).
  inline CEntity* Collides(const CEntity* pBody) const
  { return this->RCollides(pBody, &m_Root); }

  // Updates the objects to see if they have moved.
  // This requires that the object have a private "needs_update" value
  // and contains the QTNode* it belongs to.
  // See here: https://github.com/Ruskiy69/IronClad/blob/master/Source/include/IronClad/Entity/RigidBody.hpp
  // For a real definition of the objects I use.
  void Update();

private:
  // Maximum number of objects in a node before splitting is necessary.
  static const uint8_t QT_MAX_OBJECTS = 32;
  
  // Maximum tree depth. If this is reached all subsequent object adds to
  // this node will override the QT_MAX_OBJECTS value.
  static const uint8_t QT_MAX_DEPTH   = 6;
  
  // Actual recursive implementation of the Insert() method.
  bool RInsert(CEntity* pBody, QTNode* pStart);
  
  // Actual recursive implementation of the Remove() method.
  bool RRemove(CEntity* pBody, QTNode* pStart);
  CEntity* RCollides(const CEntity* pBody,
                     const QTNode*  pStart) const;
                     
  // Splits a node into 4 child nodes.
  void Split(QTNode* pNode);

  // The first node, encompassing all of the others.
  QTNode m_Root;
  
  // All of the objects in this tree.
  std::vector<CEntity*> mp_allBodies;
};