Jump to content
  • Advertisement
Sign in to follow this  
garyfletcher

Sanity check of my aabb sweep collision detection.

This topic is 4908 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

Hi all. I've been implementing vectors and collision detection based on the articles I found for An Axis-Aligned Bounding Box (AABB) sweep Test to implement the test and C++ Data Structures For Ridgid Body to implement the vectors. The articles describe vectors and collision tests for 3-D geomotry so I've had to amend the implementaion for my 2-D engine. Both are on the gamasutra website, so I'm afraid you'll need to login to access the articles....sorry. It seems to work, but I'm not too sure if it's the sweep that's working or the normal AABB collision test I do prior to the sweep test for collision between frames. I was hoping that someone might take a look and sanity check my implementation. I know it's pretty long and ardous so I completely understand if it's a little too much to ask. Many thanks in advance if you take on the task. AABB Sweep test implementation (2D):
bool SiSE::m_aabbSweepCollision(SiSEASprite* aSprite, SiSEASprite* bSprite)
{
    Vector2D extentX;
    Vector2D extentY;
    
    if (aSprite->Centre()->GetY() >= bSprite->Centre()->GetY())
    {
        extentY = *aSprite->MinYExtent() - *bSprite->MaxYExtent();
    }
    else
    {
        extentY = *aSprite->MaxYExtent() - *bSprite->MinYExtent();
    }
    
    if (aSprite->Centre()->GetX() >= bSprite->Centre()->GetX())
    {
        extentX = *aSprite->MinXExtent() - *bSprite->MaxXExtent();
    }
    else
    {
        extentX = *aSprite->MaxXExtent() - *bSprite->MinXExtent();
    }
    
    Vector2D tempVec = *aSprite->Centre() - *bSprite->Centre();
    
    if (((fabs(tempVec.GetX()) <= fabs(extentX.GetX())) &&
         (fabs(tempVec.GetY()) <= fabs(extentY.GetY()))))
        return true;
        
    // Check if an overlap has occured during frames
    
    Vector2D aDis = *aSprite->Pos() - *aSprite->OldPos();  // aSprite Displacement
    Vector2D bDis = *bSprite->Pos() - *bSprite->OldPos();  // bSprite Displacement
    
    // Sweep in aSprites frame of reference
    Vector2D a2DVec  = aDis - bDis;
    
    // Get relative velocity (in normalised times)
    Vector2D u0(0,0);
    Vector2D u1(1,1);
    
    if (aSprite->OldMaxXExtent()->GetX() < bSprite->OldMinXExtent()->GetX() && a2DVec.GetX() < 0)
    {
        u0.SetX((aSprite->OldMaxXExtent()->GetX() - bSprite->OldMinXExtent()->GetX())/a2DVec.GetX());
    }
    else if (bSprite->OldMaxXExtent()->GetX() < aSprite->OldMinXExtent()->GetX() && a2DVec.GetX() > 0)
    {
        u0.SetX((aSprite->OldMinXExtent()->GetX() - bSprite->OldMaxXExtent()->GetX())/a2DVec.GetX()); 
    }
    
    if (bSprite->OldMaxXExtent()->GetX() > aSprite->OldMinXExtent()->GetX() && a2DVec.GetX() < 0)
    {
        u1.SetX((aSprite->OldMinXExtent()->GetX() - bSprite->OldMaxXExtent()->GetX())/a2DVec.GetX());
    }
    else if (aSprite->OldMaxXExtent()->GetX() > bSprite->OldMinXExtent()->GetX() && a2DVec.GetX() > 0)
    {
        u1.SetX((aSprite->OldMaxXExtent()->GetX() - bSprite->OldMinXExtent()->GetX())/a2DVec.GetX()); 
    }
    
    if (aSprite->OldMaxYExtent()->GetY() < bSprite->OldMinYExtent()->GetY() && a2DVec.GetY() < 0)
    {
        u0.SetY((aSprite->OldMaxYExtent()->GetY() - bSprite->OldMinYExtent()->GetY())/a2DVec.GetY());
    }
    else if (bSprite->OldMaxYExtent()->GetY() < aSprite->OldMinYExtent()->GetY() && a2DVec.GetY() > 0)
    {
        u0.SetY((aSprite->OldMinYExtent()->GetY() - bSprite->OldMaxYExtent()->GetY())/a2DVec.GetY()); 
    }
    
    if (bSprite->OldMaxYExtent()->GetY() > aSprite->OldMinYExtent()->GetY() && a2DVec.GetY() < 0)
    {
        u1.SetY((aSprite->OldMinYExtent()->GetY() - bSprite->OldMaxYExtent()->GetY())/a2DVec.GetY());
    }
    else if (aSprite->OldMaxYExtent()->GetY() > bSprite->OldMinYExtent()->GetY() && a2DVec.GetY() > 0)
    {
        u1.SetY((aSprite->OldMaxYExtent()->GetY() - bSprite->OldMinYExtent()->GetY())/a2DVec.GetY()); 
    }
    
    SCALAR u_0;  // Normalise time of 1st collision
    SCALAR u_1;  // Normalise time of 2nd collision
    
    SCALAR u0X = u0.GetX();
    SCALAR u0Y = u0.GetY();
    SCALAR u1X = u1.GetX();
    SCALAR u1Y = u1.GetY();
    
    u_0 = (u0X <= u0Y)?u0Y:u0X;
    u_1 = (u1X >= u1Y)?u1Y:u1X;
    
    return (u_0 > u_1);

}


