Archived

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

Time-based logic / collision detection

This topic is 5521 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
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
First off, let me say again that I''m really no master at this stuff, so if there does turn out to be a flaw in any of this I''m really gonna feel silly Having said that, here we go...

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

Yeah, it is a nice idea to be sure And yes, actually I think there is an error in your example. We''ll take a look at that in a moment, but first let me clarify something. The examples I''ve given so far really only spells out one part of the problem, and that is how to get the info necessary to then performa calculation to find out if a collision occurred. Nothing more and nothing less.

To be clear, let me say that again. What I''ve shown so far only gives you the info you need to be able to check for collision. I have not shown the actual check for collision, just the gathering of information needed to be able to check for collision.

Now, as I vaguely alluded to in my first post, the reason I have not shown the actual collision check is because that method will differ depending on what method you''re using to check your collsion. You could, for example, be using a Point, an Axis-Aligned Bounding Box, an Oriented Bounding Box, a Bounding Circle/Sphere, etc. Each of these methods will require slightly different handling of the information we''ve collected.

Another thing that is VERY important to understand about performing collision detection over time is that it is NOT the same as performing an intersection test between the two objects. The reason for this is immediately obvious if you picture one object moving really fast while another one moves slowly, or stands still. If all you perform is an intersection test, then it''s entirely possible that one object will move right through another object without you catching that.

In other words, you could test on one frame and object A is to the left of object B. On the next frame object B might have moved through A and is now completely on the right side of A. In this case, if you only perform an intersection test then you will miss the collision. This problem can occurr whether you lock the frame-rate or not, which is why I suggest doing a real time-based check. Anything less would be prone to errors anyway, which means no advantage for locking the frame-rate.

Again, I apologize for the crudeness of my explanation, but while it''s a pretty simple concept for the most part, it''s hard to explain it really well without pictures or without getting too wordy.

So, before I begin to go over your example, let''s take a quick look at the full set of operations you need to do to actually perform collision detection over time if you''re using a Bounding Circle for your objects:


1. Get the elapse time
2. Get the position and velocity for each object
3. Compute the total velocity over time for each object
4. Pretend object "A" stands still and transfer velocity to "B"
5. Compute the new "pretend" position for "B"

RESULT: This is what I''ve shown in my examples so far. To actually find out if a collision occured we need to:


6. Create a ray from B''s initial position to B''s "pretend" position
7. Perform a ray-to-circle intersection test.

RESULT: This will tell you IF a collision occurred. It will NOT tell you when or where it happened...just that it did happen. Now, if a collision did occur then you must do some additional work to find out where and when it happened. How you go about figuring this out will depend on what you''re using(Circle, Box, etc), but for a circle, I *think* it goes something like this:


8. Get the normalized intersection point on the ray from Step7
9. Calculate the actual "World" position on the ray from that

RESULT: This will give you where the collision happened. To get the time of intersection you can:


10. Multiply the normalized intersection value with the elapsed time

RESULT: You now know if a collision occurred, and if it did, where and when it happened. From here you can stop your objects or use the remaining frame time to bump them off each other an appropriate amount


>>But assuming I did it right, there should be a collision at (6, 3.4)...But honestly, if I''m wrong, please let me know because this method seems absolutely too good to be true.<<

Whew! Well, it took me a lot longer to write the above then I would''ve figured, so I''m afraid I don''t have time right now to walk through your example step by step. However, I plotted it out and it looks to me like the problem is that they in fact do not collide.

When I drew out both objects actual path of movement, it looked like their paths did cross at (2.701, 4.719). BUT, by the time object B got to that point A was already long gone. So, I''m not exactly sure where your problem was occuring but hopefully my above explanation of all the steps will help you figure it out.

Well, it''s time for me to get some sleep. If I made some mistakes above or any of it doesn''t make sense let me know and I''ll try to elaborate/correct that. But I hope it all makes a little more sense now

-John

PS: If anyone has some space on the web where I could store something, I could try to draw up some pictures to better illustrate all this jazz

Share this post


Link to post
Share on other sites
D''oh! I think I just realized a small mistake in my last post. Before you perform the ray-circle intersection test in Step #7, you need to combine object B''s radius into object A''s for the check.

Basically, for almost any collision check what you want to do is transfer all the motion to one object and all the volume to the other object. All this trickery is to allow you to do a ray-volume intersection test, to figure out IF a collision occurred. The reason for this is that it is a lot easier and faster to do a simple ray-volume intersection test than it is to check two moving volumes over time.

In reality, you''re calculating the same thing. You''re just moving stuff around to make it easier to perform the check

-John

Share this post


Link to post
Share on other sites
quote:
Original post by Teknofreek
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?

You''re working with discrete integer values - which you''re unlikely to have in time-based movement and collision detection, and equal steps each frame, which you will almost certainly not get. I suggested a scenario where each object moves 10 units in one frame. Imagine that one object moves 10 units and the other moves 9.89 units, for example. How''re you gonna handle this with your method?

And more relevant, are ''ray-volume intersection tests'' really worth it for a 2D game? (I''m gonna keep banging this drum until people listen )


