Jump to content
  • Advertisement

Archived

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

Kanzetsu

Time-based logic / collision detection

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

I'm currently making a small 2D arcade-style game (think Super Mario). I have to decide whether to use frames or real time as basis for ingame time ("object moves X pixels per frame" vs "object moves Y pixels per second"). Frames can be convenient, but I want to use vertical sync. This means that I can't choose my own fixed frame rate too easily, since refresh rates differs between systems. So, using the timer instead would be good. But I've got a problem with this: Let's say object A and B are moving towards eachother. During the next iteration of the game loop A moves a great distance because of a temporary freeze (e.g. some other process starts doing some demanding task), and B does the same in the opposite direction. They have now passed eachother and are not detected in a simple bounding-box collision detection. Worse, what if one of the objects decide that it wishes to stop moving and do something else during this period of time? How do I detect the collision that should have occured? One idea that appeared in my head while writing this is to split the time that has passed into 5 ms segments ("200 FPS precision"), do full "AI" logic/collision detect for each frame and save remaining time (< 5 ms) to be processed in the next iteration of the game loop. Does this seem like a good solution to you? Or is there some more correct, smarter, secret, evil, guarded-by-ninjas technique that I could find useful? Any suggestions or ideas on this matter are appreciated! [edited by - Kanzetsu on December 1, 2002 2:47:00 AM]

Share this post


Link to post
Share on other sites
Advertisement
First of all, I would say that it''s almost always a better idea to go for frame-rate independant time handling. You can never be sure how slow(or fast!) you''re game will run on the multitude of systems out there. Heck, even if the systems are all the same, your game will probably run at different speed depending on how much is going on on-screen at a given point in time. So yeah, I''d go with a time-based, rather than frame-based approach.

Now, as for collision detection, I''m by no means a grand master when it comes to it, but I think there''s one technique that can help you a lot here. You can solve across time. To make it easy to understand let''s look at a situation in 1 dimension:

Object "A" is at 0 and is traveling +5 over the time interval. Object "B" is at 10 and is traveling -7 over the time interval. Now, to solve for their collision, what you can do is pretend that one of them is standing still and that the other one is moving. You can do this by subtracting the velocity of one object from both of them. So, if you leave A at 0, you need to subtract 5 from B. This means that A is at 0, and B is moving from 10 to -2. If you calculate a vector from 10 to -2 you will get a collision for with the bounds of A.

Now, depending on what you use for collision detection(Bounding Boxes, Bounding Spheres, etc) there are different ways to figure out where they hit, when they hit, etc. But that''s the basic principal of it all.

Make sense?

-John

Share this post


Link to post
Share on other sites
quote:
Original post by Teknofreek
Now, to solve for their collision, what you can do is pretend that one of them is standing still and that the other one is moving.

But as you said, this only works in one dimension. Imagine 2 objects moving at equal speed, one starting from (0,0) moving (1,1) per second, and another object at (10,0) moving (-1,0) per second. If you check their positions after 10 seconds, they should have collided at (5,5), but your method will not spot that.

Personally, for a 2D game, I would just stick with a frame limiter. But if you''re determined to do it separately, you could try checking for collisions at a fixed frame rate and update graphics as often as possible.



