spieleprogrammierer.de - Forum und Wiki zur Spieleprogrammierung und Spieleentwicklung

C-/C++-Quelltext

/********************************************************************
    created:    2011/06/29
    created:    29:6:2011   20:07
    file base:  RDC
    file ext:   h
    author:     Marcus Finzel
    
    purpose:    recursive dimensional clustering for fast collisions detection
*********************************************************************/
#pragma once

#define MAX_PAIRS       2000
#define MAX_BRACKETS    210000
// a pair of Objects
class CPairs
{

public:
    CPairs();
    CPairs(CUnknownObject* pObjA, CUnknownObject* pObjB);
    void Set(CUnknownObject* pObjA, CUnknownObject* pObjB);
    CUnknownObject* m_pObjA;
    CUnknownObject* m_pObjB;
};



class CBracket
{
public:

    int KindOfBracket;
    int Value;
    CUnknownObject* pObj;

    
private:
};

int _cdecl CompareFunction(const void* el1, const void* el2);


class CRDC
{
public:
    CRDC();
    ~CRDC();
    // run the RDC function to search collision pairs
    // pPairs hold the final pairs
    // pGroup is the current group of objects
    // pSubGroup hold the final groups
    // axis1 is the axis to analyze in this function (can be X_AXIS, Y_AXIS, INVALID_AXIS)
    // axis2 will be analyzed in recursive calls
    bool run(CPairs * pPairs, CGrowableArray<CUnknownObject*>* pGroup, int Axis1, int Axis2,bool bBruteForce);
    
    GET_SET_ACCESSOR(unsigned int, nCalls);

    GET_SET_ACCESSOR(int, nSubDiv);

    GET_SET_ACCESSOR(int, nCollisions);
private:

    // find and add sorted open/close boundaries
    int FindOpenCloseBoundaries(int Axis, CGrowableArray<CUnknownObject*>* pGroup, CBracket* pBoundaries);

    void CheckIntersectionBF(CGrowableArray<CUnknownObject*>* pSubGroup);

    CPairs                          m_Pairs[MAX_PAIRS];

    int                             m_nCurrentPairs;

    unsigned int                    m_nCount;       // counter for brackets

    int                             m_nNewAxis1;
    int                             m_nNewAxis2;

    unsigned int                    m_nCalls;

    CBracket                        m_BracketList[MAX_BRACKETS];

    int                             m_nCollisions;
    int                             m_nRunCall;
    int                             m_nSubDiv;

};

C-/C++-Quelltext

/********************************************************************
    created:    2011/06/29
    created:    29:6:2011   20:07
    file base:  RDC
    file ext:   cpp
    author:     Marcus Finzel
    
    purpose:    recursive dimensional clustering for fast collisions detection
*********************************************************************/
#include "includes.h"

int _cdecl CompareFunction(const void* el1, const void* el2)
{
    if(((CBracket*)el1)->Value < ((CBracket*)el2)->Value)
        return -1;
    else if(((CBracket*)el1)->Value > ((CBracket*)el2)->Value)
        return +1;

    return 0;
}

CPairs::CPairs()
{
    m_pObjA = NULL;
    m_pObjB = NULL;
}

CPairs::CPairs(CUnknownObject* pObjA, CUnknownObject* pObjB)
{
    Set(pObjA,pObjB);
}

void CPairs::Set(CUnknownObject* pObjA, CUnknownObject* pObjB)
{
    m_pObjA = pObjA;
    m_pObjB = pObjB;
}

CRDC::CRDC()
{
    m_nCurrentPairs     = 0;
    m_nCurrentPairs     = 0;
    m_nCount            = 0;
    m_nNewAxis1         = 0;
    m_nNewAxis2         = 0;
    m_nCalls            = 0;
    m_nRunCall          = 0;
    m_nCollisions       = 0;

}

CRDC::~CRDC()
{

}

bool CRDC::run(CPairs * pPairs, CGrowableArray<CUnknownObject*>* pGroup, int Axis1, int Axis2,bool bBruteForce)
{
    if(pGroup->GetSize()*2 >= MAX_BRACKETS)
        return false;

    // is size of group less then 15, brute force is faster
    // if INVALID_AXIS the function is ready
    if((pGroup->GetSize() < 10) || (Axis1 == INVALID_AXIS) || (bBruteForce))
    {
        CheckIntersectionBF(pGroup);
    }
    else
    {
        
        int nBracketCounter;

        nBracketCounter = FindOpenCloseBoundaries(Axis1, pGroup, m_BracketList);

        if(nBracketCounter < 0) 
            return false;


        // sort brackets
        qsort(m_BracketList,nBracketCounter,sizeof(CBracket),CompareFunction);

        
        m_nCount    = 0;        // counter for brackets
        m_nNewAxis1 = Axis2;
        m_nNewAxis2 = INVALID_AXIS;

        CGrowableArray<CUnknownObject*>* pSubGroup = new CGrowableArray<CUnknownObject*>;

        // subdivide the group if possible and call recursively
        for(int i=0; i < nBracketCounter;i++)
        {
            CBracket* pBracket = &m_BracketList[i];

            m_nCalls++;

            if(pBracket->KindOfBracket == OPEN)
            {
                m_nCount++;
                
                pSubGroup->Add(pBracket->pObj);
            }
            else
            {
                m_nCount--;
                if(m_nCount == 0)
                {
                    // found end of a cluster group, take subgroup and call recursively
                    // get last object for check (-1, because array begins on 0
                    CBracket* pLastBracket = &m_BracketList[nBracketCounter-1];

                    if(pBracket->pObj != pLastBracket->pObj )
                    {
                        // reconsider all other axis
                        if(Axis1 == X_AXIS)
                        {
                            m_nNewAxis1 = Y_AXIS;

                        }
                        else if (Axis1 == Y_AXIS)
                            m_nNewAxis1 = X_AXIS;
                        
                    }
                
                    // next call
                    run(pPairs, pSubGroup, m_nNewAxis1, m_nNewAxis2,bBruteForce);
                    
                    // clear subGroup
                    pSubGroup->RemoveAll();
                }   
            }
            
        }

        SAFE_DELETE(pSubGroup);

    }
    
    
    m_nCurrentPairs = 0;

    return true;

}

