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

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

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

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

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

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