Page 1 of 2
How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 12:15 pm
by 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?
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 12:47 pm
by darkfrei
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 4:16 pm
by ReFreezed
Not to be rude, but this is an extremely googlable question.
https://stackoverflow.com/questions/383 ... -intersect
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 4:54 pm
by 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.
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 5:07 pm
by 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.
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 5:09 pm
by 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.
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 5:18 pm
by 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.
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 6:00 pm
by 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
Re: How to do collision detection between two lines?
Posted: Thu Feb 03, 2022 9:35 pm
by 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/
Re: How to do collision detection between two lines?
Posted: Fri Feb 11, 2022 6:58 pm
by Karai17