How to do pixel-by-pixel collision detection?

[10098]

Hi,

Suppose I have two sprites with intersecting bounding boxes. What is the efficient way to check if any of the pixels on the images actually overlap? Can I do a logical AND with two ImageData's of framebuffers containing image masks to determine whether the non-transparent parts of the images overlap?

[kikito]

Can I do a logical AND with two ImageData's of framebuffers containing image masks to determine whether the non-transparent parts of the images overlap?

Lua 5.1 is not particularly efficient with binary data. Your best shot is having an internal polygonal representation of each frame, and using those for collisions, ignoring the pixel info completely.

[molul]

I'm currently using a "double" collision system. I use Hardon Collider (http://vrld.github.com/HardonCollider/) to make shapes for the player, enemies, items and platforms. Then, having these shapes, I have two collision detection functions:

-For enemies, items and platforms: I use Hardon Collider's "on_collide" callback, and then I program the resolution function to each collision case.

-For the stage floors, walls and ceilings, I use a pixel-perfect collision approach. Using the player's shape created with Hardon Collider (a rectangular bounding box), I check if, with the current velocity X and Y, it will be colliding a tile marked as ground, wall or ceiling in the next frame, so I update velocity X and Y BEFORE updating the position (Hardon Collider collisions must be resolved AFTER the collision happens, that's why I chose not to use it for this).

This approach is currently working really well for me. My only pending issue is diagonal grounds, which I've been trying to make work for a month with no success (I finally moved to other stuff like implementing different kinds of platforms and items, but I'll eventually get back to diagonals).

[trubblegum]

Code: Select all

obj = function(path, x, y)
  o = {}
  o.imageData = love.image.newImageData(path)
  o.image = love.graphics.newImage(o.imageData)
  o.x = x or 0
  o.y = y or 0
  o.w = o.imageData:getWidth()
  o.h = o.imageData:getHeight()
  return o
end

boxcollide = function() return true end
pixcollide = function(o1, o2)
  local offsetx = o2.x - o1.x
  local offsety = o2.y - o1.y
  local limitx = math.min((o2.x + o2.w) - (o1.x + o1.w), o2.w)
  local limity = math.min((o2.y + o2.w) - (o1.y + o1.w), o2.h)
  for i = math.max(offsetx, 0), limitx do
    for ii = math.max(offsety, 0), limity do
      if checkpixel(o2.imageData:getPixel(i, ii)) and checkpixel(o1.imageData:getPixel(i + offsetx, ii + offsety)) then
        return true
      end
    end
  end
  return false
end
checkpixel = function(r, g, b, a) return (r == 0 and g == 0 and b == 0 and a == 0) end

love.load = function()
  obj1 = obj('someimg.png')
  obj2 = obj('someotherimg.png')
end
love.update = function(dt)
  -- do some stuff that moves one of the objects
  if boxcollide(obj1, obj2) and pixcollide(obj1, obj2) then
    -- Houston, we have collision!
  end
end
love.draw = function()
  love.graphics.draw(obj1.image, obj1.x, obj1.y)
  love.graphics.draw(obj2.image, obj2.x, obj2.y)
  love.graphics.print(tostring(love.timer.getFPS()), 0, 0)
end

Like kikito said, it's inherently inefficient.

In fact, it's untested too, but in principle, it finds an intersecting rectangle, and checks each pixel in one object's imageData against the screen coordinate correspondent one in the other object's imageData, after a bounding box collision has been detected.

boxcollide() simply returns true for brevity, and ideally would return something useful, like the actual intersecting rectangle, rather than a boolean, which would change the structure of the collision check to something like if pixcollide(boxcollide(obj1, obj2)), where pixcollide would return false at the top if it receives false as its first argument. There are examples of functional bounding box collision littered throughout the forum if you need one.

[Xgoff]

Code: Select all

obj = function(path, x, y)
  o = {}
  o.imageData = love.image.newImageData(path)
  o.image = love.graphics.newImage(o.imageData)
  o.x = x or 0
  o.y = y or 0
  o.w = o.imageData:getWidth()
  o.h = o.imageData:getHeight()
  return o
end

boxcollide = function() return true end
pixcollide = function(o1, o2)
  local offsetx = o2.x - o1.x
  local offsety = o2.y - o1.y
  local limitx = math.min((o2.x + o2.w) - (o1.x + o1.w), o2.w)
  local limity = math.min((o2.y + o2.w) - (o1.y + o1.w), o2.h)
  for i = math.max(offsetx, 0), limitx do
    for ii = math.max(offsety, 0), limity do
      if checkpixel(o2.imageData:getPixel(i, ii)) and checkpixel(o1.imageData:getPixel(i + offsetx, ii + offsety)) then
        return true
      end
    end
  end
  return false
end
checkpixel = function(r, g, b, a) return (r == 0 and g == 0 and b == 0 and a == 0) end

love.load = function()
  obj1 = obj('someimg.png')
  obj2 = obj('someotherimg.png')
end
love.update = function(dt)
  -- do some stuff that moves one of the objects
  if boxcollide(obj1, obj2) and pixcollide(obj1, obj2) then
    -- Houston, we have collision!
  end
end
love.draw = function()
  love.graphics.draw(obj1.image, obj1.x, obj1.y)
  love.graphics.draw(obj2.image, obj2.x, obj2.y)
  love.graphics.print(tostring(love.timer.getFPS()), 0, 0)
end

Like kikito said, it's inherently inefficient.

In fact, it's untested too, but in principle, it finds an intersecting rectangle, and checks each pixel in one object's imageData against the screen coordinate correspondent one in the other object's imageData, after a bounding box collision has been detected.

boxcollide() simply returns true for brevity, and ideally would return something useful, like the actual intersecting rectangle, rather than a boolean, which would change the structure of the collision check to something like if pixcollide(boxcollide(obj1, obj2)), where pixcollide would return false at the top if it receives false as its first argument. There are examples of functional bounding box collision littered throughout the forum if you need one.

i wonder if storing collision maps as quadtrees would help. then you could use the intersection box as the query region for both colliding objects

then again, if the intersection is small it'd probably be slower than checking each pixel

[Inny]

Collision detection is usually broken down into several steps: The Broad Phase step and the Narrow Phase step.

In the Broad Phase Step, you generate a list of all objects that might collide. For instance, if you have 1000 live objects floating around your gameworld, then checking each against the others for collisions would lead to upwards of 1000000 checks a cycle, and most of those checks would be misses and not hits. So, in this step, you first determine which objects are even candidates for collision. If you had a quadtree or sptial hash set up, then you would only have to check entities against each other. If on average any given object only has 10 nearby objects, then that's only 10000 checks, a dramatic step down.

In the Narrow Phase Step, this is where you actually try to determine who is colliding. With the lists you got from the first step, you do your regular comparing of objects against each other. If you only have 10 live objects in the gameworld in any given moment, the broad phase step can and should be skipped.

As for pixel-by-pixel collision, it probably isn't necessary for most games to do this. Having a collision box surrounding the objects and doing a rectangle overlap check will go miles. If it's not precise enough, make the rectangle smaller, or give each object a couple of rectangle surrounding it's parts. If you're making a Bullet-hell type of shooter, like Gradius, they give you exactly one pixel as your collision mask, meaning that you can visually be hit by tons of projectiles, but nor actually die.