[Ghoser777]

So, I had put together a little demo with pretty basic hit detection and conservation of momentum/energy properties (pretty cool). The only thing that's holding me up is that some times if one object is moving just fast enough, it can technically jump right through another object (there are other similar situations - all have a central commonality though).

I'm using the Shape class and an Area wrapper and comparing the two to see if the intersection is empty to check for a hit. The problem is that I don't want to check if the new areas intersect by themselves (this works most of the time). Instead, I want the areas to be considered the whole region that the shape would pass over if movements were truly continuous. A really simple way for me to think of that in my head is to make a map from each point on the original shape in it's original location to it's corresponding point on the shape in the new location - that would give me the region to check for intersection (with the small possibility of having some intersections that shouldn't have really happened).

So the question is... how could I do that? Or is there a better way to do hit detection that I haven't thought of? I would like it to be general enough (not just rectangle intersections - that's too easy).

Thanks, and I hope this makes sense,
Matt Fahrenbacher

[absmiths]

It sounds like the problem is the granularity of your timer. If, in one tick, an object moves 10 pixels it might be tough to determine all the collisions which might have happened along the way. Instead, move the precision of your timer to tick once every pixel move and check for collisions there. Even if you only draw a frame every ten ticks, that will allow you to detect the collision. The upside is that most areas of animation become easier that way; the downside is that your routines must be much more highly optimized or else the increased hit detection can cause a drag.

I did something similar when doing some animation a while back. I made all of my objects (Actors) listeners to the clock and each tick they would calculate their position and check for collisions (the actors which cared about that sort of thing). A small optimization is to make sure to only check each collision once, E.G., if a >> e fails, don't check e >> a. You might also choose to ignore actors which do not move, and only do your checks using actors who have moved. This doesn't sound like much, but it will save you time comparing two actors who have both not moved. One more thing which just occurred to me is to divide the scene up into quadrants (or whatever) and only check collisions between actors in the same quadrant. An actor could of course be in multiple quadrants at once, but that could dramatically decrease the number of hit detections required. As an example, consider 16 actors on a canvas, with 4 each in each of the four quadrants. Normal hit detection could check 135 collisions (16 + 15 + 14 + 13 + 12 + ... + 2). If just each quadrant is checked, that results in 36 checks (4 * (4 + 3 + 2)). (This is just off the top of my head, and may not be useful at all . . .)

There was another listener to the clock which redrew the canvas when it was necessary. E.G., if no actors change, don't update the canvas (no need to redraw the same scene).

If you decide to interpolate actions between ticks (because an object just moves too darn fast) then you will get into all sorts of complexity (such as determining a collision between A and B over a time period involves knowing the exact behavior of each actor over that span, I.E., no single actor can determine that - it requires intimate knowledge of both). You will probably end up doing the above thing anyway - checking each step along the way for a collision - so the above method seems more general-purpose.

[Ghoser777]

GENIUS! Total duh on the updating the position more often than I draw. I still have small problems, but I'm guessing they are problems in Java's Area class and it's intersection/isEmpty method. Otherwise, it's working so much better now!

Thanks,
Matt Fahrenbacher

[11011001]

Keep track of the current and previous position of the object, define a rectangle with it's top at the current position and bottom at the previous position. Then check for intersection using this rectangle, and the shape at the current position.

edit: crap.. that's what you said.. sorry

but, why won't this work? in this case you are checking the intersection of the objects inscribed path between two points in time rather than it's intersection at any given moment, it seems that it would work to me.

[arekkusu]

11011001, because it assumes your objects are moving in straight lines. Two objects could be moving along curves, so the rectangle of intersection might indicate they collide when in fact they don't.

As absmiths says, you still have problems if one object is moving 1000 px per tick and another is moving 0.001 px per tick. You do not want to do 1000+ collision detections per object per frame in any sort of real-time simulation.

[11011001]

Originally posted by arekkusu:
11011001, because it assumes your objects are moving in straight lines. Two objects could be moving along curves, so the rectangle of intersection might indicate they collide when in fact they don't.

As absmiths says, you still have problems if one object is moving 1000 px per tick and another is moving 0.001 px per tick. You do not want to do 1000+ collision detections per object per frame in any sort of real-time simulation.

Well, then if they are moving along curves, then one should be able to generate an equation that will give one a nice curve. (or at least interpolate an equation)

It doesn't have to be a perfectly smooth curve either. The distance between the last and current position could determine the number of line segments necessary. Then just replace the line segments with rectangles. But a better solution would be to use polygons.

[absmiths]

Originally posted by 11011001:
Well, then if they are moving along curves, then one should be able to generate an equation that will give one a nice curve. (or at least interpolate an equation)

It doesn't have to be a perfectly smooth curve either. The distance between the last and current position could determine the number of line segments necessary. Then just replace the line segments with rectangles. But a better solution would be to use polygons.

The real issue is going to be not the path that each object travels but rather if the objects would intersect at any point in time. You could determine a path that had two objects colliding many times when no collision had actually taken place. Polygon hit detection can be very expensive - the more complex the area to detect the longer it will take. Approximating rectangles would probably be the fastest - even if you sacrifice a little accuracy.

Often a little brute force checking can be more efficient than complex algebra - there is a limit though.

[11011001]

Originally posted by absmiths:
The real issue is going to be not the path that each object travels but rather if the objects would intersect at any point in time. You could determine a path that had two objects colliding many times when no collision had actually taken place. Polygon hit detection can be very expensive - the more complex the area to detect the longer it will take. Approximating rectangles would probably be the fastest - even if you sacrifice a little accuracy.

Often a little brute force checking can be more efficient than complex algebra - there is a limit though.

Ah ha!!! It finally clicked.. thanks.

Hmm, another idea then

Let's just assume we have a time based function that returns the position of an object at the given point in time.

We we use rectangles to approximate the travel area. So a path becomes an indexed list of rectangles.

If there is an intersection between two paths, that is an intersection between list1 and list2, then we get the index of the colliding rectangles in each list, i1, and i2.

The end of each rectangle is going to be a certain distance from the origin of the intersection area, and is going to have an index. We normalize this index, and we get:
n1 = (i1 + 1) / list1.size()
n2 = (i2 + 1) / list2.size()

We define a range for an index as (i) to (i + 1).

So, if the ranges of i1 and i2 overlap then the two objects intersect.

It's a bit complicated, but it's very similar to over sampling, but with this method I think one can save a bit on calculations because we have lower sampling for slower moving objects, and higher sampling for fast moving objects.