# Collisions between objects using line intersection Collisions are always one of the more difficult aspects of computer game programming.  One very useful method of determining whether one object has hit another is to check whether two lines cross each other.

As an example, consider a bullet (b) located at coordinates bx and by which travels at a velocity in the x and y axis of bvx and bvy.  This is shown in the diagram below and you can see that the movement of the bullet follows a line finishing at the position {bx+bvx, by+bvy). If we have another object with edges as shown in the figure below, we can check for whether the line described by the bullet crosses with the line described by the edge of the object (shown as a red circle).  The bonus of this method of calculating collisions is that you can obtain the exact coordinates of any collision and use this for further, more exciting, options in your game. Languages such as GameMaker provide plenty of collision based functions such as collision_line or point_in_rectangle. Even these may not give the exact coordinates of a collision, instead returning a boolean answer.

In order to find where two lines cross we need to calculate the straight line formula (y=mx+c) for the two lines.  For this I write a function that requires the start and end coordinates of the line (In this post I use PICO-8 to describe the function, but the mathematics and structure are applicable to GameMaker or any other language):

```function get_line_data(x1,y1,x2,y2)
local l={}
l.m=(y2-y1)/(x2-x1)
l.c=-(l.m*x1)+y1
return l
end```

This returns a linear equation data type with two variables: m for the gradient and c for the y axis intercept.  The gradient is simply calculated as dy/dx.  The value for c is calulcated by feeding this value of m back into one of the sets of coordinates (a full explanation can be found here).

This linear equation data type is important as we use it in the next function which gives the coordinates of the location where the two lines meet.

```function lines_cross(l1,l2)
local i={}
local tm = l1.m-l2.m
local tc = l2.c-l1.c

--are they parallel?
if l1.m==l2.m then
i.cross=false
i.x=0
i.y=0
else
i.cross=true
--x intercept
i.x = tc/tm
--y intercept
i.y = l1.m*i.x+l1.c
end
return i
end```

This function takes two linear equations (that is a pair of variables relating to m and c) and outputs a coordinate for the meeting of the lines.  If the two lines cross, they will share a set of x,y coordinates and so this function churns the maths required to calculate this.  Two parallel lines never meet (or meet at infinity, which is probably out of the scope of your game), so the function returns a third value as well as the coordinates (cross) which is set to true if the lines cross.

We are nearly there now, but all we have established so far are the coordinates (or otherwise) of interception of two lines.  The final piece of the jigsaw is to determine whether the lines cross in the range of the two lines.  The figure below shows the difference: So, we finally check if the coordinates are within the bounds and for this we send the coordinates (x and y) and two sets of line data (x1,y1 & x2,y2).  To keep it neat, I wrap all three of these into tables (PICO-8) or whatever data type system you may like.

```function in_range_lines(coord,lin1,lin2)
local bmax_x=max(lin2.x1,lin2.x2)
local bmin_x=min(lin2.x1,lin2.x2)
local bmax_y=max(lin2.y1,lin2.y2)
local bmin_y=min(lin2.y1,lin2.y2)
local smax_x=max(lin1.x1,lin1.x2)
local smin_x=min(lin1.x1,lin1.x2)
local smax_y=max(lin1.y1,lin1.y2)
local smin_y=min(lin1.y1,lin1.y2)
local cross=true

if (coord.x>bmax_x or
coord.x<bmin_x or
coord.y>bmax_y or
coord.y<bmin_y) or
(coord.x>smax_x or
coord.x<smin_x or
coord.y>smax_y or
coord.y<smin_y) then
cross=false
end

return cross
end```

Basically, we check if the coordinates fall into both lines.  If they do we have coordinates and we know they represent where two lines cross.

In order to merge it into a project I have written a single PICO-8 function that returns a table containing three variables:

```c: boolean - do the lines intersect
x: the x coordinate of the intesection
y: the y coordinate of the intesection```

The code is below.  Please use it and enjoy!

```function line_intersect(ax1,ay1,ax2,ay2,bx1,by1,bx2,by2)
--output
out={}
out.cross=false
out.x=0
out.y=0

--linear equation
local l1={}
local l2={}

l1.m=(ay2-ay1)/(ax2-ax1)
l1.c=-(l1.m*ax1)+ay1
l2.m=(by2-by1)/(bx2-bx1)
l2.c=-(l2.m*bx1)+by1

if l1.m==l2.m then
--parallel
return out
else
--coordinates of cross
local tm = l1.m-l2.m
local tc = l2.c-l1.c

--x intercept
local ix = tc/tm
out.x=ix

--y intercept
local iy = l1.m*ix+l1.c

--finally, check the range
local amax_x=max(ax1,ax2)
local amin_x=min(ax1,ax2)
local amax_y=max(ay1,ay2)
local amin_y=min(ay1,ay2)
local bmax_x=max(bx1,bx2)
local bmin_x=min(bx1,bx2)
local bmax_y=max(by1,by2)
local bmin_y=min(by1,by2)

if (ix>amax_x or
ix<amin_x or
iy>amax_y or
iy<amin_y) or
(ix>bmax_x or
ix<bmin_x or
iy>bmax_y or
iy<bmin_y) then
out.cross=false
else
out.x=ix
out.y=iy
out.cross=true
end
end
return out
end```

Happy programming!