Skip to main content
gamedev.net
🔒 Locked

QuadTree critique

Started by newera Jan 24, 2007 at 6:57 PM 0 replies 1.2k views
Original Post
newera
newera
Hello all, I am a novice of the language C++, with that said I have an implementation of a QuadTree working(so I think). Can some helpful soul help me with any syntactical optimizations or point out any flaws the following piece of code may have. The templates especially are giving me trouble, I would like to move some code outside of the header file if possible. Thanks in advanced! QuadTree.h: 

#pragma once

#include <vector>
#include <map>

#include "geom.h"

#pragma warning( disable : 4244)


template<class T>
bool SwapAndErase( std::vector< T > &list, T &object )
{
    std::vector< T >::iterator it = list.begin();
    for(; it != list.end(); ++it )
    {
        if ( (*it)->GetID() == object->GetID() )
        {
            list.erase( it );
            return true;
        }
    }
    return false;
    
    //for (size_t i=0;i < list.size(); ++i )
    //{
    //    if ( list == object )
    //    {
    //        list = list[ list.size()-1 ];
    //        list[list.size()-1 ] = object;
    //        list.pop_back();
    //        return;
    //    }
    //}
}

template<class T>
void AppendVector( std::vector< T > &list, std::vector< T > &appendMe )
{
    for ( size_t i = 0; i < appendMe.size(); ++i )
    {
        list.push_back( appendMe );
    }
}

template<class T>
void CloneVector( std::vector< T > &cloneMe, std::vector< T > &list )
{
    list.clear();
    for ( size_t i = 0; i < cloneMe.size(); ++i )
    {
        list.push_back( cloneMe );
    }
}



/**
================================================================================
QuadTree Node
================================================================================
*/
template <class T>
class QuadTreeNode
{
public:
    QuadTreeNode(Rect r)
    {
        for ( int i = 0; i < 4;  ++i )
        {
            m_children = NULL;
        }
        m_bounds.Set( r.x, r.y, r.width, r.height);
    }

    /** Put an item in the QuadTree */
    virtual bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            // how many leafs does this fit into
            int counter = 0;
            int nodeToPlaceObjectIn = -1;
            for ( int i=0;i<4;i++)
            {
                if ( m_children->GetBounds().Intersects( objectBounds ) ) {
                    nodeToPlaceObjectIn = i;
                    ++counter;
                }
    
                // if we are fitting in multiple leafs,
                // store in the parent node
                if ( counter >= 2 )
                {
                    m_objects.push_back( object );
                    return true;
                }

            }
            if ( nodeToPlaceObjectIn != -1 && counter < 2 )
            {
                m_children[ nodeToPlaceObjectIn ]->Put( object );
            }
            return true;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    virtual bool Pop( T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            // how many leafs does this fit into
            int counter = 0;
            int nodeToRemoveObjectIn = -1;
            for ( int i=0;i<4;i++)
            {
                if ( m_children->GetBounds().Intersects( objectBounds ) ) {
                    nodeToRemoveObjectIn = i;
                    ++counter;
                }
    
                // if it fits in multiple leafs,
                // this means it SHOULD be stored in
                // this node.
                if ( counter >= 2 )
                {
                    return SwapAndErase<T>( m_objects, object );
                }

            }
            // push work to a leaf node
            if ( nodeToRemoveObjectIn != -1 && counter < 2 )
            {
                m_children[ nodeToRemoveObjectIn ]->Pop( object );
            }
            return true;
        }
        return false;
    }

    /** Get all the objects contained in this region */
    virtual void GetObjects( const Rect &region, std::vector< T > &list )
    {
        if ( m_bounds.Intersects( region ) )
        {
            bool NW = m_children[0]->GetBounds().Intersects( region );
            bool NE = m_children[1]->GetBounds().Intersects( region );
            bool SW = m_children[2]->GetBounds().Intersects( region );
            bool SE = m_children[3]->GetBounds().Intersects( region );

            
            // if this region fits in all quadrants
            // we have the highest node 
            if ( NW && NE && SW && SE )
                return AppendVector( list, m_objects );
            else
            {   
                AppendVector( list, m_objects );
                if ( NW )
                    m_children[0]->GetObjects( region, list ) ;
                if ( NE )
                    m_children[1]->GetObjects( region, list ) ;
                if ( SW )
                    m_children[2]->GetObjects( region, list ) ;
                if ( SE )
                    m_children[3]->GetObjects( region, list ) ;
            }
        }
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_bounds.Intersects( region ); };


    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_bounds; };

    /** Number of objects */
    virtual int Size() {
        int j = m_objects.size();
        for ( int i=0;i<4;i++)
        {
            j += m_children->Size();
        }
        return j;
    }

    static enum {
        NORTHWEST = 0,
        NORTHEAST = 1,
        SOUTHWEST = 2,
        SOUTHEAST = 3
    };
    
    // children
    QuadTreeNode*    m_children[4];
        // this nodes bounds 
    Rect    m_bounds;

