2D Collision Detection help?

[Chuckleluck]

Can someone give me some resources (books, online tutorials, etc.) on algorithms for 2D collision detection? I've searched a little, and all the ones I can find are for 3D collision detection.

Thanks in advance.

EDIT: Just to clarify, I know how to do collision detection, just not efficiently.

[Labdabeta]

I do not know of any resources off hand, but I used to use GML's automatic collision detection and it gave a half-decent explanations in the help files. It said that it starts by checking a bounding box defined by the most extreme points on the image. A bounding box is easy to check collision for:

bool isInBox(float x, float f, float boxTop, float boxLeft, float boxBottom, float boxRight)
{
    return ((x<=boxRight&&x>=boxLeft)&&(y<=boxBottom&&y>=boxTop));
}

If that returns true you have to decide whether you want to continue checking. If you do want to continue checking you will have to break the image into a bunch of rectangles and check them. I believe there are algorithms out there that can break the image into rectangles, I just don't know any off hand.

[mrnutty]

Can someone give me some resources (books, online tutorials, etc.) on algorithms for 2D collision detection? I've searched a little, and all the ones I can find are for 3D collision detection.

Thanks in advance.

EDIT: Just to clarify, I know how to do collision detection, just not efficiently.

which shapes are you trying to find collision detection on? There seems to be tons of resource in google

[Chuckleluck]

I don't need to be exact, all I need is collision detection for boxes. The most obvious way I can think of (what labdabeta said) seems to run really slow in real-time applications where I test each box against another.

[Tumlee]

The best thing to do is to show us the class or struct you're using as a box.

[BobS0327]

Can someone give me some resources (books, online tutorials, etc.) on algorithms for 2D collision detection? I've searched a little, and all the ones I can find are for 3D collision detection.

Thanks in advance.

EDIT: Just to clarify, I know how to do collision detection, just not efficiently.

Advanced 2D Game Development has a lot of excellent information on 2D collision detection. I have access to this book if you should need additional details about the book.

Alos, check out Chris Hecker's 2D Physics totorials

[mrnutty]

I don't need to be exact, all I need is collision detection for boxes. The most obvious way I can think of (what labdabeta said) seems to run really slow in real-time applications where I test each box against another.

The box-test should be really fast. Your problem lies somewhere else. If you have a lot of boxes in the screen, then you need to do some pruning to the screen to eliminate certain checks. Post your code and we'll try to help

[Chuckleluck]

The box-test should be really fast. Your problem lies somewhere else. If you have a lot of boxes in the screen, then you need to do some pruning to the screen to eliminate certain checks. Post your code and we'll try to help

I'm using SFML, but the code is pretty straightforward even if you don't know SFML.

// Collision.h Header File
#ifndef _COLLISION_H
#define _COLLISION_H
#include <SFML/Graphics.hpp>

enum Side { LEFT, RIGHT, TOP, BOTTOM, NOHIT };
Side CollisionBoxTest(sf::Sprite ObjectA, sf::Sprite ObjectB);

#endif

// Collision.cpp C++ Source Code
#include "Collision.h"

Side CollisionBoxTest(sf::Sprite Hitter, sf::Sprite Hittee)
{

    sf::Rect<int> HitterBox;
    sf::Rect<int> HitteeBox;

    // Get the image of sprite, so we can extract the height & width
    sf::Vector2f HitterFar = Hitter.GetSize();
    sf::Vector2f HitteeFar = Hittee.GetSize();

    // Initialize parameters for Hitterbox
    int BoxHeight = HitterFar.y;
    int BoxWidth = HitterFar.x;
    sf::Vector2f BoxPos = Hitter.GetPosition();

    // Pass parameters to HitterBox
    HitterBox.Left = BoxPos.x;
    HitterBox.Right = BoxPos.x + BoxWidth;
    HitterBox.Top = BoxPos.y;
    HitterBox.Bottom = BoxPos.y + BoxHeight;

    // Change the parameters to HitteeBox
    BoxHeight = HitteeFar.y;
    BoxWidth = HitteeFar.x;
    sf::Vector2f BoxPos1 = Hittee.GetPosition();

    // Pass parameters to HitteeBox
    HitteeBox.Left = BoxPos1.x;
    HitteeBox.Right = BoxPos1.x + BoxWidth;
    HitteeBox.Top = BoxPos1.y;
    HitteeBox.Bottom = BoxPos1.y + BoxHeight;

    // Test for collision by examining the two rects created around the sprite's images
    if(HitterBox.Bottom >= HitteeBox.Top && HitterBox.Top <= HitteeBox.Bottom &&
       HitterBox.Right >= HitteeBox.Left && HitterBox.Left <= HitteeBox.Right)
       {
        if(HitterBox.Top < HitteeBox.Top && HitteeBox.Top < HitterBox.Bottom && HitterBox.Bottom < HitteeBox.Bottom)
            return BOTTOM;
        else if(HitteeBox.Top < HitterBox.Top && HitterBox.Top < HitteeBox.Bottom && HitteeBox.Bottom < HitterBox.Bottom)
            return TOP;
        else if(HitterBox.Left < HitteeBox.Left && HitteeBox.Left < HitterBox.Right && HitterBox.Right < HitteeBox.Right)
            return RIGHT;
        else if(HitteeBox.Left < HitterBox.Left && HitterBox.Left < HitteeBox.Right && HitteeBox.Right < HitterBox.Right)
            return LEFT;
       }
    else
        return NOHIT;
}

[mrnutty]

>> CollisionBoxTest(sf::Sprite Hitter, sf::Sprite Hittee) Change that to take a constant reference. Copying Sprite can be expensive. So try making that into CollisionBoxTest(const sf::Sprite& Hitter, const sf::Sprite& Hittee) . Make sure to change the prototype as well. Also you can do without creating all of those temporaries, but for now leave them. Change the above first and see if it helps. Also show us how you are calling it, more specifically the context its being called from? It is important to know if its being called 1000 times per second ?

[Chuckleluck]

I'm using it in a 2D sidescrolling game, so every frame I test each player (in this case 4) against a couple of leaf sprites and the ground using this method. The game runs (or is supposed to run) at around 45 FPS.

[raptr_dflo]

That number of collision-tests shouldn't be bad. Most of "efficiency" involves a priori knowledge of what's going on. For example, if the ground stays flat and your players start above the ground, and are supposed to stay there, then you can use a simpler collision: just make sure each player.y is above groundHeight ... you don't need to test if the player's head (player.y + player.h) is intersecting the bottom of the ground-rect!

Once you need to test a player against a huge number of objects, it starts to help if you group objects that are near each other into a single bounding box -- if the player doesn't intersect that box, then he can't be intersecting any of the items inside it. Again, for stationary objects or objects that move together nicely, determining the bounding box can be done once (or updated very simply). If all of your objects are flying around randomly with respect to each other, that's when it gets challenging!