Jump to content
  • Advertisement
Sign in to follow this  
Actium

2D Collision Detection

This topic is 3699 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

Hiya, I've written most of my first ever 2D graphics engine using C and SDL. It is based on sprites that have different animations that have frames; animations can be toggled, sprites can be moved and scaled, etc. My idea for collision detection would work like this: Separate collision rectangles can be created. A function would exist ("collision handler adder") that would take as arguments two rectangles to check, a function pointer to a handler for this specific collision, and parameters to pass this function. This "collision handler adder" would use a linked list to store the data. The collision "checker" would then traverse through the list and call the appropriate functions if a collision is found to have occurred. This "checker" would run every time my main game loop runs. So, I could create 2 different rectangles and move them around the screen, and if they were to collide it would run some function A. It seems to make sense to me that this form of collision detection would work well. Is this a good method, or is there a better way to do this?

Share this post


Link to post
Share on other sites
Advertisement
This method seems unnecessarily complicated. Especially when you consider tiles and such, a linked list is simply not the right solution. A simple array or vector is much better.

You kind of have the right idea with the collision handler. What I do, is simply have the collision manager have access to the map, player, and enemies. You call a function like validmove() and it will see if the move can be performed on the map. Then at another point I just check the player against enemies, objects, etc, and handle the response there.

Share this post


Link to post
Share on other sites
I have a Collision Manager hold all the GameObjects which are able to collide with each other in a dictionary (in using c# at the mo), the key is the object type, and the value a is a list of game objects of that type.

That way I can traverse through all the objects of the type im interested in and take appropriate action.


foreach(GameObject bullet in collidables[typeof(Bullet)])
{
foreach(GameObject enemy in collidables[typeof(Enemy)])
{
if(isColliding(bullet, enemy))
Collision((Bullet)bullet, (Enemy)enemy);
}
}


public void Collision(Bullet b, Enemy e)
{
// do something with colliding enemy and bullet
}

Share this post


Link to post
Share on other sites
If you have too many objects in your space then checking each object with every other object might be expensive. I've once employed a system which divides the 2D space into rectangular regions or areas.

The regions or areas (something like North, South, Northwest, Center, etc.) are big enough such that an object cannoy jump across two regions in one frame.

Now all you have to do is make sure to update which region an object likes in during every move. In your collision detection phase, you just have to check for collisions between each object and objects in the adjacent regions (in case of border crossing collision).

This approach might seem complicated and unnecessary but it helps if you have something like a tile-based game with hundreds of objects most of which roam around in a specific area.

Share this post


Link to post
Share on other sites
@cclyde: linked lists aren't that complicated ;P this isn't a doubly linked list, it only works in one direction; which means that a simple

rfg_sprite * t = global->sprites;
while (t != NULL) {
// do something with the sprite
t = t->n;
}
printf ("We've done all the sprites!");

does the trick instead of a foreach. An array? Then I can only check COLLISION_MAX or something number of collisions, but I want to be able to check as many collisions as I want.

I can create five objects (A, B, C, D, E) and then register collision handlers for only B with E or D with C. Understand that collision detection is engine side; but deciding which collisions to check, and handling these collisions, is not.

@DaveMS: Again, no foreaches in C, which is why I'm using linked lists. But that's the general idea; except instead of calling a generic Collision function, the programmer of the game would give the engine a function ptr to a collision handler for that specific collision.

@Verminox: I'm checking rectangles; not doing per-pixel detection. It's just integer comparison; if the X positions of either of the two sides of rectangle 1 fall inside rectangle 2, then I check the same for the Y; if this is true then the objects have collided. I can store a rectangle in memory with four ints; I just compare the ints of one rectangle with the ints of another rectangle. I don't really see how this is at all complicated.

So, one run of the engine collision handler would do something like:

rfg_collision * t = global->collisions;
while (t != NULL) {
if ((t->rect_1->x_1 >= t->rect_2->x_1) && (t->rect_1->x_1 <= t->rect_2->x_2))
//the left side of rect 1 is inside rect 2. Check y axis..
if ((t->rect_1->y_1 >= t->rect_2->y_1) && (t->rect_1->y_1 <= t->rect_2->y_2))
//collided. Call collision function
t->collision_function (global, t->param1, t->param2);
// now I'd have to do the same for the other side of rect 1..
t = t->n;
}

This is only a couple of integer comparisons per collision to detect, and that's not very many. I know those comparisons look messy, but they're not really all that complicated, and considering it's only integer comparisons it should go really fast.

//edit: rfg_collision would be something like
typedef struct {
rfg_rect * rect_1; // first rectangle
rfg_rect * rect_2; // second rectangle
rfg_collision_handler_t * collision_function; // pointer to the collision handler function
void * param1; // first param to pass collision_function
void * param2; // second param to pass collision_function
void * n; // pointer to next node in the list
} rfg_collision;

Share this post


Link to post
Share on other sites
From the R&D that I've done, it looks like the "best" method of collision detection is something like the following:


class CollisionInfo
{
private:
vector2d m_OutPenetration; // Output: penetration
vector2d m_OutContact; // Output: contact point in A's local space
vector2d m_OutNormal; // Output: contact normal in A's local space

public:
const vector2d& GetPenetration(void) const; // etc.
};

class BoundingVolume
{
public:
virtual ~BoundingVolume();

public:
// velocity is optional, collision info is optional

virtual bool Collision(const BoundingVolume* pOther, const vector2d* pVelocity, CollisionInfo* pOutCollisionInfo);
};

class BoundingVolumeCircle: public BoundingVolume
{
private:
vector2d m_center;
float m_fRadius;

public:
const vector2d& GetCenter(void) const; // etc

virtual bool Collision(...);
};

class BoundingVolumeAABB: public BoundingVolume
{
private:
vector2d m_min;
vector2d m_max;

public:
const vector2d& GetMin(void) const; // etc.

virtual bool Collision(...);
};

class BoundingVolumeOBB: public BoundingVolume
{
private:
vector2d m_center;
vector2d m_axis[2];
vector2d m_lengths[2];

public:
//// etc.
};



class Entity: public Object
{
protected:
// These two arrays would be filled & updated by AI code

vector<BoundingVolume*> m_arCollisionBounds;
vector<BoundingVolume*> m_arRenderBounds;

public:
const BoundingVolume* GetRenderBounds(int nLOD)
{
if(m_arRenderBounds.empty()) return NULL;
if(nLOD < 0 || nLOD >= int(m_arRenderBounds.size())) return &m_arRenderBounds[0];

return &m_arRenderBounds[nLOD];
};

const BoundingVolume* GetCollisionBounds(int nLOD)
{
if(m_arCollisionBounds.empty()) return NULL;
if(nLOD < 0 || nLOD >= int(m_arCollisionBounds.size())) return &m_arCollisionBounds[0];
};
};


Then when you check collision, you progressively increase LOD as long as you keep getting positives.

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.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!