How to do collision detection between two lines?

[togFox]

I'm thinking about writing a turn based battle ship game where you lob high-calibre shells at ships at sea.

At a wire-frame level, battleships are reduced to a thin line with two end points drawn in a 2d plane. They shoot at each other with shells - which are just small points in space.

What math is needed to detect collisions between shells and ships - or when a small dot travels through a line?

Or when two battleships/lines ram each other?

The game will draw nice battleship images with animation etc, but I want the collision detection to be more than a small box hitting a large box. The ships are long and skinny and not round and symmetrical so I feel the 'clipping' of a hit-box would give an awful experience and not realistic.

Hopefully this won't be too hard?

[darkfrei]

Like this?
https://love2d.org/forums/viewtopic.php ... 39#p236939

[ReFreezed]

Not to be rude, but this is an extremely googlable question.
https://stackoverflow.com/questions/383 ... -intersect

[togFox]

Reading that stack overflow post - would that work for a single point like a bullet? Would I use the same formula but make the segment really short?

And if the segment is so short (a 2 pixel bullet), would it not pass over the other line in any given dt and not actually intersect?

I think that formula answers the 'two ships colliding' question. For the bullet/shell - maybe some 'look ahead' technique that constructs a segment from its current position to its future position will create a segment long enough to perform collision detection without 'skipping over' the target.

I'll look at darkfrei example for inspiration.

[togFox]

I believe what I'm describing is the "Bullet through Paper" problem: if you have a very fast moving object move through a very thin object with a large enough time step, you won't detect the collision.

I've now got a name for my problem so I can research this further.

[BrotSagtMist]

Its a non problem really.
Taking the position from the old frame and the position of the new frame will create a sufficient line for bullets to never pass through anything.
Create the line formula out of this> the m*x+b form.
Find the intersection with all edges (create their line form before that in one step). From the intersection point you only need to check if its X value is between the X values of either of the two points used to create on of the lines, if yes you got a hit.
Edit: Actually the bullets movement can already be saved as line form. Meaning to hit a target you only need to check for intersections once, then place the bullet on that line using a timer. If the position crosses a certain X it hits.
That wont allow evades tho.

[togFox]

Yes. I'll take time step 0 + time step 1 to create segments then check for intercepts.

I can also use the love2d physics engine (which I'm experienced with) with bodies that are very small circles (bullets) and rectangles that are long but not wide. There won't be a lot of bodies at any given time so this might be easier to let the engine manage collision detection.

[BrotSagtMist]

What? wait no, why segments now? There are segments already, its your very movement between frames.

From what ive experienced is that its easier to write yourself than using the overly complicated physics engine.
I am too sleepy still to grasp what exactly my code does here and explain it proper, but it looks like this:

Code: Select all

addEdge=function(tab)	
 tab.m=(tab[2]-tab[4])/(tab[1]-tab[3])
 tab.b=(tab[2]-tab.m*tab[1])  
 tab.f=function(x) return tab.m*x+tab.b end
 --[[if not (math.abs(tab.m)==math.huge) then --ignore these for it is used for extreme lines only.
  tab.f=function(x) return tab.m*x+tab.b end
 else
  tab.f=function(x) return tab[1]>x and math.huge or -math.huge end
 end]]
end

This creates the line function out of a two points stored as {x,y,x2,y2}
next resolving the function for booth lines with two points to be known on one of these lines yields a hit or miss:

Code: Select all

(l1.f(x)<l2.f(x)) ~= (l1.f(x2)<l2.f(x2))

This l1.f(x)<l2.f(x) checks if the point at value x on l1 is below the value on the line l2, we check two x values and if the result is different, hence ~=, it shows that there was an intersection between x and x2.

In your scenario that would be:
l1={shipfrontx,shipfronty,backx,backy}
l2={bulletx,bullety,bulletxlaestframe,bulletylastframe}
run addEdge on booth, run combare with bulletx and bulletxlastframe

[pgimeno]

To solve the bullet through paper problem in 2D, you need to determine whether two segments intersect. One segment is the ship, the other segment is the one between the previous position and the current position of the bullet. That's why ReFreezed suggested that.

When googling for 'check if two segments intersect', there are some solutions and not all of them are good. Make sure you find a solution that accounts for the case where the segments are collinear. This one, for example: https://www.geeksforgeeks.org/check-if- ... intersect/

[Karai17]

https://github.com/excessive/cpml/blob/ ... #L254-L343