[ 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
>>You''re working with discrete integer values - which you''re unlikely to have in time-based movement and collision detection, and equal steps each frame, which you will almost certainly not get. I suggested a scenario where each object moves 10 units in one frame. Imagine that one object moves 10 units and the other moves 9.89 units, for example. How''re you gonna handle this with your method?<<

Check out my last two posts. None of the values have to be integers. Not the elapsed time, the positions, the velocities, the bounding circles....none of ''em. Just plug in whatever values you want and check it out.

>>And more relevant, are ''ray-volume intersection tests'' really worth it for a 2D game? (I''m gonna keep banging this drum until people listen )<<

Maybe. It all depends on whether you can run the risk of your objects moving too quickly through each other. If all your objects are moving slow, or are moving in ways in which they''d never move pass through another object over the course of a frame, then no, you don''t. However, if that possibility exists then using a ray-volume intersection will handle it quite nicely.

Another thing to note is that doing something like a ray-point, ray-circle, or ray-box intersection really isn''t that costly. It''s not that difficult to do either. Each of them only requires about a few steps which you should be able to copy verbatim from many a website or book.

So, I guess my point of view is that no, in some cases it''s not absolutely necessary. But since it''s really not all that hard to do and since it takes care of any frame-rate or speed anomolies you may run into, I don''t see much of a reason not to do it

-John

Share this post


Link to post
Share on other sites
I have to admit that I didn''t read all the previous posts therefore I might be off topic anyway .. what happens if you make your objects keep track of their previous positions aswell ? ...

then, imagine this :

dp1 = A.prevPosition dotproduct B.prevPosition
dp2 = A.curPosition dotproduct B.curPosition

if (sign(dp1) != sign(dp2)) boom

of course, you''ll have to add some more checks.


---
novocaine thru yer veinz

Share this post


Link to post
Share on other sites
>>if (sign(dp1) != sign(dp2)) boom<<

You could do that, but of course you would get the "boom" condition in all kinds of cases where the objects were never even near each other. I suppose that coupled with a bunch of other tests you probably could make this work though.

However, you still wouldn''t know where and when they collided unless you did the other stuff anyway. So, I dunno if it''d be worth it.

-John

Share this post


Link to post
Share on other sites
quote:
Original post by Kylotan
And more relevant, are ''ray-volume intersection tests'' really worth it for a 2D game? (I''m gonna keep banging this drum until people listen )



What else are you gonna do with all those extra cpu cycles that don''t have to push polys to your graphics card =)

Share this post


Link to post
Share on other sites
quote:
Original post by Teknofreek
Check out my last two posts. None of the values have to be integers. Not the elapsed time, the positions, the velocities, the bounding circles....none of ''em. Just plug in whatever values you want and check it out.

Well, to be honest I still don''t see how your method can account for all situations... you seem to be sampling Object A''s position at discrete points and this leaves the possibility of none of those points crossing Object B''s path, despite the paths having actually crossed at a stage that would have fallen between 2 of the samples.

Example (arrows are direction vector):

Frame 1

A->

^
|
B


Frame 2

^
|
B
A->


If you leave A still and compute B''s path, there''s no collision, as B''s path travels clear in front of A. If you leave B still and compute A''s path, there''s still no collision, as A''s path is clearly in front of B. Only by either plotting both paths and calculating the intersection time, can you be sure of knowing that these 2 objects crossed paths, somewhere between Frame 1 and Frame 2.



Oh, and sjelkjd: I''d use the cycles for AI


[ 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
>>If you leave A still and compute B''s path, there''s no collision, as B''s path travels clear in front of A. If you leave B still and compute A''s path, there''s still no collision, as A''s path is clearly in front of B. Only by either plotting both paths and calculating the intersection time, can you be sure of knowing that these 2 objects crossed paths, somewhere between Frame 1 and Frame 2.<<

Ahhh...ok, I think you''re missing the key point here. You don''t leave one still and plot only the path of the other. You leave one still and COMBINE the two paths onto the other one. So, if you leave A still, then you move B (Bpath - Apath).

It''s kind of like solving an algebra problem. Instead of solving for simultaneous things, you move all like things to one side of the equation. This doesn''t change anything, it just makes it easier to look at. So, instead of doing this:

5x + 5 = 2x + 1
3x = -4

We''re doing this:

A.position + (A.velocity * Time) COLLIDE_WITH B.position + (B.velocity * Time)
A.position + (A.velocity * Time) - (B.Velocity * Time) COLLIDE_WITH B.position

Same thing with the volumes. Instead of testing the collision of two volumes against the other, we combine them on one side.

So, basically, we''re changing a ray-ray intersection test to a ray-point intersection test. Or, if we take into account the volume of the object, which we probably should, we''re changing a swept-volume to swept-volume intersection test to a ray to volume intersection test.

We''re still taking into account all the factors at once, we''ve just transfered all the movement onto one object and all the volume onto the other object.

Does that make more sense now?

-John

Share this post


Link to post
Share on other sites