Collision Detection Lib

[ishkabible]

ok so its pretty small but i haven't seen anything like it so far. first off per pixel collision detection credit goes to Yojimbo. it has the following features

*per pixel collision between 2 sprites
*line intersection detection
*box line intersection detection (really sprite line intersection)
*can extend lines so that you can take 2 points and test for a line like it but much longer
*bounding circle between two sprites
*bounding box between two sprites
*bounding box between two sprites with reduced/added tolerance so that you can reduce/increase size of bounding box for each sprite
*line constructor for use of lines with these functions

sprites must have x,y, and image property's where x and y donate numerical position and image donates a love image class
lines must have x1,y1,x2,y2 property's where each respective pair of x and y donates numerical postion
note: sprites must have collisionMap key as well for use with per pixel collision detection

Code: Select all

--[[
this script contains sevral usefull functions for collsion detection of maney kinds.
it uses 2 basic data typs, line and sprite
line must be comprised of x1,y1,x2,y2 as non nil numercal values
sprite must be comprised of x,y,image where x and y are numerical and image is love image class
note: a collisionMap key is needed for pixal perfect collsion. pixal perfect collsion should be used as
little as possible becuase the collisionMap takes up more memeory and per pixal collsion detection is
very slow. the collsion map may be conscted by the NewCollisionMap with the associated filepath as argument
--]]

--[[
you never know how someone wants to store there lines so i have provided a netural line class constructor
--]]
function NewLine(sx,sy,ex,ey)
	return {x1=sx,y1=sy,x2=ex,y2=ey}
end

function BoundingCircleCollide(S1,S2)
	local Rad1 = math.sqrt((S1.image:getWidth()/2)^2+(S1.image:getHeight()/2)^2)
	local Rad2 = math.sqrt((S2.image:getWidth()/2)^2+(S2.image:getHeight()/2)^2)
	local Dist = math.sqrt((S2.image:getWidth()/2-S1.image:getWidth()/2)^2+(S2.image:getHeight()/2-S1.image:getHeight()/2)^2)
	return Rad1+Rad2 < Dist
end

--[[
this may seem silly but it extends the line so that no mater where the line is in a 800x600
screen, the line will always(unless the line is a point) reach the edge of the screen one way
(going from point 1 to point2). you should not need any more than that as even on the largest
screens i know of you would have to have a line of 3 pixals or less for it to mater.
if you think it matters then increse it. also if you want to detect things off screen from
very far away you may want to increse it
@param:
	L-a table representing a line. must have x1,y1,x2,y2 keys as non nil numercal values
--]]
function ExtendLine(L)
	local Line = L
	local xinc = L.x2-L.x1
	local yinc = L.y2-L.y1
	Line.x2 = Line.x2+xinc*1000
	Line.y2 = Line.y2+yinc*1000
	return Line
end

--[[
standerd box vs. box collsion. checks for bounding box collsion between two sprites
@param:
	S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class)
	S2-same as S1
--]]
function BoundingBoxCollide(S1,S2)
	local left1=S1.x-S1.image:getWidth()/2
	local left2=S2.x-S2.image:getWidth()/2
	local right1=S1.x+S1.image:getWidth()/2
	local right2=S2.x+S2.image:getWidth()/2
	local top1=S1.y-S1.image:getHeight()/2
	local top2=S2.y-S2.image:getHeight()/2
	local bottom1=S1.y+S1.image:getHeight()/2
	local bottom2=S2.y+S2.image:getHeight()/2
	if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
	return true
end

--[[
standerd box vs. box collsion but with tollrence, so that you can shrink your bouding box for each sprite
12 is a good tolrence for 64x64 images but it will take some messing with in most cases
@param:
	S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class)
	S2-same as S1
	t1-number, tells how much to shrink bounding box by for S1
	t2-same as t1 but instead for S2
--]]
function BoundingBoxCollideWT(S1,S2,t1,t2)
	local left1=S1.x-S1.image:getWidth()/2+t1
	local left2=S2.x-S2.image:getWidth()/2+t2
	local right1=S1.x+S1.image:getWidth()/2-t1
	local right2=S2.x+S2.image:getWidth()/2-t2
	local top1=S1.y-S1.image:getHeight()/2+t1
	local top2=S2.y-S2.image:getHeight()/2+t2
	local bottom1=S1.y+S1.image:getHeight()/2-t1
	local bottom2=S2.y+S2.image:getHeight()/2-t2
	if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
	return true
end

