Problems with SAT Collision Detection

Posted by DJ AzKai on Game Development See other posts from Game Development or by DJ AzKai
Published on 2013-10-28T17:40:02Z Indexed on 2013/10/28 22:14 UTC
Read the original article Hit count: 252

Filed under:
|
|

I'm doing a project in one of my modules for college in C++ with SFML and I was hoping someone may be able to help me. I'm using a vector of squares and triangles and I am using the SAT collision detection method to see if objects collide and to make the objects respond to the collision appropriately using the MTV(minimum translation vector)

Below is my code:

//from the main method
int main(){

    // Create the main window 
    sf::RenderWindow App(sf::VideoMode(800, 600, 32), "SFML OpenGL"); 


    // Create a clock for measuring time elapsed     
    sf::Clock Clock; 
    srand(time(0));
    //prepare OpenGL surface for HSR 
    glClearDepth(1.f); 
    glClearColor(0.3f, 0.3f, 0.3f, 0.f); //background colour
    glEnable(GL_DEPTH_TEST); 
    glDepthMask(GL_TRUE); 

    //// Setup a perspective projection & Camera position 
    glMatrixMode(GL_PROJECTION); 
    glLoadIdentity(); 

    //set up a 3D Perspective View volume
    //gluPerspective(90.f, 1.f, 1.f, 300.0f);//fov, aspect, zNear, zFar 

    //set up a  orthographic projection same size as window
    //this mease the vertex coordinates are in pixel space
    glOrtho(0,800,0,600,0,1); // use pixel coordinates


    // Finally, display rendered frame on screen 
        vector<BouncingThing*> triangles;
        for(int i = 0; i < 10; i++)
        {   //instantiate each triangle;
            triangles.push_back(new BouncingTriangle(Vector2f(rand() % 700, rand() % 500), 3));         
        }
        vector<BouncingThing*> boxes;
        for(int i = 0; i < 10; i++)
        {   //instantiate each box;
            boxes.push_back(new BouncingBox(Vector2f(rand() % 700, rand() % 500), 4));          
        }
        CollisionDetection * b = new CollisionDetection();
    // Start game loop 
    while (App.isOpen()) 
    { 

        // Process events 
        sf::Event Event; 
        while (App.pollEvent(Event)) 
        { 
            // Close window : exit 
            if (Event.type == sf::Event::Closed) 
                App.close(); 

            // Escape key : exit 
            if ((Event.type == sf::Event::KeyPressed) && (Event.key.code == sf::Keyboard::Escape)) 
                App.close();  
        }


        //Prepare for drawing 
        // Clear color and depth buffer 
        glClear(GL_COLOR_BUFFER_BIT | GL_DEPTH_BUFFER_BIT); 

        // Apply some transformations 
        glMatrixMode(GL_MODELVIEW); 
        glLoadIdentity();   

        for(int i = 0; i < 10; i++)
        {
            triangles[i]->draw();
            boxes[i]->draw();
            triangles[i]->update(Vector2f(800,600));
            boxes[i]->draw();
            boxes[i]->update(Vector2f(800,600));
        }
        for(int j = 0; j < 10; j++)
        {
            for(int i = 0; i < 10; i++)
            {
                triangles[j]->setCollision(b->CheckCollision(*(triangles[j]),*(boxes[i])));
            }
        }
        for(int j = 0; j < 10; j++)
        {
            for(int i = 0; i < 10; i++)
            {
                boxes[j]->setCollision(b->CheckCollision(*(boxes[j]),*(triangles[i])));
            }
        }

        for(int i = 0; i < triangles.size(); i++)
        {
            for(int j = i + 1; j < triangles.size(); j ++)
            {
                triangles[j]->setCollision(b->CheckCollision(*(triangles[j]),*(triangles[i])));
            }
        }
        for(int i = 0; i < triangles.size(); i++)
        {
            for(int j = i + 1; j < triangles.size(); j ++)
            {
                boxes[j]->setCollision(b->CheckCollision(*(boxes[j]),*(boxes[i])));
            }
        }
        App.display(); 
    } 

    return EXIT_SUCCESS; 
}

