[.net] collision detection for 2D game in C#

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.

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 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

This is a snippet from SDL.NET which checks for collisions between sprites using a circle collision check:

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.

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.

Separation of Axis Theorem, what Krisc said, is in my first link btw, so you know. :)

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.

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(n²) 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.

Thanks for the ideas.
well, i know its very expensive to do the pixel perfect collision detection, that's why i use the rectangles bound checking first(Rectangle.IntersectWith). but once i detected intersection between 2 rectangles, how do i do the pixel checking? i know the theory of comparing colors, but could someone pls show me or direct me to some code samples?
Thanks in advance.

Depends on your rendering API. Is it GDI+, DX or OGL? How are you drawing the sprites?

I'm using DX to render sprites. my sprites were created by using VertexBuffer to form a rectangle, then filled it with texture.
here is my rendering code:
Game.graphicsDevice.SetTexture (0, spriteImage);
Game.graphicsDevice.SetStreamSource(0, vertBuffer, 0);
Game.graphicsDevice.DrawPrimitives(PrimitiveType.TriangleStrip,0,2);

The "obvious" and simple solution is to actually read pixels and compare them, but that requires locking surfaces (or keeping duplicate surfaces in system RAM) which is not efficient.

I would think z-buffer tests / occlusion queries (mentioned in the thread above) might be the best way, but it's more complicated. Sorry, no code - haven't implemented it myself, I like lines better than pixels.

I strongly advise against per-pixel as it becomes O(n²) just to read through one of the object's pixels.