collision detection methodology

Question

I've been programming in C++ for about 6 months now, still a beginner, but I've been messing around with creating a collision detection system for a game. I've devised a way to take a polygon, and test a point to see if its within that polygon. Once I get a better handle on the graphics, I'll run an animation loop that tests all enemies with all projectiles, then moves them all according to their movement functions.

The way I've handled the collision detection is to use the system illustrated in this link. The code I created can be seen here and below. My question is, are all of these processes too much to run for every single bounding box (every enemy) for every single frame? I know processing speed and efficiency are extremely important in game design, so is this type of methodology too long-winded or am I underestimating how fast processors actually operate? Any advice on how these things are typically handled is appreciated.

#include <iostream>
#include <vector>


class point
{
    public:
        point (int a, int b): x(a), y(b) {};
        ~point () {};

        int getX() {return x;}
        int getY() {return y;}

    private:
        int x;
        int y;
};


class side
{
    public:
        side(point f, point s): first(f), second(s) {};
        ~side() {};
        point getFirst() {return first;}
        point getSecond() {return second;}

    private:
        point first;
        point second;
};


class boundingBox
{
    public:
        boundingBox(std::vector <point> p);
        ~boundingBox() {};

        std::vector <side> getSides() {return boundingSides;}

    private:
        std::vector <point> boundingPoints;
        std::vector <side> boundingSides;
};


boundingBox::boundingBox(std::vector <point> p)
{
    boundingPoints = p;

    // in the constructor, create a vector of sides from the points
    for (std::vector <point>::iterator i = boundingPoints.begin(); i != boundingPoints.end()-1; i++)
    {
        boundingSides.push_back( side(*i, *(i+1)) );
    }

    boundingSides.push_back( side (*(boundingPoints.end()-1), *(boundingPoints.begin()) ) );
}






bool collisionCheck(std::vector <side> s, point p)
{
    std::vector <side> nodeSides;

    int toleft = 0;
    int toright = 0;

    for (std::vector <side>::iterator i = s.begin(); i != s.end(); i++)
    {
        //if the Y value of the point being tested is between the Y values of a side, add a node
        if (p.getY() > (*i).getFirst().getY() && p.getY() < (*i).getSecond().getY() ||
            p.getY() < (*i).getFirst().getY() && p.getY() > (*i).getSecond().getY() )
        {
            nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
        }


        // if the Y value of the point being tested is also the Y of the second point of the side...
        if (p.getY() == (*i).getSecond().getY())
        {
            //if it isn't the last side, and this side and the next strattle that y value, add a node
            if (i != s.end()-1)
            {
                if ((*i).getFirst().getY() < p.getY() && (*(i+1)).getSecond().getY() > p.getY() ||
                    (*i).getFirst().getY() > p.getY() && (*(i+1)).getSecond().getY() < p.getY() )
                {
                    nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
                }   
            }   

            //if it is the last side, and this side and the first side strattle that y value, add a node
            else if ((*i).getFirst().getY() < p.getY() && s.front().getSecond().getY() > p.getY() ||
                 (*i).getFirst().getY() > p.getY() && s.front().getSecond().getY() < p.getY() )
            {
                nodeSides.push_back( side ( (*i).getFirst(), (*i).getSecond() ) );
            }
        }
    }

    for (std::vector <side>::iterator i = nodeSides.begin(); i != nodeSides.end(); i++)
    {
        double deltaY = (*i).getSecond().getY() - (*i).getFirst().getY();
        double deltaX = (*i).getSecond().getX() - (*i).getFirst().getX();

        double slope = deltaX - deltaY;

        double x = ( p.getY() - (*i).getSecond().getY() + (slope * (*i).getSecond().getX()) ) / slope;

        if (x < p.getX()) 
        {
            toleft++;
        }

        else
        {
            toright++;
        }
    }


    std::cout << "Analysis: " << toleft << " nodes to the left, " << toright << " nodes to the right." << std::endl;

    if (toleft % 2 == 0)
    {
        std::cout << "return false, does not hit" << std::endl;
        return false;
    }

    else
    {
        std::cout << "return true, hits" << std::endl;
        return true;
    }
}






int main ()
{
    std::vector <point> points;

    points.push_back(point(3, 5));
    points.push_back(point(1, 13));
    points.push_back(point(7, 16));
    points.push_back(point(14, 14));
    points.push_back(point(8, 13));
    points.push_back(point(9, 11));
    points.push_back(point(17, 13));
    points.push_back(point(16, 18));
    points.push_back(point(21, 15));
    points.push_back(point(17, 9));
    points.push_back(point(9, 7));
    points.push_back(point(12, 5));
    points.push_back(point(14, 7));
    points.push_back(point(15, 2));
    points.push_back(point(6, 3));

    boundingBox enemy(points);

    point hitSimp(13, 4);
    point hitComp(19, 15);
    point missNear(10, 12);
    point missFar(100,100);

    collisionCheck(enemy.getSides(), hitSimp);

    collisionCheck(enemy.getSides(), hitComp);

    collisionCheck(enemy.getSides(), missNear);

    collisionCheck(enemy.getSides(), missFar);

    return 0;
}

Answer 1

If your program will be bound by checking too many collisions, look into Quad Trees

You can also first check simple bounding volumes such as axis-aligned and oriented bounding boxes before you do polygon collision tests.