Sign in to follow this  

Collision detection in 2d games?

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

So far for my games (which are very simple) i use 2 dimensional array to see if a position is full or empty. This has worked just fine. But now let's say i want to create a pacman clone, where the obstacles are not of the same size as the ghosts and the pacman, and so i can't use an array. Well, i could, but i'm looking for something more practical. At first i thought about checking if the new position of a ghost/pacman contains a pixel with an alpha value > 0, if yes, don't move, if no, move. But i'm sure there are faster more efficient ways? One last thing, what's the difference between a sprite and a tile?

Share this post


Link to post
Share on other sites
Well, if you first test against a bounding shape (i.e. rectangle) and then per pixel only if the first test suceeded, I suppose it should be fast enough...

Share this post


Link to post
Share on other sites
There are simple collision detection methods all the way up to more complex ones. What you were talking about checking pixels and their aplha values would be accurate but slow. If you want to do this, you only want to check pixels if you think that there is a good chance that there indeed may be a collision. So you need a fast way to cull the cases for which there is no need to start checking pixels.

A circle-circle technique, to quote my last post:
For circle-circle, each 'physical' object has a collision circle associated with it. This circle could have its center on the center of the sprite and its radius could encompass the sprite. That way, in this simple collision detection scheme, to detect collisions between to objects you could check if the origins of the two objects' collision circles are closer than the sum of their radii.

This circle-circle detection could be a first phase in the detection scheme. If more accuracy is required then, you can check pixels for the cases where the circles overlap since there is a good chance that pixels may overlap. Note: just check how it looks. Circle-circle sometimes is all that is required.

The other thing is you can check every possible collision in a double nested for loop for N objects. But as N-->large you may have speed/efficiency problems. If so, google quadtree or sort and sweep for more advanced methods.

Quote:

One last thing, what's the difference between a sprite and a tile?

A sprite is usually an animated object in the game like the player, an enemy, a powerup, etc. A tile is usually just a square(or rectangle) background object whose graphics allow it to be seamlessly tiled so that it looks like a continuous background image.

Share this post


Link to post
Share on other sites
Sprite is a bit of an historical term. In the glorious 8 bit days, a lot of computers had hardware support for drawing images with transparent pixels over the existing screen buffer. These were termed sprites, so the term has evolved to normally mean a moving image.

For a pacman clone I'd try just using bounding axis-aligned bounding boxes for the collisions. I'm fairly sure that this would provide realistic-enough collisions and the intersection test is trivial.


struct Vec
{
float x,y;
};

struct AABB
{
Vec Min,Max;
};

bool Intersect(const AABB &A,const AABB &B)
{
return(A.Max.x>=B.Min.x && A.Min.x<=B.Max.x && A.Max.y>=B.Min.y && A.Min.y<=B.Max.y);
}


If that was not sufficient for your needs, you'd need to look at implementing SAT for a minimum of AABB vs circle and AABB vs AABB. Pacman could then be modelled with a circle and the ghosts as a circle and a box combination (assuming the traditional pacman and ghost images), which would provide a very tight collision system without the overhead of per-pixel checking.

Saying that, as long as the collision maps were stored in system memory rather than being GetPixel-ed from some kind of device dependant image, I wouldn't imagine that a per pixel test would be that expensive, provided you first did AABB vs AABB to see if there was a possible intersection.

You could create arrays of bools representing each pixels solidity for the images at startup and use this data to do the per-pixel testing. This used to be done using bitmasks but I doubt now that the speed increase on modern hardware would be worth the additional complications of shifting and masking the bits. It would be buffer lock/unlocks or GetPixel() from a DDB that would be the real bottleneck.

Share this post


Link to post
Share on other sites
In my 2d platformer game, I originally used my own collision detection code based on the SAT. However, once I added moving platforms, I found it impossible to resolve collisions consistently.

So I switched to Box2d. It has its own problems and is somewhat difficult to use (no documentation at the moment, although they're working on that), but it is still way better then my old system. I would recommend it for any 2d game which uses physics in a nontrivial way.

Share this post


Link to post
Share on other sites

This topic is 2844 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.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this