How to do collision detection between two lines?

Questions about the LÖVE API, installing LÖVE and other support related questions go here.
Forum rules
Before you make a thread asking for help, read this.
User avatar
togFox
Party member
Posts: 828
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

How to do collision detection between two lines?

Post 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?
Last project:
https://togfox.itch.io/hwarang
A card game that brings sword fighting to life.
Current project:
Turn-based PBEM horse stable (racing) management sim: https://togfox.itch.io/horse-stable-manager
https://discord.gg/HeHgwE5nsZ
User avatar
darkfrei
Party member
Posts: 1197
Joined: Sat Feb 08, 2020 11:09 pm

Re: How to do collision detection between two lines?

Post by darkfrei »

:awesome: in Lua we Löve
:awesome: Platformer Guide
:awesome: freebies
User avatar
ReFreezed
Party member
Posts: 612
Joined: Sun Oct 25, 2015 11:32 pm
Location: Sweden
Contact:

Re: How to do collision detection between two lines?

Post by ReFreezed »

Not to be rude, but this is an extremely googlable question.
https://stackoverflow.com/questions/383 ... -intersect
Tools: Hot Particles, LuaPreprocess, InputField, (more) Games: Momento Temporis
"If each mistake being made is a new one, then progress is being made."
User avatar
togFox
Party member
Posts: 828
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: How to do collision detection between two lines?

Post 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.
Last project:
https://togfox.itch.io/hwarang
A card game that brings sword fighting to life.
Current project:
Turn-based PBEM horse stable (racing) management sim: https://togfox.itch.io/horse-stable-manager
https://discord.gg/HeHgwE5nsZ
User avatar
togFox
Party member
Posts: 828
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: How to do collision detection between two lines?

Post 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.
Last project:
https://togfox.itch.io/hwarang
A card game that brings sword fighting to life.
Current project:
Turn-based PBEM horse stable (racing) management sim: https://togfox.itch.io/horse-stable-manager
https://discord.gg/HeHgwE5nsZ
User avatar
BrotSagtMist
Party member
Posts: 657
Joined: Fri Aug 06, 2021 10:30 pm

Re: How to do collision detection between two lines?

Post 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.
obey
User avatar
togFox
Party member
Posts: 828
Joined: Sat Jan 30, 2021 9:46 am
Location: Brisbane, Oztralia

Re: How to do collision detection between two lines?

Post 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.
Last project:
https://togfox.itch.io/hwarang
A card game that brings sword fighting to life.
Current project:
Turn-based PBEM horse stable (racing) management sim: https://togfox.itch.io/horse-stable-manager
https://discord.gg/HeHgwE5nsZ
User avatar
BrotSagtMist
Party member
Posts: 657
Joined: Fri Aug 06, 2021 10:30 pm

Re: How to do collision detection between two lines?

Post 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
obey
User avatar
pgimeno
Party member
Posts: 3655
Joined: Sun Oct 18, 2015 2:58 pm

Re: How to do collision detection between two lines?

Post 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/

Image
User avatar
Karai17
Party member
Posts: 930
Joined: Sun Sep 02, 2012 10:46 pm

Re: How to do collision detection between two lines?

Post by Karai17 »

STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+

Dev Blog | GitHub | excessive ❤ moé
Post Reply

Who is online

Users browsing this forum: Bing [Bot], Google [Bot] and 3 guests