--[[
this is mainly for BoxLineCollsion but you can use it for other stuff to
checks for intersection of two lines
@param:
	L1-a table representing a line. must have x1,y1,x2,y2 keys as non nil numercal values
	L2-same as L1
--]]
function LineIntersets(L1,L2)
	local denom = ((L2.y2-L2.y1)*(L1.x2-L1.x1)-((L2.x2-L2.x1)*(L1.y2-L1.y1)))
	local numerator = ((L2.x2-L2.x1)*(L1.y1-L2.y1)-((L2.y2-L2.y1)*(L1.x1-L2.x1)))
	local numerator2 = ((L1.x2-L1.x1)*(L1.y1-L2.y1)-((L1.y2-L1.y1)*(L1.x1-L2.x1)))
	if denom == 0 then
		return false
	end
	local ua = numerator/denom
	local ub = numerator2/denom
	return (ua>=0 and ua <= 1 and ub >= 0 and ub <= 1)
end

--[[
checks for intersection of line and bounding box(of sprite)
@param:
	S-a table representing a sprite. must have x(number),y(number),image(LOVE image class)
	L-a table representing a line. must have x1,y1,x2,y2 keys as non nil numercal values
--]]
function BoxLineCollsion(S,L)
	local left=S.x-S..image:getWidth()/2+12
	local right=S.x+S..image:getWidth()/2-12
	local top=S.y-S.image:getHeight()/2+12
	local bottom=S.y+S.image:getHeight()/2-12
	if LineIntersets(NewLine(left,top,right,top),L) then return true
	elseif LineIntersets(NewLine(left,bottom,right,bottom),L) then return true
	elseif LineIntersets(NewLine(right,top,right,bottom),L) then return true
	--no need to check thrid as there is no way to go though 1 line and 1 line only
	end
	return false
end

--[[
makes pixal map of image for pixal perfect collsion detection
@param:
	imageFileName- string donating file path to image
--]]
function NewCollisionMap( imageFileName )

    local imageData = love.image.newImageData( imageFileName )
    local width = imageData:getWidth()
    local height = imageData:getHeight()
    local collisionMap = {}

    -- Build a collision map as a table of row tables that contains 1's and 0's.
    -- A 1 means the pixel at this position is non-transparent and 0 means it
    -- transparent.
    for y = 1, height do

        collisionMap[y] = {}

        for x = 1, width do

            -- Use -1 since getPixel() starts indexing at 0 not 1 like Lua.
            local r, g, b, a = imageData:getPixel( x-1, y-1 )

            if a == 0 then
                collisionMap[y][x] = 0
            else
                collisionMap[y][x] = 1
            end

        end
    end

    return collisionMap

end

--[[
checks for pixal perfect collsion detection between two sprites
@param:
	sprite1-a table representing a sprite. must have x(number),y(number),
			image(LOVE image class),collisionMap(class donated by function above)
	sprite2-same as sprite1
--]]
function PerPixelCollision( sprite1, sprite2 )

    -- First, we do a simple bounding box collision check. This will let
    -- us know if the two sprites overlap in any way.
    if not ( (sprite1.x + sprite1.image:getWidth() > sprite2.x) and
             (sprite1.x < sprite2.x + sprite2.image:getWidth()) and
             (sprite1.y + sprite1.image:getHeight() > sprite2.y) and
             (sprite1.y < sprite2.y + sprite2.image:getHeight()) ) then
        return false
    end

    -- If we made it this far, our two sprites definitely touch or overlap,
    -- but that doesn't mean that that we have an actual collision between
    -- two non-transparent pixels.

    -- By default, sprite1 scans sprite2 for a pixel collision per line, so
    -- if sprite1 is taller, swap the sprites around so the shorter one is
    -- scanning the taller one. This will result in less work in cases where
    -- they initially overlap but ultimately do not collide at the pixel level.
    if sprite1.image:getHeight() > sprite2.image:getHeight() then
       objTemp = sprite1
       sprite1 = sprite2
       sprite1 = objTemp
    end

    -- Loop through each row of sprite1's collision map and check it against
    -- sprite2's corresponding collision map row.
    for indexY = 1, sprite1.image:getHeight() do

        local screenY = math.floor( (sprite1.y + indexY) - 1  )

        if screenY > sprite2.y and screenY <= sprite2.y + sprite2.image:getHeight() then

            -- Some, or all, of the current row (Y) of sprite1's collision map overlaps
            -- sprite2's collision map. Calculate the start and end indices (X) for each
            -- row, so we can test this area of overlap for a collision of
            -- non-transparent pixels.

            local y1 = math.floor( indexY )
            local y2 = 1

            if screenY > sprite2.y then
                y2 = math.floor( screenY - sprite2.y )
            elseif screenY < sprite2.y then
                y2 = math.floor( sprite2.y - screenY )
            end

            local sprite1Index1 = 1
            local sprite1Index2 = sprite1.image:getWidth()
            local sprite2Index1 = 1
            local sprite2Index2 = sprite2.image:getWidth()

            if sprite1.x < sprite2.x then

               sprite1Index1 = math.floor( sprite2.x - sprite1.x ) + 1
               sprite1Index2 = sprite1.image:getWidth()

               sprite2Index1 = 1
               sprite2Index2 = math.floor( (sprite1.x + sprite1.image:getWidth()) - sprite2.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite2Index2 > sprite2.image:getWidth() then
                  sprite2Index2 = sprite2.image:getWidth()
               end

            elseif sprite1.x > sprite2.x then

               sprite1Index1 = 1
               sprite1Index2 = math.floor( (sprite2.x + sprite2.image:getWidth()) - sprite1.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite1Index2 > sprite1.image:getWidth() then
                  sprite1Index2 = sprite1.image:getWidth()
               end

               sprite2Index1 = math.floor( sprite1.x - sprite2.x ) + 1
               sprite2Index2 = sprite2.image:getWidth()

            else -- sprite1.x == sprite2.x

               -- If the two sprites have the same x position - the width of
               -- overlap is simply the shortest width.
               shortest = sprite1.image:getWidth()

               if sprite2.image:getWidth() < shortest then
                  shortest = sprite2.image:getWidth()
               end

               sprite1Index1 = 1
               sprite1Index2 = shortest

               sprite2Index1 = 1
               sprite2Index2 = shortest

            end

            local index1 = sprite1Index1
            local index2 = sprite2Index1

            while index1 < sprite1Index2 and index2 < sprite2Index2 do

                if sprite1.collisionMap[y1][index1] == 1 and sprite2.collisionMap[y2][index2] == 1 then
                    return true -- We have a collision of two non-transparent pixels!
                end

                index1 = index1 + 1
                index2 = index2 + 1

            end

        end

    end

    return false -- We do NOT have a collision of two non-transparent pixels.

end

looking for any feed back

[Robin]

You seem to have a lot of code duplication going on…

Also, I'm not sure if BoundingCircleCollide() works. Shouldn't Dist be calculated from positions rather than, you know, sizes?

As for extending lines, your function is quite dangerous: it changes the table passed to it! This should work:

Code: Select all

function ExtendLine(L)
   local xinc = L.x2-L.x1
   local yinc = L.y2-L.y1
   return {x1 = 0, y1 = L.y1 - (L.x1*yinc/xinc), x2 = love.graphics.getWidth(), y2 = L.y1 + ((love.graphics.getWidth()-L.x1)*yinc/xinc) 
end

[nevon]

I would suggest collaboratively improving the lib and posting it on the wiki.

[Thursdaybloom]

Not really knowing how else to contribute I decided to clean up the english spelling and grammar incase there are plans to publish or release this. I've tried not to completely change ishkabible's sentences out of respect for the original author. Obviously I've probably missed a few things

Code: Select all

--[[
This script contains several useful functions for many kinds of collision detection.
It uses 2 basic data types, 'line' and 'sprite'.
'line' must be comprised of x1, y1, x2, y2 as non-nil numerical values.
'sprite' must be comprised of x, y, image where x and y are numerical and image is the love image class.
Note: a collisionMap key is needed for pixel-perfect collision. Pixel-perfect collision should be used as
little as possible because of its large memory consumption and possible slow downs. 
The collision map may be connected to the NewCollisionMap with the associated filepath as argument.
--]]

--[[
You never know how someone wants to store their lines so I have provided a neutral line class constructor.
--]]
function NewLine(sx,sy,ex,ey)
   return {x1=sx,y1=sy,x2=ex,y2=ey}
end

function BoundingCircleCollide(S1,S2)
   local Rad1 = math.sqrt((S1.image:getWidth()/2)^2+(S1.image:getHeight()/2)^2)
   local Rad2 = math.sqrt((S2.image:getWidth()/2)^2+(S2.image:getHeight()/2)^2)
   local Dist = math.sqrt((S2.image:getWidth()/2-S1.image:getWidth()/2)^2+(S2.image:getHeight()/2-S1.image:getHeight()/2)^2)
   return Rad1+Rad2 < Dist
end

--[[
This may seem silly but it extends the line so that no mater where the line is in a 800x600
screen. The line will always (unless the line is a point) reach the edge of the screen one way
(going from point 1 to point 2). You shouldn't need any more than this as even on the largest
screens I know of you would have to have a line of 3 pixels or less for it to matter.
Although, if you think it does matter then feel free to increase it. If you want to detect things off screen from
very far away then you may want to increase it.
@param:
   L-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values
--]]
function ExtendLine(L)
   local Line = L
   local xinc = L.x2-L.x1
   local yinc = L.y2-L.y1
   Line.x2 = Line.x2+xinc*1000
   Line.y2 = Line.y2+yinc*1000
   return Line
end

--[[
Standard box vs. box collision. Checks for bounding box collision between two sprites.
@param:
   S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class)
   S2-same as S1
--]]
function BoundingBoxCollide(S1,S2)
   local left1=S1.x-S1.image:getWidth()/2
   local left2=S2.x-S2.image:getWidth()/2
   local right1=S1.x+S1.image:getWidth()/2
   local right2=S2.x+S2.image:getWidth()/2
   local top1=S1.y-S1.image:getHeight()/2
   local top2=S2.y-S2.image:getHeight()/2
   local bottom1=S1.y+S1.image:getHeight()/2
   local bottom2=S2.y+S2.image:getHeight()/2
   if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
   return true
end

--[[
Standard box vs. box collision but with tolerance so that you can shrink your bounding box for each sprite.
12 is a good tolerance for 64x64 images but it will take some messing with in most cases.
@param:
   S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class).
   S2-same as S1.
   t1-number, tells how much to shrink bounding box by for S1.
   t2-same as t1 but instead for S2.
--]]
function BoundingBoxCollideWT(S1,S2,t1,t2)
   local left1=S1.x-S1.image:getWidth()/2+t1
   local left2=S2.x-S2.image:getWidth()/2+t2
   local right1=S1.x+S1.image:getWidth()/2-t1
   local right2=S2.x+S2.image:getWidth()/2-t2
   local top1=S1.y-S1.image:getHeight()/2+t1
   local top2=S2.y-S2.image:getHeight()/2+t2
   local bottom1=S1.y+S1.image:getHeight()/2-t1
   local bottom2=S2.y+S2.image:getHeight()/2-t2
   if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
   return true
end

--[[
This is mainly for BoxLineCollsion but you can use it for other stuff to
check for intersections between two lines.
@param:
   L1-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values.
   L2-same as L1.
--]]
function LineIntersets(L1,L2)
   local denom = ((L2.y2-L2.y1)*(L1.x2-L1.x1)-((L2.x2-L2.x1)*(L1.y2-L1.y1)))
   local numerator = ((L2.x2-L2.x1)*(L1.y1-L2.y1)-((L2.y2-L2.y1)*(L1.x1-L2.x1)))
   local numerator2 = ((L1.x2-L1.x1)*(L1.y1-L2.y1)-((L1.y2-L1.y1)*(L1.x1-L2.x1)))
   if denom == 0 then
      return false
   end
   local ua = numerator/denom
   local ub = numerator2/denom
   return (ua>=0 and ua <= 1 and ub >= 0 and ub <= 1)
end

--[[
Checks for intersections between a line and bounding box(of sprite).
@param:
   S-a table representing a sprite. must have x(number),y(number),image(LOVE image class).
   L-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values.
--]]
function BoxLineCollsion(S,L)
   local left=S.x-S..image:getWidth()/2+12
   local right=S.x+S..image:getWidth()/2-12
   local top=S.y-S.image:getHeight()/2+12
   local bottom=S.y+S.image:getHeight()/2-12
   if LineIntersets(NewLine(left,top,right,top),L) then return true
   elseif LineIntersets(NewLine(left,bottom,right,bottom),L) then return true
   elseif LineIntersets(NewLine(right,top,right,bottom),L) then return true
   --no need to check third as there is no way to go though 1 line and 1 line only
   end
   return false
end

--[[
Makes pixel map of image for pixel-perfect collision detection.
@param:
   imageFileName- string donating file path to image.
--]]
function NewCollisionMap( imageFileName )

    local imageData = love.image.newImageData( imageFileName )
    local width = imageData:getWidth()
    local height = imageData:getHeight()
    local collisionMap = {}

    -- Build a collision map as a table of row tables that contains 1's and 0's.
    -- A 1 means the pixel at this position is non-transparent and 0 means it
    -- is transparent.
    for y = 1, height do

        collisionMap[y] = {}

        for x = 1, width do

            -- Use -1 since getPixel() starts indexing at 0 not 1 like Lua.
            local r, g, b, a = imageData:getPixel( x-1, y-1 )

            if a == 0 then
                collisionMap[y][x] = 0
            else
                collisionMap[y][x] = 1
            end

        end
    end

    return collisionMap

end

--[[
Checks for pixel perfect collision detection between two sprites.
@param:
   sprite1-a table representing a sprite. must have x(number),y(number),
         image(LOVE image class),collisionMap(class donated by function above)
   sprite2-same as sprite1
--]]
function PerPixelCollision( sprite1, sprite2 )

    -- First, we do a simple bounding box collision check. This will let
    -- us know if the two sprites overlap in any way.
    if not ( (sprite1.x + sprite1.image:getWidth() > sprite2.x) and
             (sprite1.x < sprite2.x + sprite2.image:getWidth()) and
             (sprite1.y + sprite1.image:getHeight() > sprite2.y) and
             (sprite1.y < sprite2.y + sprite2.image:getHeight()) ) then
        return false
    end

    -- If we made it this far, our two sprites definitely touch or overlap,
    -- but that doesn't mean we have an actual collision between
    -- two non-transparent pixels.

    -- By default, sprite1 scans sprite2 for a pixel collision per line, so
    -- if sprite1 is taller, swap the sprites around so that the shorter one is
    -- scanning the taller one. This will result in less work in cases where
    -- they initially overlap but ultimately do not collide at the pixel level.
    if sprite1.image:getHeight() > sprite2.image:getHeight() then
       objTemp = sprite1
       sprite1 = sprite2
       sprite1 = objTemp
    end

    -- Loop through each row of sprite1's collision map and check it against
    -- sprite2's corresponding collision map row.
    for indexY = 1, sprite1.image:getHeight() do

        local screenY = math.floor( (sprite1.y + indexY) - 1  )

        if screenY > sprite2.y and screenY <= sprite2.y + sprite2.image:getHeight() then

            -- Some, or all, of the current row (Y) of sprite1's collision map overlaps
            -- sprite2's collision map. Calculate the start and end indices (X) for each
            -- row, so we can test this area of overlap for a collision of
            -- non-transparent pixels.

            local y1 = math.floor( indexY )
            local y2 = 1

            if screenY > sprite2.y then
                y2 = math.floor( screenY - sprite2.y )
            elseif screenY < sprite2.y then
                y2 = math.floor( sprite2.y - screenY )
            end

            local sprite1Index1 = 1
            local sprite1Index2 = sprite1.image:getWidth()
            local sprite2Index1 = 1
            local sprite2Index2 = sprite2.image:getWidth()

            if sprite1.x < sprite2.x then

               sprite1Index1 = math.floor( sprite2.x - sprite1.x ) + 1
               sprite1Index2 = sprite1.image:getWidth()

               sprite2Index1 = 1
               sprite2Index2 = math.floor( (sprite1.x + sprite1.image:getWidth()) - sprite2.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite2Index2 > sprite2.image:getWidth() then
                  sprite2Index2 = sprite2.image:getWidth()
               end

            elseif sprite1.x > sprite2.x then

               sprite1Index1 = 1
               sprite1Index2 = math.floor( (sprite2.x + sprite2.image:getWidth()) - sprite1.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite1Index2 > sprite1.image:getWidth() then
                  sprite1Index2 = sprite1.image:getWidth()
               end

               sprite2Index1 = math.floor( sprite1.x - sprite2.x ) + 1
               sprite2Index2 = sprite2.image:getWidth()

            else -- sprite1.x == sprite2.x

               -- If the two sprites have the same x position - the width of
               -- overlap is simply the shortest width.
               shortest = sprite1.image:getWidth()

               if sprite2.image:getWidth() < shortest then
                  shortest = sprite2.image:getWidth()
               end

               sprite1Index1 = 1
               sprite1Index2 = shortest

               sprite2Index1 = 1
               sprite2Index2 = shortest

            end

            local index1 = sprite1Index1
            local index2 = sprite2Index1

            while index1 < sprite1Index2 and index2 < sprite2Index2 do

                if sprite1.collisionMap[y1][index1] == 1 and sprite2.collisionMap[y2][index2] == 1 then
                    return true -- We have a collision of two non-transparent pixels!
                end

                index1 = index1 + 1
                index2 = index2 + 1

            end

        end

    end

    return false -- We do NOT have a collision of two non-transparent pixels.

end

[nevon]

The ExtendLine function seems odd to me. Wouldn't it be wiser to make a vector out of it? That way you'd get a true infinite line.

[zac352]

*per pixel collision between 2 sprites

Uh... Prepare for Death By Lag
Now, setting a bounding box using a sprite and a threshold is actually sane... But PER PIXEL?

Look at it this way:
For every per-pixel 16 by 16 pixel circle sprite you test, you could calculate 800 circles with a radius-position approach.

[ishkabible]

Robin has been helpful in pointing out some major flaws. by the way, benchmark the per pixel collision before you bash it, its really good actually!! i feel rather embarrassed at the bounding circle, no clue how that happened, fixing now. thanks robin!! also my spelling is horrible so thanks for cleaning it up. so long as the comments explain the same thing i don't care how they are written.

edit: here is what i got so far
*fixed bounding circle
*added bounding circle with tolerance
*fixed extend line, still i want to make it truly infinite as right now it's just kinda a hack. will keep current box line and line to line collision but will add functions for use with infinite vectors

Code: Select all

--[[
This script contains several useful functions for many kinds of collision detection.
It uses 2 basic data types, 'line' and 'sprite'.
'line' must be comprised of x1, y1, x2, y2 as non-nil numerical values.
'sprite' must be comprised of x, y, image where x and y are numerical and image is the love image class.
Note: a collisionMap key is needed for pixel-perfect collision. Pixel-perfect collision should be used as
little as possible because of its large memory consumption and possible slow downs.
The collision map may be constructed with the NewCollisionMap function with the associated filepath passed as argument.
--]]

--[[
You never know how someone wants to store their lines so I have provided a neutral line class constructor.
--]]
function NewLine(sx,sy,ex,ey)
	return {x1=sx,y1=sy,x2=ex,y2=ey}
end

function NewVec(smag,stheta)
	return {mag,theta}
end

function BoundingCircleCollide(S1,S2)
	local Rad1 = math.sqrt((S1.image:getWidth()/2)^2+(S1.image:getHeight()/2)^2)
	local Rad2 = math.sqrt((S2.image:getWidth()/2)^2+(S2.image:getHeight()/2)^2)
	local Dist = math.sqrt((S2.x-S1.x)^2+(S2.y-S1.y)^2)
	return Rad1+Rad2 > Dist
end

function BoundingCircleCollideWT(S1,S2,t1,t2)
	local Rad1 = math.sqrt((S1.image:getWidth()/2)^2+(S1.image:getHeight()/2)^2)-t1
	local Rad2 = math.sqrt((S2.image:getWidth()/2)^2+(S2.image:getHeight()/2)^2)-t2
	local Dist = math.sqrt((S2.x-S1.x)^2+(S2.y-S1.y)^2)
	return Rad1+Rad2 > Dist
end

--[[
This may seem silly but it extends the line so that no mater where the line is in a 800x600
screen. The line will always (unless the line is a point) reach the edge of the screen one way
(going from point 1 to point 2). You shouldn't need any more than this as even on the largest
screens I know of you would have to have a line of 3 pixels or less for it to matter.
Although, if you think it does matter then feel free to increase it. If you want to detect things off screen from
very far away then you may want to increase it.
@param:
   L-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values
--]]
function ExtendLine(L)
   local xinc = L.x2-L.x1
   local yinc = L.y2-L.y1
   return {x1 = 0, y1 = L.y1 - (L.x1*yinc/xinc), x2 = love.graphics.getWidth(), y2 = L.y1 + ((love.graphics.getWidth()-L.x1)*yinc/xinc)}
end

function Line2Vec(L)
	smag = math.sqrt((L.x2-L.x1)^2+(L.y2-L.y1)^2)
	stheta = math.atan2((L.y2-L.y1),(L.x2-L.x1))
	return {mag=smag,theta=stheta}
end

--[[
Standard box vs. box collision. Checks for bounding box collision between two sprites.
@param:
   S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class)
   S2-same as S1
--]]
function BoundingBoxCollide(S1,S2)
	local left1=S1.x-S1.image:getWidth()/2
	local left2=S2.x-S2.image:getWidth()/2
	local right1=S1.x+S1.image:getWidth()/2
	local right2=S2.x+S2.image:getWidth()/2
	local top1=S1.y-S1.image:getHeight()/2
	local top2=S2.y-S2.image:getHeight()/2
	local bottom1=S1.y+S1.image:getHeight()/2
	local bottom2=S2.y+S2.image:getHeight()/2
	if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
	return true
end

--[[
Standard box vs. box collision but with tolerance so that you can shrink your bounding box for each sprite.
12 is a good tolerance for 64x64 images but it will take some messing with in most cases.
@param:
   S1-a table representing a sprite. must have x(number),y(number),image(LOVE image class).
   S2-same as S1.
   t1-number, tells how much to shrink bounding box by for S1.
   t2-same as t1 but instead for S2.
--]]
function BoundingBoxCollideWT(S1,S2,t1,t2)
	local left1=S1.x-S1.image:getWidth()/2+t1
	local left2=S2.x-S2.image:getWidth()/2+t2
	local right1=S1.x+S1.image:getWidth()/2-t1
	local right2=S2.x+S2.image:getWidth()/2-t2
	local top1=S1.y-S1.image:getHeight()/2+t1
	local top2=S2.y-S2.image:getHeight()/2+t2
	local bottom1=S1.y+S1.image:getHeight()/2-t1
	local bottom2=S2.y+S2.image:getHeight()/2-t2
	if bottom1 < top2 then return false end
    if top1 > bottom2 then return false end
    if right1 < left2 then return false end
    if left1 > right2 then return false end
	return true
end

--[[
This is mainly for BoxLineCollsion but you can use it for other stuff to
check for intersections between two lines.
@param:
   L1-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values.
   L2-same as L1.
--]]
function LineIntersets(L1,L2)
	local denom = ((L2.y2-L2.y1)*(L1.x2-L1.x1)-((L2.x2-L2.x1)*(L1.y2-L1.y1)))
	local numerator = ((L2.x2-L2.x1)*(L1.y1-L2.y1)-((L2.y2-L2.y1)*(L1.x1-L2.x1)))
	local numerator2 = ((L1.x2-L1.x1)*(L1.y1-L2.y1)-((L1.y2-L1.y1)*(L1.x1-L2.x1)))
	if denom == 0 then
		return false
	end
	local ua = numerator/denom
	local ub = numerator2/denom
	return (ua>=0 and ua <= 1 and ub >= 0 and ub <= 1)
end

function LineVectorInterSection(L,V)

end

--[[
Checks for intersections between a line and bounding box(of sprite).
@param:
   S-a table representing a sprite. must have x(number),y(number),image(LOVE image class).
   L-a table representing a line. must have x1,y1,x2,y2 keys as non-nil numerical values.
--]]
function BoxLineCollsion(S,L)
	local left=S.x-S..image:getWidth()/2+12
	local right=S.x+S..image:getWidth()/2-12
	local top=S.y-S.image:getHeight()/2+12
	local bottom=S.y+S.image:getHeight()/2-12
	if LineIntersets(NewLine(left,top,right,top),L) then return true
	elseif LineIntersets(NewLine(left,bottom,right,bottom),L) then return true
	elseif LineIntersets(NewLine(right,top,right,bottom),L) then return true
	--no need to check thrid as there is no way to go though 1 line and 1 line only
	end
	return false
end

--[[
Makes pixel map of image for pixel-perfect collision detection.
@param:
   imageFileName- string donating file path to image.
--]]
function NewCollisionMap( imageFileName )

    local imageData = love.image.newImageData( imageFileName )
    local width = imageData:getWidth()
    local height = imageData:getHeight()
	collisionMap = {}

    -- Build a collision map as a table of row tables that contains 1's and 0's.
    -- A 1 means the pixel at this position is non-transparent and 0 means it
    -- transparent.
    for y = 0, height do

        collisionMap[y] = {}

        for x = 0, width do

            -- Use -1 since getPixel() starts indexing at 0 not 1 like Lua.
            local r, g, b, a = imageData:getPixel( x, y )

            if a == 0 then
                collisionMap[y][x] = 0
            else
                collisionMap[y][x] = 1
            end

        end
    end

    return collisionMap

end


--[[
Checks for pixel perfect collision between two sprites.
@param:
   sprite1-a table representing a sprite. must have x(number),y(number),
         image(LOVE image class),collisionMap(class donated by function above)
   sprite2-same as sprite1
--]]
function PerPixelCollision( sprite1, sprite2 )

    -- First, we do a simple bounding box collision check. This will let
    -- us know if the two sprites overlap in any way.
    if not ( (sprite1.x + sprite1.image:getWidth() > sprite2.x) and
             (sprite1.x < sprite2.x + sprite2.image:getWidth()) and
             (sprite1.y + sprite1.image:getHeight() > sprite2.y) and
             (sprite1.y < sprite2.y + sprite2.image:getHeight()) ) then
        return false
    end

    -- If we made it this far, our two sprites definitely touch or overlap,
    -- but that doesn't mean that that we have an actual collision between
    -- two non-transparent pixels.

    -- By default, sprite1 scans sprite2 for a pixel collision per line, so
    -- if sprite1 is taller, swap the sprites around so the shorter one is
    -- scanning the taller one. This will result in less work in cases where
    -- they initially overlap but ultimately do not collide at the pixel level.
    if sprite1.image:getHeight() > sprite2.image:getHeight() then
       objTemp = sprite1
       sprite1 = sprite2
       sprite1 = objTemp
    end

    -- Loop through each row of sprite1's collision map and check it against
    -- sprite2's corresponding collision map row.
    for indexY = 0, sprite1.image:getHeight() do

        local screenY = math.floor( (sprite1.y + indexY) - 1  )

        if screenY > sprite2.y and screenY <= sprite2.y + sprite2.image:getHeight() then

            -- Some, or all, of the current row (Y) of sprite1's collision map overlaps
            -- sprite2's collision map. Calculate the start and end indices (X) for each
            -- row, so we can test this area of overlap for a collision of
            -- non-transparent pixels.

            local y1 = math.floor( indexY )
            local y2 = 1

            if screenY > sprite2.y then
                y2 = math.floor( screenY - sprite2.y )
            elseif screenY < sprite2.y then
                y2 = math.floor( sprite2.y - screenY )
            end

            local sprite1Index1 = 1
            local sprite1Index2 = sprite1.image:getWidth()
            local sprite2Index1 = 1
            local sprite2Index2 = sprite2.image:getWidth()

            if sprite1.x < sprite2.x then

               sprite1Index1 = math.floor( sprite2.x - sprite1.x ) + 1
               sprite1Index2 = sprite1.image:getWidth()

               sprite2Index1 = 1
               sprite2Index2 = math.floor( (sprite1.x + sprite1.image:getWidth()) - sprite2.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite2Index2 > sprite2.image:getWidth() then
                  sprite2Index2 = sprite2.image:getWidth()
               end

            elseif sprite1.x > sprite2.x then

               sprite1Index1 = 1
               sprite1Index2 = math.floor( (sprite2.x + sprite2.image:getWidth()) - sprite1.x ) + 1

               -- If the sprites being tested are of different sizes it's possible
               -- for this index to get too big - so clamp it.
               if sprite1Index2 > sprite1.image:getWidth() then
                  sprite1Index2 = sprite1.image:getWidth()
               end

               sprite2Index1 = math.floor( sprite1.x - sprite2.x ) + 1
               sprite2Index2 = sprite2.image:getWidth()

            else -- sprite1.x == sprite2.x

               -- If the two sprites have the same x position - the width of
               -- overlap is simply the shortest width.
               shortest = sprite1.image:getWidth()

               if sprite2.image:getWidth() < shortest then
                  shortest = sprite2.image:getWidth()
               end

               sprite1Index1 = 1
               sprite1Index2 = shortest

               sprite2Index1 = 1
               sprite2Index2 = shortest

            end

            local index1 = sprite1Index1
            local index2 = sprite2Index1

            while index1 < sprite1Index2 and index2 < sprite2Index2 do
                if sprite1.collisionMap[y1][index1] == 1 and sprite2.collisionMap[y2][index2] == 1 then
                    return true -- We have a collision of two non-transparent pixels!
                end

                index1 = index1 + 1
                index2 = index2 + 1

            end

        end

    end

    return false -- We do NOT have a collision of two non-transparent pixels.

end

[zac352]

Robin has been helpful in pointing out some major flaws. by the way, benchmark the per pixel collision before you bash it, its really good actually!!

I'd still like to point out that a circle with a radius of 16 pixels has a little over 800 pixels in it. That means 800 tests. 800 tests per pixel in another circle.
800*800 = 640 000 tests.
640 000 tests where you could've done 2. That's an insane limitation.

[ishkabible]

Robin has been helpful in pointing out some major flaws. by the way, benchmark the per pixel collision before you bash it, its really good actually!!

I'd still like to point out that a circle with a radius of 16 pixels has a little over 800 pixels in it. That means 800 tests. 800 tests per pixel in another circle.
800*800 = 640 000 tests.
640 000 tests where you could've done 2. That's an insane limitation.

witch test are you referring to, the bounding circle dose not do this and pixel perfect dose not use any type of circles to accomplish it's task. im open to suggestions as i'm not that experienced in game development, i'm just not seeing what your talking about.

[zac352]

Robin has been helpful in pointing out some major flaws. by the way, benchmark the per pixel collision before you bash it, its really good actually!!

I'd still like to point out that a circle with a radius of 16 pixels has a little over 800 pixels in it. That means 800 tests. 800 tests per pixel in another circle.
800*800 = 640 000 tests.
640 000 tests where you could've done 2. That's an insane limitation.

witch test are you referring to, the bounding circle dose not do this and pixel perfect dose not use any type of circles to accomplish it's task. im open to suggestions as i'm not that experienced in game development, i'm just not seeing what your talking about.

I'm saying that per pixel between two circles with a radius of 16 pixels will take 640 000 tests.
Doing a simple:

Code: Select all

local p=(p1-p2)
return p.magnitude<=r1+r2

is much more efficient than doing the exact same thing 640 000 times. I'm not sure why you think that's efficient.. Please explain?