(ignore this line)

//from the BouncingThing.cpp
BouncingThing::BouncingThing(Vector2f position, int noSides)
    : pos(position), pi(3.14), radius(3.14), nSides(noSides)
{
    collided = false;


    if(nSides ==3)
    {
        Vector2f vert1 = Vector2f(-12.0f,-12.0f);
        Vector2f vert2 = Vector2f(0.0f, 12.0f);
        Vector2f vert3 = Vector2f(12.0f,-12.0f);
        verts.push_back(vert1);
        verts.push_back(vert2);
        verts.push_back(vert3);
    }
    else if(nSides == 4)
    {

        Vector2f vert1 = Vector2f(-12.0f,12.0f);
        Vector2f vert2 = Vector2f(12.0f, 12.0f);
        Vector2f vert3 = Vector2f(12.0f,-12.0f);
        Vector2f vert4 = Vector2f(-12.0f, -12.0f);
        verts.push_back(vert1);
        verts.push_back(vert2);
        verts.push_back(vert3);
        verts.push_back(vert4);
    }
    velocity.x = ((rand() % 5 + 1) / 3) + 1;
    velocity.y = ((rand() % 5 + 1) / 3 ) +1;
}

void BouncingThing::update(Vector2f screenSize)
{
    Transform t;
    t.rotate(0);
    for(int i=0;i< verts.size(); i++)
    {
        verts[i]=t.transformPoint(verts[i]);
    }

    if(pos.x >= screenSize.x || pos.x <= 0)
    {
        velocity.x *= -1;
    }
    if(pos.y >= screenSize.y || pos.y <= 0)
    {
        velocity.y *= -1;
    }
    if(collided)
    {
        //velocity.x *= -1;
        //velocity.y *= -1;
        collided = false;
    }
    pos += velocity;
}
void BouncingThing::setCollision(bool x){
    collided = x;
}

void BouncingThing::draw()
{

    glBegin(GL_POLYGON);
        glColor3f(0,1,0);
        for(int i = 0; i < verts.size(); i++)
        {
            glVertex2f(pos.x + verts[i].x,pos.y + verts[i].y);              
        }
    glEnd();
}


vector<Vector2f> BouncingThing::getNormals()
{
    vector<Vector2f> normalVerts;
    if(nSides == 3)
    {
        Vector2f ab = Vector2f((verts[1].x + pos.x) - (verts[0].x + pos.x), (verts[1].y + pos.y) - (verts[0].y + pos.y));
        ab = flip(ab);
        ab.x *= -1;
        normalVerts.push_back(ab);
        Vector2f bc = Vector2f((verts[2].x + pos.x) - (verts[1].x + pos.x), (verts[2].y + pos.y) - (verts[1].y + pos.y));
        bc = flip(bc);
        bc.x *= -1;
        normalVerts.push_back(bc);
        Vector2f ac = Vector2f((verts[2].x + pos.x) - (verts[0].x + pos.x), (verts[2].y + pos.y) - (verts[0].y + pos.y));
        ac = flip(ac);
        ac.x *= -1;
        normalVerts.push_back(ac);
        return normalVerts;
    }
    if(nSides ==4)
    {
        Vector2f ab = Vector2f((verts[1].x + pos.x) - (verts[0].x + pos.x), (verts[1].y + pos.y) - (verts[0].y + pos.y));
        ab = flip(ab);
        ab.x *= -1;
        normalVerts.push_back(ab);
        Vector2f bc = Vector2f((verts[2].x + pos.x) - (verts[1].x + pos.x), (verts[2].y + pos.y) - (verts[1].y + pos.y));
        bc = flip(bc);
        bc.x *= -1;
        normalVerts.push_back(bc);
        return normalVerts;
    }
}

