I have a fairly simple game I need to do collision detection for. The only objects that can collide are bullets with ships. Bullets are treated as points (no radius), and ships are treated as circles (point and radius). There are, however, several catches that make it more difficult: - Both ships and bullets can be travelling at arbitary speeds - The arena is wrapped at both edges - eg, going off the left brings you in on the right, going off the top brings you in at the bottom, and vice-versa. - I need to check for collisions that occur between time steps. It's not sufficient to check if a ship and bullet are colliding after a step is completed, as otherwise a ship/bullet travelling sufficiently fast could pass straight through each other. I'm aware that the general way to check for collisions between time steps would be to generate line segments for bullets and ships representing the distance they covered during the time step, then check for collisions. How do I do this when the bullet and ship can pass over a wrap-around boundary, possibly more than once(!) in a time step? And how do I narrow things down so I'm not checking every bullet against every ship every turn?

A while back this problem was discussed in a thread in this forum, and a nice solution was presented, along with some diagrams and pseudocode. I'll see if I can dig it up sometime today (it's been a while, so it may be a bit hard to find).

Ha, that was easy - it was the first hit on google. Here is the thread.

The thread topic is finding the shortest distance between two points in a wrap-around 2D environment, but the concepts apply to your problem as well.

First of all, you'll want two segment-vs-circle intersection functions: a cheap boolean test (a simple point-segment distance query) and a quadratic 'time of intersection' test.

When a projectile wraps within a timestep, you'll actually intersect multiple copies of it with the objects in the world; you can use the efficient static test to find if there is an intersection, and then use the continuous test to find the time of intersection.

The diagrams in the thread I linked to should give you some idea of how to construct the copies of the projectile segments. Post back if you get stuck on anything though.

I've actually already got point and vector classes that do pretty much exactly what's described there. I can call point1.VectorTo(point2) and get back a radius and angle. What I'm still vague on is how to handle determining if a particular bullet and ship collided between steps (why point/segment intersection? Shouldn't it be capsule/line intersection?), and how to create the multiple copies for wrapping - particularly if _both_ objects need wrapping.

I'm also wanting to try and find an indexing structure of some sort that will mean I don't have to test every single bullet against every single ship every turn.

Quote:Original post by Osmirik
I've actually already got point and vector classes that do pretty much exactly what's described there. I can call point1.VectorTo(point2) and get back a radius and angle. What I'm still vague on is how to handle determining if a particular bullet and ship collided between steps (why point/segment intersection? Shouldn't it be capsule/line intersection?), and how to create the multiple copies for wrapping - particularly if _both_ objects need wrapping.

I'm also wanting to try and find an indexing structure of some sort that will mean I don't have to test every single bullet against every single ship every turn.

A continuous test between two moving objects can be expressed as if one were non-moving, by subtracting the velocity of one of the objects from the velocities of both (resulting in a velocity of 0 for one of the objects). In this way, a moving point vs. moving circle test can be reduced to a static line segment vs. circle test. Expressing the problem as a capsule-line test, while intuitive, doesn't work, as it has no notion of time of intersection.

One other idea I'll throw out is that if the speed of the projectiles is high compared to the speed of the ships, you could treat the ships as non-moving for the purpose of intersection with the projectiles. This is how it's done in many games, and the inaccuracy is seldom noticable. And as long as you represent the motion of the projectile as a line segment, you won't have problems with tunneling.

As for the wrapping part, I'd have to sit down and work through it to give you a precise answer, but I think the diagrams in the thread I linked to express the general idea fairly clearly. If you're still stuck on this part though I might be able to draw up a quick diagram showing what I mean in more detail.

Quote:A continuous test between two moving objects can be expressed as if one were non-moving, by subtracting the velocity of one of the objects from the velocities of both (resulting in a velocity of 0 for one of the objects).

Good point. Essentially, do the test from the POV of the ship, or the bullet.

Quote:In this way, a moving point vs. moving circle test can be reduced to a static line segment vs. circle test. Expressing the problem as a capsule-line test, while intuitive, doesn't work, as it has no notion of time of intersection.

This occurred to me just after I finished posting. :/

Quote:One other idea I'll throw out is that if the speed of the projectiles is high compared to the speed of the ships, you could treat the ships as non-moving for the purpose of intersection with the projectiles. This is how it's done in many games, and the inaccuracy is seldom noticable. And as long as you represent the motion of the projectile as a line segment, you won't have problems with tunneling.

Unfortunately, since ships can travel at arbitary speeds, and the bullets they emit have their velocity plus something, any combination of ship and bullet velocities is possible.

Quote:As for the wrapping part, I'd have to sit down and work through it to give you a precise answer, but I think the diagrams in the thread I linked to express the general idea fairly clearly. If you're still stuck on this part though I might be able to draw up a quick diagram showing what I mean in more detail.

I think I have the general idea. After expressing the line segment of the bullet from the POV of the ship, take the segment from the beginning to the first time it intersects the border, and test that. If that fails, take the next bit, from that intersection to the next, and try again. Repeat until you run out of line segment or discover an intersection.

Thanks for all your help.