Problem with a collision that I can't find documents on...
Author
Okay, here''s the scenario.
The game world is tile-based, simple enough right?
The game objects are rotating ractangles (full 360 degree rotation). Now do you see the problem? I need to figure out how to check for collision between a moving rectangle (that has floatational positions) and the tile-based world. If anyone can help you would be helping a weeks worth of brainstorming.
I''m approaching a similar point in my game also. It''s a driving game where the car is a rectangular object, but the ground map is a complex mesh (mess?, no mesh!)
Your life will be a little easier in that the "tiled" world will only have square edges with which your object collides, agreed?
If a car is being driven in a straight line (backwards or forwards) then you only need to check the front or rear bumpers (or "fenders"?) for collisions. The main problem arises from the velocity of the car. To truely check for collisions you must calculate the next position of the car from vehicle movement routines, (which can be ANY distance travelled depending on velocity and frame-rate), then check every position that the whole bumper passes through to get from where it is to where it should be...
Now if it''s taken me that long to describe it (however badly) you can bet that it''s a million times worse to code efficiently.
But I intend to do this..
Firstly, instead of using the bumper as a line, break it up into four,five or x number of points - One at each end, and the rest equi-spaced between. If ANY of these points causes a collision in the next move, halve the distance travelled and try again. If the distance travelled is now less than an inch or two, use this as the distance to move the car and flag up the collision. If the distance was still more than a few inches, use 3/4 of the original distance and try again etc. etc.
Now I''m going to experiment with this idea a bit myself, if you''d like some more clarification - email me. I know there''s a lot of complex math available in order to do some of this (Runge-Kutta?) but they essentially get hacked down in this way in order to make them fast enough.
If your object is like a tank that can rotate about it''s own centre you''ll have to consider the four corners in a similar way. Also, if like me, you want your vehicle to slide, you''ll need to check the side of the car too...
This is all very painful! If anybody has any other ideas I''d like to hear them too.
Quick but shameless plug: www.btinternet.com/~Matthew.Bennett
If I were rich, I'd buy myself some real friends!
Your life will be a little easier in that the "tiled" world will only have square edges with which your object collides, agreed?
If a car is being driven in a straight line (backwards or forwards) then you only need to check the front or rear bumpers (or "fenders"?) for collisions. The main problem arises from the velocity of the car. To truely check for collisions you must calculate the next position of the car from vehicle movement routines, (which can be ANY distance travelled depending on velocity and frame-rate), then check every position that the whole bumper passes through to get from where it is to where it should be...
Now if it''s taken me that long to describe it (however badly) you can bet that it''s a million times worse to code efficiently.
But I intend to do this..
Firstly, instead of using the bumper as a line, break it up into four,five or x number of points - One at each end, and the rest equi-spaced between. If ANY of these points causes a collision in the next move, halve the distance travelled and try again. If the distance travelled is now less than an inch or two, use this as the distance to move the car and flag up the collision. If the distance was still more than a few inches, use 3/4 of the original distance and try again etc. etc.
Now I''m going to experiment with this idea a bit myself, if you''d like some more clarification - email me. I know there''s a lot of complex math available in order to do some of this (Runge-Kutta?) but they essentially get hacked down in this way in order to make them fast enough.
If your object is like a tank that can rotate about it''s own centre you''ll have to consider the four corners in a similar way. Also, if like me, you want your vehicle to slide, you''ll need to check the side of the car too...
This is all very painful! If anybody has any other ideas I''d like to hear them too.
Quick but shameless plug: www.btinternet.com/~Matthew.Bennett
If I were rich, I'd buy myself some real friends!
Hiya-
It seems that the problem you are describing is a recurring problem with many 2D games in general.
The problem seems to be one of 2D collision detection/reaction. I am specifically working on my
own implementation of "Pong" in order to develop my routines. This is what I''ve got done so far:
(1) Line-Segment/Line-Segment Intersection - Test if two segments intersect & where.
(2) Line-Segment/Polygon Intersection - Pretty much an extension of (1) above.
(3) "Point In Polygon" - Test if a given point is inside or outside of an artibrary polygon
(4) Polygon/Polygon distance - Determine the shortest distance between two polygons
(5) Shortest Distance from a point to a line segment
(6) Shortest distance between two lines segments
(7) Ray/Segment Reflection - Given ray R, velocity V and line segment S (where R intersects S within
a given time T), determine the reflection vector
In terms of, say, a car racing game, it''s easy to define a rectangular polygon for the car.
As the car turns, turn the polygon so that the polygon is a contour of your car graphic.
As the car moves, test for intersections with other object polygons or segments.
I wrote a test program to exercise most of these routines. It draws two different random polygons
(with buttons to randomly redfine them) and a ball (point (x,y) with a radius R and velocity vector (vx,vy).
The program will draw the ball as an "X" if it is outside either of the two random polygons and draws
the ball as an "O" if it is inside one of the polygons. Then I have two buttons: move ball (to move the
ball one step) and "run ball" to continuously move the ball. As the ball moves around, it checks each
polygon for a collision; if it hits, it determines the new velocity vector (as if bouncing off it) and
continues.
Obviously, I could have implemented pong with much simpler code. But the idea is to get a set of
portable routines for general 2D collision detection and reflection. After Pong, I plan on doing
a ''Break Out'' style game... Eventually I would like to build up to a ''Gauntlet'' style game (hint-hint).
Cheers!
// CHRIS
It seems that the problem you are describing is a recurring problem with many 2D games in general.
The problem seems to be one of 2D collision detection/reaction. I am specifically working on my
own implementation of "Pong" in order to develop my routines. This is what I''ve got done so far:
(1) Line-Segment/Line-Segment Intersection - Test if two segments intersect & where.
(2) Line-Segment/Polygon Intersection - Pretty much an extension of (1) above.
(3) "Point In Polygon" - Test if a given point is inside or outside of an artibrary polygon
(4) Polygon/Polygon distance - Determine the shortest distance between two polygons
(5) Shortest Distance from a point to a line segment
(6) Shortest distance between two lines segments
(7) Ray/Segment Reflection - Given ray R, velocity V and line segment S (where R intersects S within
a given time T), determine the reflection vector
In terms of, say, a car racing game, it''s easy to define a rectangular polygon for the car.
As the car turns, turn the polygon so that the polygon is a contour of your car graphic.
As the car moves, test for intersections with other object polygons or segments.
I wrote a test program to exercise most of these routines. It draws two different random polygons
(with buttons to randomly redfine them) and a ball (point (x,y) with a radius R and velocity vector (vx,vy).
The program will draw the ball as an "X" if it is outside either of the two random polygons and draws
the ball as an "O" if it is inside one of the polygons. Then I have two buttons: move ball (to move the
ball one step) and "run ball" to continuously move the ball. As the ball moves around, it checks each
polygon for a collision; if it hits, it determines the new velocity vector (as if bouncing off it) and
continues.
Obviously, I could have implemented pong with much simpler code. But the idea is to get a set of
portable routines for general 2D collision detection and reflection. After Pong, I plan on doing
a ''Break Out'' style game... Eventually I would like to build up to a ''Gauntlet'' style game (hint-hint).
Cheers!
// CHRIS
well, since this a tile based world, it shouldn''t be too hard 
lets say your rectangle is moving at x velocity xv and y velocity yv, towards a wall tile (or whatever), and the object is currently at x,y.
what to do is that since you know the edge of the wall is at x2,y2 (i hope, BTW these are the thresholds of the wall, if you get me) you semi-add (il explain that below) x and xv, y and yv, to see if they "go past" the wall threshold (x2, y2). if they do, just make the object (x,y) be at (x2-1,y2-1), and flag a collision. that way, the object would have gone past the wall, so instead just make it barely touch the edge and collide.
Above when i said semi-add, i meant you would do like
x + xv
and
y + yv
in you if statement, no
x += xv
or
y += yv
i hope this explanation was clear.
if not, just e-mail me
lets say your rectangle is moving at x velocity xv and y velocity yv, towards a wall tile (or whatever), and the object is currently at x,y.
what to do is that since you know the edge of the wall is at x2,y2 (i hope
, BTW these are the thresholds of the wall, if you get me) you semi-add (il explain that below) x and xv, y and yv, to see if they "go past" the wall threshold (x2, y2). if they do, just make the object (x,y) be at (x2-1,y2-1), and flag a collision. that way, the object would have gone past the wall, so instead just make it barely touch the edge and collide.Above when i said semi-add, i meant you would do like
x + xv
and
y + yv
in you if statement, no
x += xv
or
y += yv
i hope this explanation was clear.
if not, just e-mail me
Author
OH MY GOD! I''m so stupid, I forgot about how I was adding the xv and yv to x and y! Duh! Thanks you helped alot!
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement
