CQuadTree::RInsert()

QuadTreeInsert.cpp

// The one used by the public, all it does is start 
// the recursive algorithm with the root.
bool CQuadTree::Insert(CEntity* pEnt)
{
  // If inserted, we want to add to the whole internal list of 
  // objects, which is used later in CQuadTree::Update().
  if(this->RInsert(pBody, &m_Root))
  {
    mp_allBodies.push_back(pBody);
    return true;
  }
  
  return false;
}

// The real work-horse.
bool CQuadTree::RInsert(CEntity* pEnt, QTNode* pStart)
{
  if(pStart == nullptr) return false;

  // Leaf node.
  if(pStart->pChildren == nullptr)
  {
    // The node is full?
    if(pStart->nodeObjects.size() >= QT_MAX_OBJECTS)
    {
      // Can't split further, add anyway.
      if(pStart->depth >= QT_MAX_DEPTH)
      {
        pStart->nodeObjects.push_back(pEnt);
        
        // Assign the node to the entity, for CQuadTree::Update() later.
        pEnt->pCurrentNode = pStart;
        return true;
      }
      
      // We can split, so split and then recurse on self,
      // since now it's not a leaf node.
      else
      {
        this->Split(pStart);
        return this->RInsert(pEnt, pStart);
      }
      
      // Assign the node to the entity, for CQuadTree::Update() later.
      pEnt->pCurrentNode = pStart;
      return true;
    }

    // Assign the node to the entity, 
    pEnt->pCurrentNode = pStart;
    pStart->nodeObjects.push_back(pEnt);
    pStart->is_full = (pStart->nodeObjects.size() > QT_MAX_OBJ);
    return true;
  }

  // Branch
  else
  {
    for(uint8_t i = 0; i < 4; ++i)
    {
      if(pEnt->DetectCollision(pStart->pChildren[i]->Rect))
      {
        return this->RInsert(pEnt, pStart->pChildren[i]);
      }
    }
  }

  // This shouldn't happen, unless called by Update().
  // If it does, though, we go up the tree to the root, 
  // to find a node that we can fit in.
  
  // Return false if we've reached the root node and
  // still can't insert.
  return (pStart->pParent == nullptr) ? false :
          this->RInsert(pEnt, pStart->pParent);
}