Archived

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

-Fruz-

2d polygon collision detection, and reaction

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
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
hm, i just check x-y cordinates if they are inside a polygon. or actually the x-y of a player + the deltas. like X + dx, y + dy, and check if the result cords is inside the polygon. that lets me figure out if i am going to crash before i actually modify the real cordinates. this is a simple workaround for "look, i went inside the wall". *caugh* bad example. but. you see the point. i guess it''s nothing special.

Share this post


Link to post
Share on other sites
Hmm.. small enough means that an object wont go more than a few screen units in one timestep.

If you have really thin rectangels just pretend it''s a line with some width.

[ 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
If you are primarly using textured polygons, then go with Direct3d or OpenGL. Though if you are using mainly bitmap graphics with some textured map things, then DirectDraw is fine. I would suggest that you finish a texture-mapped polygon renderer just so you can see for yourself whether you want to do it or not. I''ve had some decent results from mine.

Share this post


Link to post
Share on other sites