[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
>>But as you said, this only works in one dimension.<<

No, I didn''t. I said I''d use a one dimensional example to make it easy to understand. The same concept works fine in 2D or 3D.

>>Imagine 2 objects moving at equal speed, one starting from (0,0) moving (1,1) per second, and another object at (10,0) moving (-1,0) per second. If you check their positions after 10 seconds, they should have collided at (5,5), but your method will not spot that.<<

Uhh, actually they wouldn''t collide. If the one starts at (0,0) and is moving (+1,+1) it will move diagonally. In your example, after 5 seconds, one will be at (5,5) and the other will be at (5,0)...which is not a collision unless your objects are big enough to cover the 5 unit distance apart.

Really, the way I explained is only one way to do it. But it does have the upside that it''ll be accurate regardless of your time step, as long as your objects are moving in a linear path between each time step. It also has the upside of being a method that can scale to 3D. So, if you get it all working in 2D then you''ll have a technique you can carry over to 3D

-John

Share this post


Link to post
Share on other sites
quote:
Original post by Teknofreek
No, I didn''t. I said I''d use a one dimensional example to make it easy to understand. The same concept works fine in 2D or 3D.

But it''s harder to give a simple 2D example, which is probably why you didn''t do so

quote:
Uhh, actually they wouldn''t collide.

You''re an intelligent guy (I assume), and should be able to guess that I made a mistake in my example I meant that the one at (10, 0) is moving (-1, 1). How would you account for that? Pretending that one is standing still and the other is moving, no matter which one you choose, will not yield a collision.

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
>>But it''s harder to give a simple 2D example, which is probably why you didn''t do so<<

Sure. But it''s not that much harder. It''s just easier to "get it" with something super-simple, like a 1D example

>>You''re an intelligent guy (I assume), and should be able to guess that I made a mistake in my example<<\

Hehe, yeah, I figured that. Looking back, unfortunately, I think my reply came off more in a patronizing tone then the whimsical one I was going for Ahh, sometimes it''s hard to expression motion over the net

>>I meant that the one at (10, 0) is moving (-1, 1). How would you account for that? Pretending that one is standing still and the other is moving, no matter which one you choose, will not yield a collision.<<

LOL! I think you made a mistake again

Anyway, the key here is that you only pretend it''s not moving for the sake of collision. It''s position does get updated appropriately if they don''t collide. So, here goes a 2D example:

Object "A" starts at ( 0, 0 ) and is moving ( +1, +1 )
Object "B" starts at ( 5, 5 ) and is moving ( -1, -1 )

Frame 1:
CHECK: Pretend "A" stays at ( 0, 0 ) and "B" moves from ( 5, 5 ) to ( 3, 3 )
RESULT: No Collision
DO: Move "A" to ( 1, 1 ). Move "B" to ( 4, 4 )

Frame 2:
CHECK: Pretend "A" stays at ( 1, 1 ) and "B" moves from ( 4, 4 ) to ( 2, 2 )
RESULT: No Collision
DO: Move "A" to ( 2, 2 ). Move "B" to ( 3, 3 )

Frame 3:
CHECK: Pretend "A" stays at ( 2, 2 ) and "B" moves from ( 3, 3 ) to ( 1, 1 )
RESULT: Collision!!

Now, to handle that collision you can do check to see the speed of each object as well as how far apart they are before that movement to determine where exactly they will collide.

You could also do each check while taking into account the object''s size, using a bounding circle since we''re in 2D. To do so, you use the same type of trickery. You combine the objects size and "pretend" that one is a dot of zero size.

In fact, most of the collision/culling/intersection routines work like this. Basically, it''s a lot easier to test a point or ray against a stationary volume of some sort than it is to test two moving volumes. So, as long as you can live with the objects only moving in a linear direction between each time sample, you''re cool.

Does that make sense?

-John

Share this post


Link to post
Share on other sites
No, it doesn''t make sense, and you''re still working in just 1 dimension, it''s just that it''s rotated through 45 degrees. My example shows one object going up and to the right, and another going up and to the left, and their paths cross in the middle.

If, in Frame 1, object A is at (0,0) and object B is at (10,0), and in Frame 2, object A is at (10,10) and object B is at (0, 10), both velocities were constant, and both objects travelled in a straight line and have a non-zero size, they would have collided at (5,5). Right? My basic approach at calculating this would be to draw the 2 vectors, see where they intersect, use interpolation to guess the time at which a collision would have to occur, and test it at that point... but even that is error-prone since one object could have arrived just before the other but a collision would still have occured due to its size... and so on. And when you want to get down to irregularly-shaped objects and pixel-perfect collisions, it gets harder still.

This is the problem with time-based movement - solving this sort of problem is not impossible, but it''s a damn sight harder than simply fixing your frame rate! It makes sense for 3D games where you''re going to have to do a lot of the mathematics anyway, but for a 2D platform game it''s not worth it, is it?

[ MSVC Fixes | STL | SDL | Game AI | Sockets | C++ Faq Lite | Boost | Asking Questions | Organising code files | My stuff ]

Share this post


Link to post
Share on other sites
>> No, it doesn''t make sense, and you''re still working in just 1 dimension, it''s just that it''s rotated through 45 degrees.<<

Ok, fair enough, I guess. But again, that was just for ease of illustration. They are actually moveing in 2D. It just so happens that they were moving in vectors that lie along a single line. However, that''s not required, and the algorithm should work the same regardless of which direction they''re moving.

>>My example shows one object going up and to the right, and another going up and to the left, and their paths cross in the middle.<<

Sorry that I seem to be illustrating this badly. Ok, let''s try your example out:

Object "A" starts at ( 0, 0 ) and is moving ( +1, +1 )
Object "B" starts at ( 10, 0 ) and is moving ( -1, +1 )

Frame 1:
CHECK: Pretend "A" stays at ( 0, 0 ) and "B" moves from ( 10, 0 ) to ( 8, 0 )
RESULT: No Collision
DO: Move "A" to ( 1, 1 ). Move "B" to ( 9, 1 )

Frame 2:
CHECK: Pretend "A" stays at ( 1, 1 ) and "B" moves from ( 9, 1 ) to ( 7, 1 )
RESULT: No Collision
DO: Move "A" to ( 2, 2 ). Move "B" to ( 8, 2 )

Frame 3:
CHECK: Pretend "A" stays at ( 2, 2 ) and "B" moves from ( 8, 2 ) to ( 6, 2 )
RESULT: No Collision
DO: Move "A" to ( 3, 3 ). Move "B" to ( 7, 3 )

Frame 4:
CHECK: Pretend "A" stays at ( 3, 3 ) and "B" moves from ( 7, 3 ) to ( 5, 3 )
RESULT: No Collision
DO: Move "A" to ( 4, 4 ). Move "B" to ( 6, 4 )

Frame 5:
CHECK: Pretend "A" stays at ( 4, 4 ) and "B" moves from ( 6, 4 ) to ( 4, 4 )
RESULT: Collision!!

That''s it. Same thing. It''s really pretty easy. Remember, to do the check you:

1. Pretend to leave A at it''s current position
2. Pretend that B moves from: ( B.position ) to ( B.position + (B.velocity - A.Velocity) )

Does that make sense now?

-John

Share this post


Link to post
Share on other sites
Okay, this is a stretch, and I'm sure I screwed up somewhere, but I think this disproves the validity of this method (which really sucks because I was hoping it would work). Ap is A's initial position, Bp is B's initial position, Av is A's velocity, Bv is B's velocity:

Ap = (1.27, 3.5)
Av = (2.5, 2.13)

Bp = (8, 2.6)
Bv = (-2, 0.8)

time between frame1 and frame2 = 3.43 seconds

Av is then (8.575, 7.31)
Bv is then (-6.86, 2.744)

A stays at Ap, B moves to (Bp + (Bv - Av))

so Bp = (8 + (-6.86 - 8.575), 2.6 + (2.744 - 7.31))
Bp = (-7.435, -1.966)

No collision.

But assuming I did it right, there should be a collision at (6, 3.4) (and both move well beyond that point in 3.43 seconds). I don't know if the problem is the use of floating point numbers, or what (and I really like to know where the screw up was), but if it's right, the method doesn't work in general.

But honestly, if I'm wrong, please let me know because this method seems absolutely too good to be true.

EDIT - wrong y-coordinate for the collision...
EDIT - and this only holds true for time-based rather than frame-based (otherwise the method should work since the 'time' is always 1 unit between frames)

[edited by - Chozo on December 4, 2002 2:19:10 AM]

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!