Vector Class:
#ifndef INCLUDE_VEC2D_H
#define INCLUDE_VEC2D_H

typedef float SCALAR;

class Vector2D
{
    public:
        Vector2D();
        Vector2D(const SCALAR& a, const SCALAR& b);
        ~Vector2D();
        SCALAR& operator[](const long i);
        const bool operator==(const Vector2D& v) const;
        const bool operator!=(const Vector2D& v) const;
        const Vector2D operator-(void) const;
        const Vector2D& operator=(const Vector2D& v);
        const Vector2D& operator+=(const Vector2D& v);
        const Vector2D& operator-=(const Vector2D& v);
        const Vector2D& operator*=(const SCALAR& s);
        const Vector2D& operator/=(const SCALAR& s);
        const Vector2D operator+(const Vector2D& v) const;
        const Vector2D operator-(const Vector2D& v) const;
        const Vector2D operator*(const SCALAR& s) const;
        friend inline const Vector2D operator* (const SCALAR& s, const Vector2D v){return v*s;}
        const Vector2D operator/(const SCALAR& s) const;
        const Vector2D perpen(void) const;
        const SCALAR dot(const Vector2D& v) const;
        const SCALAR length(void) const;
        const Vector2D unit(void) const;
        void normalise(void);
        const bool nearlyEquals(const Vector2D& v, const SCALAR e) const;
        void SetX(SCALAR xPos){x=xPos; calcMagnitude();}
        SCALAR GetX(void){return x;}
        void SetY(SCALAR yPos){y=yPos; calcMagnitude();}
        SCALAR GetY(void){return y;}
        void SetXY(SCALAR xPos, SCALAR yPos){x=xPos; y=yPos; calcMagnitude();}
        
        private:
            void calcMagnitude(void);
            SCALAR x;
            SCALAR y;
            double magnitude;
        
};

typedef Vector2D POINT;

#endif

#include "Vector2D.h"
#include <cmath>

Vector2D::Vector2D():x(0), y(0), magnitude(0.0)
{
}

Vector2D::Vector2D(const SCALAR& a, const SCALAR& b):x(a), y(b)
{
    calcMagnitude();
}

Vector2D::~Vector2D()
{
}

void Vector2D::calcMagnitude(void)
{
    magnitude = sqrt(fabs(x*x)+fabs(y*y));
}

SCALAR& Vector2D::operator[](const long i)
{
    return *((&x)+i);
}
        
const bool Vector2D::operator==(const Vector2D& v) const
{
    return (v.x==x && v.y==y);
}
        
const bool Vector2D::operator!=(const Vector2D& v) const
{
    return !(v==*this);
}

const Vector2D Vector2D::operator-(void) const
{
    return Vector2D(-x,-y);
}
 
const Vector2D& Vector2D::operator=(const Vector2D& v)
{
    x=v.x;
    y=v.y;
    
    return *this;
}

const Vector2D& Vector2D::operator+=(const Vector2D& v)
{
    x+=v.x;
    y+=v.y;
    
    return *this;
}

const Vector2D& Vector2D::operator-=(const Vector2D& v)
{
    x-=v.x;
    y-=v.y;
    
    return *this;
}

const Vector2D& Vector2D::operator*=(const SCALAR& s)
{
    x*=s;
    y*=s;
    
    return *this;
}

const Vector2D& Vector2D::operator/=(const SCALAR& s)
{
    const SCALAR r = 1/s;
    
    x*=r;
    y*=r;
    
    return *this;
}

const Vector2D Vector2D::operator+(const Vector2D& v) const
{
    return Vector2D(x+v.x,x+v.y);
}
        
const Vector2D Vector2D::operator-(const Vector2D& v) const
{
    return Vector2D(x-v.x,y-v.y);
}

const Vector2D Vector2D::operator*(const SCALAR& s) const
{
    return Vector2D(x*s, y*s);
}

const Vector2D Vector2D::operator/(const SCALAR& s) const
{
    SCALAR t=1/s;
    
    return Vector2D(t*x,t*y);
}

const Vector2D Vector2D::perpen(void) const
{
    return Vector2D(this->y, -(this->x));
}

const SCALAR Vector2D::dot(const Vector2D& v) const
{
    return x*v.x + y*v.y;
}

const SCALAR Vector2D::length(void) const
{
    return (SCALAR)sqrt((double)this->dot(*this));
}

const Vector2D Vector2D::unit(void) const
{
    return (*this)/length();
}

void Vector2D::normalise(void)
{
    (*this)/=length();
}

const bool Vector2D::nearlyEquals(const Vector2D& v, const SCALAR e) const
{
    return fabs(x-v.x)<e && fabs(y-v.y) < e;
}


Sprite (has pointers to vectors to represent coords)
#ifndef INCLUDE_CSPRITE_H
#define INCLUDE_CSPRITE_H

#include "SiSEASprite.h"
#include "SiSESpriteBase.h"
#include "Vector2D.h"

class SiSEASprite : public SiSESprite
{
    public:
        SiSEASprite(SiSESpriteBase* SBase, SDL_Surface *screen, float x = 0.0f, float y = 0.0f, float speed = 0.0f);  // Constructor
        virtual ~SiSEASprite();         // Destructor
        
        // Sprite initialiser
        bool Init(SiSESpriteBase *base, SDL_Surface *screen);
        
        // Drawing functoins
        virtual void draw(void);
        virtual void clearBG(void);
        virtual void updateBG(void);
        void DrawSpriteIMG(SDL_Surface *img, float x, float y);
        
        // Inline functions
        // Accessor functions
        Vector2D* Pos(void){return pos;}
        Vector2D* OldPos(void){return oldPos;}
        int GetHeight(void){return mSpriteBase->GetHeight();}
        int GetWidth(void){return mSpriteBase->GetWidth();}
        void SetFrame(int nr){mFrame = nr;}
        int GetFrame(void){return mFrame;}
        void SetSpeed(float nr){mSpeed = nr;}
        float GetSpeed(void){return mSpeed;}
        void SetScreen(SDL_Surface *aScreen){mScreen = aScreen;}
        SDL_Surface *GetScreen(void){return mScreen;}
        Vector2D* MinXExtent(void){return minXExtPos;}
        Vector2D* MaxXExtent(void){return maxXExtPos;}
        Vector2D* MinYExtent(void){return minYExtPos;}
        Vector2D* MaxYExtent(void){return maxYExtPos;}
        Vector2D* OldMinXExtent(void){return oldMinXExtPos;}
        Vector2D* OldMaxXExtent(void){return oldMaxXExtPos;}
        Vector2D* OldMinYExtent(void){return oldMinYExtPos;}
        Vector2D* OldMaxYExtent(void){return oldMaxYExtPos;}
        Vector2D* Centre(void){return centre;}
        
        // Animations control functions
        void ToggleAnim(void){mAnimating = !mAnimating;}
        void StartAnim(void){mAnimating = true;}
        void StopAnim(void){mAnimating = false;}
        void Rewind(void){mFrame = 0;}
        bool isAnimating(void){return mAnimating;}
        
