[.net] collision detection for 2D game in C#
Author
Hi, I'm writting a 2D shooting game using C#, i know how to do the rectangle intersection detection, but it is not very accurate since the sprites dont fully fill the rectangles.(2 rectangles intersect each other but the sprites are not actually overlapping). Therefore, could someone pls show me some sample codes of a more accurate collision detection or direct me to such tutorials.
Thanks in advance.
Hi, I believe this is a very good one for polygons. No code, but good explanation and math (actually there may be some Java): http://www.harveycartel.org/metanet/tutorials/tutorialA.html
And here looks like some interesting ideas on pixel-perfect collision detection:
http://www.experts-exchange.com/Programming/Game_Development/AI_Physics/Q_20702856.html
Hope it helps.
And here looks like some interesting ideas on pixel-perfect collision detection:
http://www.experts-exchange.com/Programming/Game_Development/AI_Physics/Q_20702856.html
Hope it helps.
Polygon intersection wont help i think, because you will have to redesign each sprite and add a fitting poligon to it. Rather you should test the sprites pixel-by-pixel :) That would be really accurate. Thest sprite A's transparent pixels against sprite B. If you find a nontransparent pixel of B under the transparent pixel of A, than an intersection occurs. Of yourse its advised to check for rectangle intersection first, to save the 99% of your CPU's time :D
I dont know your actual implementation, so cannot give more detailed advice :)
I dont know your actual implementation, so cannot give more detailed advice :)
I would recommend polygon hulls for CD. You don't have to redesign your sprites or manually create polygons, you can (in the majority of cases) calculate the hulls automatically.
Benefits:
* Increased performance using different LODs of the hull (can be done with multiple bitmaps of different resolutions as well, but it's a less elegant solution IMO)
* Better collision checking between renderings by using a moving line-line algorithm (e.g. avoids bullets passing through your object just because their relative velocity > overlap area)
* Better prepared for more complex scenarios (I sometimes use bezier curves to describe items, and break them down into lines at an appropriate resolution for actual CD)
* Sliding against edges is more difficult to implement with pixels than with lines
You can also use 3rd-party physics engines with your hulls and get a lot of extra features "for free".
Also see discussion at
http://www.gamedev.net/community/forums/topic.asp?topic_id=394445
Benefits:
* Increased performance using different LODs of the hull (can be done with multiple bitmaps of different resolutions as well, but it's a less elegant solution IMO)
* Better collision checking between renderings by using a moving line-line algorithm (e.g. avoids bullets passing through your object just because their relative velocity > overlap area)
* Better prepared for more complex scenarios (I sometimes use bezier curves to describe items, and break them down into lines at an appropriate resolution for actual CD)
* Sliding against edges is more difficult to implement with pixels than with lines
You can also use 3rd-party physics engines with your hulls and get a lot of extra features "for free".
Also see discussion at
http://www.gamedev.net/community/forums/topic.asp?topic_id=394445
This is a snippet from SDL.NET which checks for collisions between sprites using a circle collision check:
public virtual bool IntersectsWithRadius(Sprite sprite, int radius, int radiusOther, int tolerance) { if (sprite == null) { throw new ArgumentNullException("sprite"); } Point center1 = this.Center; Point center2 = sprite.Center; int xdiff = center2.X - center1.X; // x plane difference int ydiff = center2.Y - center1.Y; // y plane difference // distance between the circles centres squared int dcentre_sq = (ydiff*ydiff) + (xdiff*xdiff); // calculate sum of radiuses squared int r_sum_sq = radius + radiusOther; r_sum_sq *= r_sum_sq; return (dcentre_sq - r_sum_sq <= (tolerance * tolerance)); }
I've never tried this before, but you might be able to use the alpha as the true false for the collision. That way there is no calculation at all. You just go to that location ie (10,10) is alpha?
Or if your sprites use a color key it could be the same thing. This is assuming that you have easy access to the pixel information.
Depends on how big the sprite is and what type of game.
Really these alpha maps are the hull right?
So you would do something like :
is ( click_pos inside square )
then new_pos = click_pos - top_corner
is ( new_pos == blank_color ) no hit else hit?
Maybe I misunderstood the problem. Seems like an easier calculation to me.
Or if your sprites use a color key it could be the same thing. This is assuming that you have easy access to the pixel information.
Depends on how big the sprite is and what type of game.
Really these alpha maps are the hull right?
So you would do something like :
is ( click_pos inside square )
then new_pos = click_pos - top_corner
is ( new_pos == blank_color ) no hit else hit?
Maybe I misunderstood the problem. Seems like an easier calculation to me.
Per Pixel collision detection is very expensive.
I suggest you use the Separation of Axis Theorem as that is what I ended up using for my engine. It proved to be extremely accurate when I needed it to be. The major plus is being able to solve for any two N-Sided Convex Polygons (N > 2).
One of the best things you can do is have differing levels of detail and/or use a QuadTree structure to get samples to test. For example there is no need to test extreme details of two objects if their two bounding circles do not intersect.
I suggest you use the Separation of Axis Theorem as that is what I ended up using for my engine. It proved to be extremely accurate when I needed it to be. The major plus is being able to solve for any two N-Sided Convex Polygons (N > 2).
One of the best things you can do is have differing levels of detail and/or use a QuadTree structure to get samples to test. For example there is no need to test extreme details of two objects if their two bounding circles do not intersect.
Krisc: the OP is already using a bounding-box test, which is as good as anything unless there is a quick and easy way to create a convex bounding polygon for use with the SAT (or other) algorithm.
To the OP: You should use a cheap test (like a bounding box intersection) to find possible collisions, then you can use an expensive but accurate test to determine if the collisions actually happen. Depending on your graphics API (are you using DirectX? or just GDI+?) per-pixel tests may be really easy, or they may not.
To the OP: You should use a cheap test (like a bounding box intersection) to find possible collisions, then you can use an expensive but accurate test to determine if the collisions actually happen. Depending on your graphics API (are you using DirectX? or just GDI+?) per-pixel tests may be really easy, or they may not.
A bounding box is a very simple and fixed SAT test. You are basically testing for intersection on the X and Y axes. An OBB is a bit more complicated since the axes move. (plural of axis = axes?) Anyways, I believe a bounding circle-distance test will be slightly faster since you just have to check if the distance between the two centers is more or less than the sum of the radii.
The nice thing about the SAT is you can have any shape you want, provided it is convex. If you need a concave polygon you can split them into two convex polygons.
However as I said before your biggest improvement in efficiency will be given by a better sorting algorithm. If you look at it a standard double loop will be O(n2) where as using a QuadTree will be O(logn) which is significantly more efficient; especially for larger samples such as in a particle collision. Granted you have to build the tree before you test it (once every frame?) it will still be O(n+logn) which will still be faster... much faster. The only problem with the QuadTree is sometimes you will get an object that gets stuck in the tree twice because it is on a boundry.
Never-the-less the greatest part about using the SAT and/or QuadTree solutions is that they can be easily changed for 3D collision detection.
The nice thing about the SAT is you can have any shape you want, provided it is convex. If you need a concave polygon you can split them into two convex polygons.
However as I said before your biggest improvement in efficiency will be given by a better sorting algorithm. If you look at it a standard double loop will be O(n2) where as using a QuadTree will be O(logn) which is significantly more efficient; especially for larger samples such as in a particle collision. Granted you have to build the tree before you test it (once every frame?) it will still be O(n+logn) which will still be faster... much faster. The only problem with the QuadTree is sometimes you will get an object that gets stuck in the tree twice because it is on a boundry.
Never-the-less the greatest part about using the SAT and/or QuadTree solutions is that they can be easily changed for 3D collision detection.
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
