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?
How to do collision detection between two lines?
Forum rules
Before you make a thread asking for help, read this.
Before you make a thread asking for help, read this.
How to do collision detection between two lines?
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
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
Re: How to do collision detection between two lines?
Not to be rude, but this is an extremely googlable question.
https://stackoverflow.com/questions/383 ... -intersect
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."
"If each mistake being made is a new one, then progress is being made."
Re: How to do collision detection between two lines?
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.
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
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
Re: How to do collision detection between two lines?
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.
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
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
- BrotSagtMist
- Party member
- Posts: 657
- Joined: Fri Aug 06, 2021 10:30 pm
Re: How to do collision detection between two lines?
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.
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
Re: How to do collision detection between two lines?
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.
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
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
- BrotSagtMist
- Party member
- Posts: 657
- Joined: Fri Aug 06, 2021 10:30 pm
Re: How to do collision detection between two lines?
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:
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:
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
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
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
Re: How to do collision detection between two lines?
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/
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?
STI - An awesome Tiled library
LÖVE3D - A 3D library for LÖVE 0.10+
Dev Blog | GitHub | excessive ❤ moé
LÖVE3D - A 3D library for LÖVE 0.10+
Dev Blog | GitHub | excessive ❤ moé
Who is online
Users browsing this forum: Bing [Bot] and 4 guests