Vector2f BouncingThing::flip(Vector2f v){
    float vyTemp = v.x;
    float vxTemp = v.y * -1;
    return Vector2f(vxTemp, vyTemp);
}

(Ignore this line)

    CollisionDetection::CollisionDetection()

{
}

vector<float> CollisionDetection::bubbleSort(vector<float> w) {
    int temp;
    bool finished = false;
    while (!finished)    {
       finished = true;
       for (int i = 0; i < w.size()-1; i++) {
          if (w[i] > w[i+1]) {
             temp = w[i];
             w[i] = w[i+1];
             w[i+1] = temp;
             finished=false;
          }
        }
     }
    return w; 
}

class Vector{
    public:
    //static int dp_count;
    static float dot(sf::Vector2f a,sf::Vector2f b){
        //dp_count++;
        return a.x*b.x+a.y*b.y;
    }

    static float length(sf::Vector2f a){
        return sqrt(a.x*a.x+a.y*a.y);
    }
    static Vector2f add(Vector2f a, Vector2f b)
    {
        return Vector2f(a.x + b.y, a.y + b.y);
    }



    static sf::Vector2f getNormal(sf::Vector2f a,sf::Vector2f b){
        sf::Vector2f n;
        n=a-b; 
        n/=Vector::length(n);//normalise
        float x=n.x;
        n.x=n.y;
        n.y=-x;
        return n;
    }

};

bool CollisionDetection::CheckCollision(BouncingThing & x, BouncingThing & y)
{
    vector<Vector2f> xVerts = x.getVerts();
    vector<Vector2f> yVerts = y.getVerts();
    vector<Vector2f> xNormals = x.getNormals();
    vector<Vector2f> yNormals = y.getNormals();
    int size;
    vector<float> xRange;
    vector<float> yRange;
    for(int j = 0; j < xNormals.size(); j++)
    {
        Vector p;
        for(int i = 0; i < xVerts.size(); i++)
        {           
            xRange.push_back(p.dot(xNormals[j], Vector2f(xVerts[i].x, xVerts[i].x)));
        }
        for(int i = 0; i < yVerts.size(); i++)
        {
            yRange.push_back(p.dot(xNormals[j], Vector2f(yVerts[i].x , yVerts[i].y)));
        }
        yRange = bubbleSort(yRange);
        xRange = bubbleSort(xRange);
        if(xRange[xRange.size() - 1] < yRange[0] || yRange[yRange.size() - 1] < xRange[0])
        {
            return false;
        }
        float x3 = Min(xRange[0], yRange[0]);
        float y3 = Max(xRange[xRange.size() - 1], yRange[yRange.size() - 1]);
        float length = Max(x3, y3) - Min(x3, y3);
    }
    for(int j = 0; j < yNormals.size(); j++)
    {
        Vector p;
        for(int i = 0; i < xVerts.size(); i++)
        {           
            xRange.push_back(p.dot(yNormals[j], xVerts[i]));
        }
        for(int i = 0; i < yVerts.size(); i++)
        {
            yRange.push_back(p.dot(yNormals[j], yVerts[i]));
        }
        yRange = bubbleSort(yRange);
        xRange = bubbleSort(xRange);
        if(xRange[xRange.size() - 1] < yRange[0] || yRange[yRange.size() - 1] < xRange[0])
        {
            return false;
        }
    }

    return true;
}

float CollisionDetection::Min(float min, float max)
{
    if(max < min)
    {
        min = max;
    }
    else return min;
}

float CollisionDetection::Max(float min, float max)
{
    if(min > max)
    {
        max = min;
    }
    else return min;
}

On the screen the objects will freeze for a small amount of time before moving off again. However the problem is is that when this happens there are no collisions actually happening and I would really love to find out where the flaw is in the code. If you need any more information/code please don't hesitate to ask and I'll reply as soon as possible Regards, AzKai

© Game Development or respective owner

Related posts about c++

Related posts about sfml