Jump to content
  • Advertisement

Archived

This topic is now archived and is closed to further replies.

-Fruz-

2d polygon collision detection, and reaction

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

hmm. being fairly new to the more complex aspects of game programming, i was not able to think of any decent way of doing this. i have one idea, but. i would like to hear an experienced pov. about this. what i thought, was to just keep a list of all the lines in every polygon, and constantly check if the movement line, interfere with the line of the polygon. hmm. but how to determin what side of the polygon you are in (to not end up inside it), i havnt manage to think of. atleest not any decent/safe way. please give me some pointers, thanx. JFK

Share this post


Link to post
Share on other sites
Advertisement
H Fruz. Not quite sure what you mean here, but I can offer you this:

struct vector{
float x, y;
};

bool PointInTri( vector A, vector B, vector C, vector Point )
{
vector AB;// = B-A;

vector BC;// = C-B;


AB.x = B.x - A.x;
AB.y = B.y - A.y;
BC.x = C.x - B.x;
BC.y = C.y - B.y;

if( AB.x * BC.y - AB.y * BC.x < 0 )
{
if( AB.x * ( Point.y - A.y ) >= AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) >= BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) >= ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
else
{
if( AB.x * ( Point.y - A.y ) < AB.y * ( Point.x - A.x ) ) return( 0 );
if( BC.x * ( Point.y - B.y ) < BC.y * ( Point.x - B.x ) ) return( 0 );
if( ( A.x - C.x ) * ( Point.y - C.y ) < ( A.y - C.y ) * ( Point.x - C.x ) ) return( 0 );
}
return( 1 );
}


It is a peice of code that I origonaly picked up from somones post in the Maths and Pysics forum, the addapted for my own use. It returns whether or not the point passed into the function is inside the triangle, which is good when dealing with 2D polygons. Not quite sure if this is any help or not.
Completly off-topic, I was wondering how that line-of-sight thing with DDraw went?(a little while ago now)

Share this post


Link to post
Share on other sites
thanx. although not exactly what i needed. but that''s ok, i think i have found a decent way that checks wheter or not i am inside a polygon, by using angles etc.

ah, yes, the los-thing. actually i have just experienced with it a little. not included it into the game. you could say it got put on hold (as projects often do), but i have picked it up recently and i''m working on it on a daily basis.
the question posted here is actually about the game. i decided to do a polygon based map system, instead of tiles. atleast experience with it and see how it looks. everything to get the best results

JFK

Share this post


Link to post
Share on other sites
If you are doing polygons then I ceratinly hope you have switched to D3D for you game (you do intend to draw these polygons to the screen, as opposed to just using them for collision?).

Share this post


Link to post
Share on other sites
as for the moment, no. no d3d. the polygons are easily drawn with DD. the only problem(?) is that i cant find a decent way to fill them. the one way i know is by using windows built in functions, allthough what i would really want are textured poligons. so that would require the impletation of d3d.

Share this post


Link to post
Share on other sites
this is what i did for Street Cars (see the thread about it):

(I only used recangles should work with any shape).

PointInPoly func: use the dotproduct of the normal of each side and a vector from the side to the point to determine if the point is inside the poly.

PolyToPoly collision: check each poly''s points against the other polys.

To resolve the collision: find the deepest penetrating point. Compute a resolve vector that will displace the polys to a non-penetrating distance. From this make 2 vectors, taking into account the objects'' masses, which will displace the polys. Add the two vectors to each poly''s Center of Mass.

I also used Chris Hecker''s paper for computing speeds after the collision.

Also you could use circles: fill the poly with circles (do this manually, or use an algorithm - very hard). The circle to circle collision test is quite simple and so is finding the resolve vectors.



[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/

Share this post


Link to post
Share on other sites
quote:
Original post by Ilici
PolyToPoly collision: check each poly''s points against the other polys.


I''m trying to do poly-poly collisions as well, so i''m interested in knowing how you did this. But if you''ve checking points of one against the poly of the other (and vice versa), what about this situation?:


+----+
| |
+------------+
| | | |
+------------+
| |
+----+

Share this post


Link to post
Share on other sites
That will never happen given that the timestep does not exceed some limit. And if it does you can do multiple loops over the collision detection in one frame.



[ My Site ]
''I wish life was not so short,'' he thought. ''Languages take such a time, and so do all the things one wants to know about.'' - J.R.R Tolkien
/*ilici*/

Share this post


Link to post
Share on other sites
Yes, that was what someone else pointed out to me, assuming the timesteps are small enough you''ll detect the initial entry before this odd case.

However it raises the question - whats ''small enough''. If you get very thin rectangles, or very fast moving ones, you can still end up with this situation.

Just a trade off for speed over accuracy I guess. I''m going to try this method first and see if its good enough. If so then no need to spend time doing something more complex

Share this post


Link to post
Share on other sites
Lemme ask a question: Are all of your bounding rectangles parallel to the x or y axis? If so, there is an easy 2D collision algo I''ve got for you

Share this post


Link to post
Share on other sites

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!