Line-to-line collision detection

So I have some line segments, let’s say 15 to 20 of them for arguments’ sake. Those line segments are moving around the screen, and they are able to hit both each other and some other fixed line segments. I update the line segments’ positions with an enter-frame listener, and the line segments are all stored in an array. Each array component has the start point and end point of each line.
It’s not the collision detection, it’s the efficiency. I’m using a for loop on all of the dynamic line segments. I want to cut down how many checks I need for optimization. If I’m checking on 20 line segments and 30 fixed bodies, that’s already 49*20=980 checks. I want to find out if I can cut down on the number of checks I perform per frame. Is there any way to do this?

Are you using math based collision? I hope you are. 980 math checks isn’t all that much.

You could always check half one frame and the other half the next frame. But you’d be sacrificing some precision there. Depends how fast lines would be moving.

Finally, where does the 49 come from?

Originally posted by UnknownGuardian:

Are you using math based collision? I hope you are. 980 math checks isn’t all that much.

You could always check half one frame and the other half the next frame. But you’d be sacrificing some precision there. Depends how fast lines would be moving.

Finally, where does the 49 come from?

i think 49 is 1 line vs other 19 + 30 bodies.

Some kind of spatial partitioning would probably help.

A typical grid-based (4×4, 3×3 maybe? larger if there’s less movement) partition would probably work well. You could also try a Skip list or Quadtree but those seem like overkill for this.

Wouldn’t that totally be dependent on how long the lines were? If they are like 200+px long and at angles that might be next to useless…

Originally posted by truefire:

Some kind of spatial partitioning would probably help.

no, it wouldn’t. line segments are easily checked with some math; and the math is far faster than treating them like anything more than lines; they can check collisions with other lines very simply (point-intersection of two lines; if intersection is more than length away from origin, or negative, return false. else true; if intersection is NaN/Infinity return false) collision with the bounding rectangle of the other bodies is very simple and fast too (basically the same math), if the rectangle collision is true and the body is more complex than a rectangle, a more advanced heck may be needed, or perhaps a simpler one in the case of a circle (avoiding the rectangle test all together).

the number of checks per frame can be reduced by checking element 0 against elements 1 through length, then element 1 by elements 2 through length, etc. skipping the final element all together (since there’s nothing more for it to collide with and all other lines have tested against it). it requires either creating a new array that is a concatenation of the other arrays (fairly slow, but easy to implement) or a more permanent secondary array of elements checking against each other. if i recall, the number of checks is n((n-1)/2). or, in this case, 20*9.5+20*30; 790

if the first 30 elements in the hitTest array are the stationary elements, then you can iterate over it like this (checks performed externally to the objects):

for (var i = arr.length - 1; i > fixedElementCount; --i) {
    var el = arr[i];
    for (var j = i - 1; j > 0; --j) {
        checkCollision(el, arr[j]);
    }
}

Collision checks between 30 objects is nothing. That should go like lightning, and if it doesn’t there’s a problem with your detection code.

line segments are easily checked with some math; and the math is far faster than treating them like anything more than lines;

The collision is still done the same. The reason spatial partitioning would be beneficial is to reduce the number of collisions. Say we have 5000 lines cross-colliding (a lot, but still a possible number) That becomes 5000×4999/2 ~= 1.25m collisions. Even if they’re cheap, that’s going to eat some cycles. Now, say our spatial partitioning that reduces it to something functionally equivalent to ‘groups’ of 1000. 5000×1000/2 (we could probably do better). that’s only 250k collisions. 5 times as fast. The cost of maintaining 5000 lines is quite likely going to be smaller then the time you’re saving.

Indeed, it’s more valuable to partition with high numbers of objects when cross-coliding like this. (collision is O(n^2) while maintaining the partitions can be O(n)*)

I was just suggesting to try various partitioning methods to see if any were beneficial at your levels.

*Depending on how you maintain the partition and what type of partitioning you use