        // COORD control functions
        void xAdd(float nr);
        void yAdd(float nr);
        void xSet(float nr);
        void ySet(float nr);
        void xySet(float x, float y);
        
    private:
        int mFrame;                     // Animation frame tracker
        Vector2D* pos;
        Vector2D* oldPos;
        Vector2D* minXExtPos;
        Vector2D* maxXExtPos;
        Vector2D* minYExtPos;
        Vector2D* maxYExtPos;
        Vector2D* oldMinXExtPos;
        Vector2D* oldMaxXExtPos;
        Vector2D* oldMinYExtPos;
        Vector2D* oldMaxYExtPos;
        Vector2D* centre;
        float xPos;                     // Current x-coord
        float yPos;                     // Current y-coord
        float xOld;                     // Last x-coord
        float yOld;                     // last y-coord
        float minXExtent;
        float maxXExtent;
        float minYExtent;
        float maxYExtent;
        float centreX;
        float centreY;
        bool mAnimating;                // Animating flag
        bool mDrawn;                    // Drawn flag
        float mSpeed;                   // Speed indicator (pause multiplier)
        long mLastUpdate;               // Time sprite was last animated
        SiSESpriteBase* mSpriteBase;    // Pointer to animations (sprite frames)
        SDL_Surface* mScreen;           // Pointer to the surface to animate on 
        
        void calcVectors(void);
        void calcCentre(void);
        void calcExtents(void);
        void calcXExtents(void);
        void calcYExtents(void);
};

#endif

#include "SiSEASprite.h"

SiSEASprite::SiSEASprite(SiSESpriteBase* SBase, SDL_Surface *screen, float x, float y, float speed)
{
    mFrame = 0;                 // Animation frame tracker
    xPos = x;                   // Current x-coord
    yPos = y;                   // Current y-coord
    xOld = 0;                   // Last x-coord
    yOld = 0;                   // last y-coord
    mAnimating = 0;             // Animating flag
    mDrawn = false;             // Drawn flag
    mSpeed = speed;               // Speed indicator (pause multiplier)
    mLastUpdate = 0L;           // Time sprite was last animated
    mSpriteBase = 0;            // Pointer to animations (sprite frames)
    
    mSpriteBase = SBase;
    
    if(mSpriteBase->isBuilt())
    {
        if (mSpriteBase->GetFramesNum() > 1)
        {
            mAnimating = true;
        }
    }

    mScreen = screen;
    
    calcCentre();
    calcExtents();
    
    pos = new Vector2D(x,y);
    oldPos = new Vector2D();
    minXExtPos = new Vector2D(minXExtent,centreY);
    maxXExtPos = new Vector2D(maxXExtent,centreY);
    minYExtPos = new Vector2D(centreX,minYExtent);
    maxYExtPos = new Vector2D(centreX,maxYExtent);
    oldMinXExtPos = minXExtPos;
    oldMaxXExtPos = maxXExtPos;
    oldMinYExtPos = minYExtPos;
    oldMaxYExtPos = maxYExtPos;
    centre = new Vector2D(centreX,centreY);
}
        
SiSEASprite::~SiSEASprite()
{
    mSpriteBase = 0;
    
    delete pos;
    pos = 0;
    
    delete oldPos;
    oldPos = 0;
    
    delete minXExtPos;
    minXExtPos = 0;
    
    delete minXExtPos;
    maxXExtPos = 0;
    
    delete minXExtPos;
    minYExtPos = 0;
    
    delete minXExtPos;
    maxYExtPos = 0;
}

void SiSEASprite::xAdd(float nr)
{
    oldPos = pos;
    xOld = xPos; 
    xPos += nr; 
    pos->SetX(xPos);
    calcVectors();

    return;
}

void SiSEASprite::yAdd(float nr)
{
    oldPos = pos;
    yOld = yPos; 
    yPos += nr;  
    pos->SetY(yPos);
    calcVectors();

    return;    
}
        
void SiSEASprite::xSet(float nr)
{
    oldPos = pos;
    xOld = xPos; 
    xPos = nr;
    pos->SetX(xPos);
    calcVectors();

    return;    
}
        
