Assuming that I have a number of perfectly circular objects that can interact with each other and the terrain, what is the best system for accurately detecting collisions. Some objects might move so fast that they can cross paths and still not touch from frame to the next unless extra care is taken to be precise. Is the cpu cost of accuracy too expensive? If anyone has pseudocode or has experience with this please respond. My game is a platform game. thanks. -pTymN

If the system is closed (fixed number of objects and no external forces/interactions), maintain a list/array of times of projected collisions of all objects with all other objects and animate until then. At that point, recalculate the times of collision. You can limit the number of necessary recalculations by determining whether the new direction of the objects that have collided will intersect the path of other objects; if they don''t, those objects are essentially unaffected by the results of the collision.

That''s one way...

---

I wanna work for Microsoft!

I assume you''re working in 2D as you say your objects are circular. Are they under any sort of acceleration (i.e. gravity) or just moving linearly until collision?

If they''re all moving linearly, or all moving under constant acceleration then you can calculate the time it will take for two circles to intersect (providing you''re moving a fixed distance per frame or second):

x = object 1 position
v = object 1 velocity
y = object 2 position
u = object 2 velocity
r1 = object 1 radius
r2 = object 2 radius
t = time

((x + tv) - (y + tu)) * ((x + tv) - (y + tu)) == (r1 + r2) * (r1 + r2)

(x - y + t(u - v)) * (x - y + t(u - v)) == (r1 + r2) * (r1 + r2)

x² - 2xy + 2xt(u - v) + y² - 2yt(u - v) + t²(u - v)² - (r1 + r2)² == 0

t²(u - v)² + t(2x(u - v) - 2y(u - v)) + (x² + y² - 2xy - (r1 + r2)²) == 0

solve the quadratic to find t, and this is the time to the next collision. First run this for each object against each other object at the start of your code and store the resulting times with the objects. Now whenever you have a collision, do your collision repsonce and then run this code again for the objects that collided, against all other objects. Find the earliest collision between your just collided object and another object. If that time is less than the currently stored time in the second object, then update both of their times.

Note - every time a collision occurs you need to subtract the elapsed time since last collision from every objects stored time.

Sorry if this is really confusing, that''s the best I can think to word it.

(P.S. if you''re working in 3D I can just post some code to do it!)