optomized collisions to exclude half of the tests

[physics.git] / src / collisionManager.cpp

/*
 *  Copyright (C) 2008 Patrik Gornicz, Gornicz_P (at) hotmail (dot) com.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation, either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details.
 *
 *  You should have received a copy of the GNU General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include "collisionManager.h"
#include "debug.h"

#include "Vector2.h"

#include "Entities/Ball.h"
#include "Entities/PhysicsEntity.h"

#include "CollisionInfo.h"

/// ***** Private Class Header *****

/// ***** Private Method Headers *****

void clearEntities();
void placeEntity(PhysicsEntity* p);
void updateEntities();

void applyCollision(PhysicsEntity* p1, PhysicsEntity* p2);
void applyCollision(Ball* b1, Ball* b2);

bool getInfo(Ball* b1, Ball* b2, CollisionInfo* cInfo);

/// ***** Private Variables *****

const int xDivisions = 20;
const int yDivisions = 16;
const int screenX    = 800;
const int screenY    = 600;

setPhys divisions[xDivisions][yDivisions];

/// ***** Initializers/Cleaners *****

void collision::init()
{

}
void collision::clean()
{

}

/// ***** Public Methods *****

void collision::update(setPhys& sp)
{
    clearEntities();

    for( setPhys::iterator it = sp.begin();
         it != sp.end();
         it++ )
    {
        placeEntity(*it);
    }

    updateEntities();
}

/// ***** Private Methods *****

void clearEntities()
{
    for( int x = 0;
             x < xDivisions;
             x++ )
    {
        for( int y = 0;
                 y < yDivisions;
                 y++ )
        {
            divisions[x][y].clear();
        }
    }
}

void placeEntity(PhysicsEntity* p)
{
    Ball* b = dynamic_cast<Ball*>(p);

    if( b == NULL )
    {
        DPF(0, "ENTITY TYPE NOT SUPPORTED BY placeEntity()!!");
        return;
    }

    const float& xb     = b->positionRaw().x;
    const float& yb     = b->positionRaw().y;
    const float& rad    = b->radius;

    for( int x =  static_cast<int>( (xb - rad) / (screenX / xDivisions) );
             x <= static_cast<int>( (xb + rad) / (screenX / xDivisions) );
             x++ )
    {
        if(x < 0 || xDivisions <= x)
            break;

        for( int y =  static_cast<int>( (yb - rad) / (screenY / yDivisions) );
                 y <= static_cast<int>( (yb + rad) / (screenY / yDivisions) );
                 y++ )
        {
            if(y < 0 || yDivisions <= y)
                break;

            divisions[x][y].insert(p);
        }
    }
}

void updateEntities()
{
    for( int x = 0;
             x < xDivisions;
             x++ )
    {
        for( int y = 0;
                 y < yDivisions;
                 y++ )
        {
            for( setPhys::iterator it1 = divisions[x][y].begin();
                 it1 != divisions[x][y].end();
                 it1++ )
            {
                for( setPhys::iterator it2 = divisions[x][y].begin();
                     it2 != divisions[x][y].end();
                     it2++ )
                {
                    if( *it1 == *it2 )
                        break;

                    applyCollision(*it1, *it2);
                }
            }
        }
    }
}

void applyCollision(PhysicsEntity* p1, PhysicsEntity* p2)
{
    Ball* b1 = dynamic_cast<Ball*>(p1);
    Ball* b2 = dynamic_cast<Ball*>(p2);

    if( b1 != NULL && b2 != NULL )
    {
        applyCollision(b1, b2);
        return;
    }

    DPF(0, "ENTITY TYPE NOT SUPPORTED BY applyCollision()!!");
}

void applyCollision(Ball* b1, Ball* b2)
{
    CollisionInfo   cInfo;

    if(!getInfo(b1, b2, &cInfo))
        return;

    // a few values to simplify the equations
    const Vector2& normal = cInfo.normal;
    const Vector2& point  = cInfo.point;

    float m1 = b1->mass;
    float m2 = b2->mass;

    float e = (b1->CoR + b2->CoR) / 2;

    Vector2 v1 = b1->velocityRaw();
    Vector2 v2 = b2->velocityRaw();


    float iTop = -(e + 1) * (v1 - v2).dot(normal);

    // otherwise the collision happened and we do the math the below assumes
    // collisions have no friction

    float impulse = iTop / (normal.dot(normal) * (1 / m1 + 1 / m2));

    b1->applyImpulse(impulse / m1 * normal, point);
    b2->applyImpulse(-impulse / m2 * normal, point);
}

bool getInfo(Ball* b1, Ball* b2, CollisionInfo* pcInfo)
{
    // a few values to simplify the equations
    float r1 = b1->radius;
    float r2 = b2->radius;

    Vector2 p1 = b1->positionRaw();
    Vector2 p2 = b2->positionRaw();
    Vector2 v1 = b1->velocityRaw();
    Vector2 v2 = b2->velocityRaw();

    // quick binding box check
    if (p1.x - r1 > p2.x + r2
     || p1.x + r1 < p2.x - r2
     || p1.y - r1 > p2.y + r2
     || p1.y + r1 < p2.y - r2)
        return false;

    // test if not touching
    if ((p1 - p2).sqrLength() >= (r1 + r2)*(r1 + r2))
        return false;

    // test if they are moving apart in some way if they aren't it's likely
    // that they collided last frame and are still overlapping

    if ((v1 - v2).dot(p1 - p2) >= 0)
        return false;

    pcInfo->point   = p1 - (p1 - p2) * r1 / (r1 + r2);
    pcInfo->normal  = p1 - p2;

    return true;
}