void SiSEASprite::ySet(float nr)
{
    oldPos = pos;
    yOld = yPos; 
    yPos = nr;  
    pos->SetY(yPos);
    calcVectors();
    
    return;    
}
        
void SiSEASprite::xySet(float x, float y)
{
    xOld = xPos; 
    yOld = yPos; 
    xPos = x; 
    yPos = y;
    oldPos = pos; 
    pos->SetXY(xPos,yPos);
    calcVectors();
    
    return;    
}


// Drawing functions
void SiSEASprite::draw(void)
{
    if(mAnimating)
    {
        
        if((mLastUpdate+mSpriteBase->mAnim[mFrame].pause*mSpeed) < SDL_GetTicks())
        {
            mFrame++;
            
            if (mFrame > (mSpriteBase->GetFramesNum()-1))
            {
                
                mFrame = 0;
            }
            
            mLastUpdate = SDL_GetTicks();
        }
    }
    
    if(!mDrawn)
    {
        mDrawn = true;  
    }
    
    DrawSpriteIMG(mSpriteBase->mAnim[mFrame].image, xPos, yPos);
    
    return;
}
        
void SiSEASprite::clearBG(void)
{
    if(mDrawn)
    {
        
        SDL_Rect dest;
        
        dest.x = (Sint16)xOld;
        dest.y = (Sint16)yOld;
        dest.w = mSpriteBase->GetWidth();
        dest.h = mSpriteBase->GetHeight();
        
        DrawSpriteIMG(mSpriteBase->mAnim[mFrame].image, xPos, yPos);
    }
    
    return;   
}

void SiSEASprite::updateBG(void)
{   
    SDL_Rect srcRect;
    
    srcRect.w = mSpriteBase->GetWidth();
    srcRect.h =  mSpriteBase->GetHeight();
    srcRect.x = (Sint16)xPos;
    srcRect.y = (Sint16)yPos;
    xOld = xPos;
    yOld = yPos;
    
    DrawSpriteIMG(mSpriteBase->mAnim[mFrame].image, xPos, yPos);
    
    return;
}

void SiSEASprite::DrawSpriteIMG(SDL_Surface *img, float x, float y)
{
    SDL_Rect dest;
    
    dest.x = (Sint16)x;
    dest.y = (Sint16)y;
    
    SDL_BlitSurface(img, NULL, mScreen, &dest);
    
    return;
}

void SiSEASprite::calcVectors(void)
{
    calcCentre();
    calcExtents();
    minXExtPos->SetXY(minXExtent,centreY);
    maxXExtPos->SetXY(maxXExtent,centreY);
    minYExtPos->SetXY(centreX,minYExtent);
    maxYExtPos->SetXY(centreX,maxYExtent);
    centre->SetXY(centreX,centreY);
    
    return;
}
    
void SiSEASprite::calcExtents(void)
{
    oldMinXExtPos = minXExtPos;
    oldMaxXExtPos = maxXExtPos;
    oldMinYExtPos = minYExtPos;
    oldMaxYExtPos = maxYExtPos;
    calcXExtents();
    calcYExtents();   
    
    return;
}
        
void SiSEASprite::calcXExtents(void)
{
    minXExtent = xPos;
    maxXExtent = xPos+mSpriteBase->mAnim[mFrame].image->w;
    
    return;
}
        
void SiSEASprite::calcYExtents(void)
{
    minYExtent = yPos;
    maxYExtent = yPos+mSpriteBase->mAnim[mFrame].image->h;
    
    return;
}

void SiSEASprite::calcCentre(void)
{
    centreX = xPos+(mSpriteBase->mAnim[mFrame].image->w/2);
    centreY = yPos+(mSpriteBase->mAnim[mFrame].image->h/2);
    
    return;
}


Share this post


Link to post
Share on other sites
Advertisement
Don't do a gazillion accesses like that. Instead, implement the collision detection as a Sprite method, because that's where the data lies that is needed for the collision. You can then add a wrapper if it's more convenient:

// along these lines...
T collide(Sprite* a, Sprite* b) {
a->collide(b);
}

Share this post


Link to post
Share on other sites
Okay I have done that, thanks Zahlman.

Have requested that the post be moved. Think it might be in the wrong one..:)

[Edited by - garyfletcher on May 12, 2005 5:34:37 AM]

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!