protected:
    // list of objects in this node
    typedef std::vector< T > type_List;
    type_List m_objects;



public:
    virtual ~QuadTreeNode(void)
    {
        for ( int i = 0; i < 4;  ++i )
        {
            if ( m_children ) delete m_children;
        }   
    };
};



/**
================================================================================
LeafNode
================================================================================
*/
template <class T>
class QuadTreeLeaf : public QuadTreeNode<T>
{
public:
    QuadTreeLeaf(Rect r) : QuadTreeNode(r) {};

    /** Put an item in the QuadTree */
    bool Put(  T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            m_objects.push_back( object );
            return true;
        }
        return false;
    }

    /** Pop an item in the QuadTree */
    bool Pop( T& object )
    {
        Rect &objectBounds = object->GetBounds();
        if ( m_bounds.Intersects( objectBounds ) )
        {
            return SwapAndErase( m_objects, object );
        }
        return false;
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region, std::vector< T > &list )
    {
        return AppendVector( list, m_objects );
    }

    int Size() { return m_objects.size(); };
public:
    virtual ~QuadTreeLeaf(void) {};
};






/**
================================================================================
Data Structure for holding
world data
================================================================================
*/
template <class T>
class QuadTree
{
public:
    QuadTree(float minw, float minh, float maxw, float maxh):  m_maxWidth(maxw), 
                                                                                m_maxHeight(maxw),
                                                                                m_minWidth(minw),
                                                                                m_minHeight(minh)
    {

        m_root = new QuadTreeNode<T>( Rect( 0, 0, m_maxWidth, m_maxHeight ) );
        BuildTree( m_root );

    }
    QuadTree();

    /** Put an item in the QuadTree */
    bool Put( T& object )
    {
        return m_root->Put( object );
    }
    /** Pop off an object */
    bool Pop( T& object )
    {
        return m_root->Pop( object );
    }

    /** Get all the objects contained in this region */
    void GetObjects( const Rect &region,std::vector< T > &list )
    {
        return m_root->GetObjects( region, list );
    }

    /** Has this object in this region */
    bool    IsInBounds( const Rect &region ) { return m_root->IsInBounds(region); };

    /** Get this nodes bounds */
    Rect    &GetBounds() { return m_root->m_bounds; };

    /** Get the number of elements in the tree */
    int Size() { return m_root->Size(); };

    // TEMP
    void Draw(IRender *r) {
        m_root->Draw(r);
    }
private:
    /** BuildTree */
    template<class T>
    void BuildTree( QuadTreeNode<T>* root ) 
    {
        float h_width  = root->m_bounds.width / 2;
        float h_height = root->m_bounds.height / 2;

        
        if (  h_width < m_minWidth*2 && h_height < m_minHeight*2 ) 
        // build the leafs
        {
            root->m_children[ root->NORTHWEST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x, root->GetBounds().y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x, root->GetBounds().y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeLeaf<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y+h_height, h_width, h_height ) );
        }
        else    // build the branches
        {
            root->m_children[ root->NORTHWEST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x, root->GetBounds().y, h_width, h_height )                  );
            root->m_children[ root->NORTHEAST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y,h_width, h_height )           );
            root->m_children[ root->SOUTHWEST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x, root->GetBounds().y+h_height,h_width, h_height)           );
            root->m_children[ root->SOUTHEAST ] = new QuadTreeNode<T>( Rect(root->GetBounds().x+h_width, root->GetBounds().y+h_height, h_width, h_height ) );

            BuildTree ( root->m_children[ root->NORTHWEST ] );
            BuildTree ( root->m_children[ root->NORTHEAST ] );
            BuildTree ( root->m_children[ root->SOUTHWEST ] );
            BuildTree ( root->m_children[ root->SOUTHEAST ] );
        }
    }

    //  max size
    float   m_maxWidth,
            m_maxHeight;

    //  min size
    float   m_minWidth,
            m_minHeight;

    // list of objects in this node
    typedef std::vector< T > type_List;
    type_List objects;

    // root
    QuadTreeNode<T>*   m_root;

public:
    virtual ~QuadTree(void) { delete m_root; };
};
ldeej
ldeej
there is a better way to do AppendVector and CloneVector:

std::copy(appendMe.begin(), appendMe.end(), std::back_inserter(appendMe));

I would set the number 4 on the quadtree on a constant for the whole class (static const int child_count)


Rect &GetBounds() { return m_bounds; };

should probably be:

const Rect &GetBounds() const { return m_bounds; };

I would rename Put and Pop to Insert and Erase

Architecture wise, do you really want to have both a QuadTreeNode and a leaf node? It seems like you pay a very high price for that in terms of ease of understanding and potentially performance.

Hope this helps...

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.

Sign in to reply to this topic.