int CRDC::FindOpenCloseBoundaries(int Axis, CGrowableArray<CUnknownObject*>* pGroup, CBracket* pBoundaries)
{
    if(Axis == INVALID_AXIS)
        return -1;


    CUnknownObject* pTempObj        = NULL;
    CBracket*       pTempBracket    = NULL;
    CRect2D*        pBoundingRect   = NULL;
    int             nBracketCounter = 0;
    

    for(int i=0; i< pGroup->GetSize();i++)
    {
        // get object pointer
        pTempObj = pGroup->GetAt(i);
        
        if(!pTempObj)
            continue;

        //////////////////////////////////////////////////////////////////////////
        // create new brackets
        //////////////////////////////////////////////////////////////////////////

        // get bounding rect pointer
        pBoundingRect = pTempObj->GetBoundary();

        // settings for OPEN bracket
        if(Axis == X_AXIS)
        {
            // OPEN Bracket
            pBoundaries[nBracketCounter].Value = (int)pBoundingRect->x0;
            // CLOSE Bracket
            pBoundaries[nBracketCounter+1].Value = (int)pBoundingRect->x1;
        }
        else if(Axis == Y_AXIS)
        {
            // OPEN Bracket
            pBoundaries[nBracketCounter].Value = (int)pBoundingRect->y0;
            // CLOSE Bracket
            pBoundaries[nBracketCounter+1].Value = (int)pBoundingRect->y1;
        }
        // OPEN Bracket
        pBoundaries[nBracketCounter].KindOfBracket = OPEN;
        pBoundaries[nBracketCounter].pObj = pTempObj;
        nBracketCounter++;
        // CLOSE Bracket
        pBoundaries[nBracketCounter].KindOfBracket = CLOSE;
        pBoundaries[nBracketCounter].pObj = pTempObj;

        nBracketCounter++;

        m_nCalls++;
    
    }

    return nBracketCounter;
}

void CRDC::CheckIntersectionBF(CGrowableArray<CUnknownObject*>* pSubGroup)
{
    CRect2D *rc1, *rc2, rcResult;
    int nSize = pSubGroup->GetSize();
    CUnknownObject* pSenderObj;
    CUnknownObject* pReceiverObj;

    if(pSubGroup)
    {
        // loop through array
        for(int a=0; a< nSize; a++)
        {
            pSenderObj = pSubGroup->GetAt(a);

        //  if (pSenderObj->GetbCollide())
            //  continue;
        

            // loop through array
            for(int i=0; i< nSize; i++)
            {
                pReceiverObj = pSubGroup->GetAt(i);

                m_nCalls++;
                // skip same object
                if((!pReceiverObj)||(pReceiverObj == pSenderObj))
                    continue;

                //TODO: 06.12.2011
            //  if(pReceiverObj->GetKernel()->GetbAlive())
                {
                    if(pReceiverObj->GetbCollide())
                        continue;
                }
                

                

                rc1 = pSenderObj->GetBoundary();
                rc2 = pReceiverObj->GetBoundary();


                if(GetLength(pReceiverObj->GetvecPosition()-pSenderObj->GetvecPosition()) < ballNS::BALL_SIZE)
                //if(M3D::Intersect(rcResult, *rc1, *rc2))
                {

                    pSenderObj->SetbCollide(true);
                    pReceiverObj->SetbCollide(true);
                    pSenderObj->SetpKollPartner(pReceiverObj);
                    pReceiverObj->SetpKollPartner(pSenderObj);
                    //GetGameApp()->GetObjectManager()->SendMessage(pSenderObj, pReceiverObj, OM_COLLIDE);
                    //GetGameApp()->CallGrafikDevice()->DrawTextLine(0,300,300,0,M3DCOLOR(1,1,1,1),"Collide");
                    //m_Pairs->Set(pSenderObj,pReceiverObj);
                    m_nCurrentPairs++;
                    m_nCollisions++;
                    //GetGameApp()->CallGrafikDevice()->CallSpriteManager()->RenderQuad(M3DVector(rcResult.x0,rcResult.y0,0),16,16,m_pCol);

                //  if (m_nCurrentPairs>=MAX_PAIRS)
                    //  break;
                }
                else
                {
                    pReceiverObj->SetbCollide(false);
                    pSenderObj->SetbCollide(false);
                    pSenderObj->SetpKollPartner(NULL);
                    pReceiverObj->SetpKollPartner(NULL);
                }

            }// end second loop
        }//end first loop


    }// end if(subGroup)

}