Pixel based collision map

[pgimeno]

I'm trying to make a pixel-based collision detector, but every path I take has led to a brick wall. I wonder if someone has any recommendations. The problem is finding if a tile mask intersects the sprite mask. That can be done by bitwise ANDing the masks, or by multiplying (setBlendMode) the alphas or the RGBs, and checking if the result is uniform (all zeros, all transparent, all black) or not.

So, first I tried with a canvas and getImageData. Alas, even with a 1x1 canvas, getImageData causes 100% CPU usage:

Code: Select all

function love.load()
  canvas = love.graphics.newCanvas(1, 1)
end

function love.update(dt)
  canvas:getImageData()
end

(not even garbage collection runs, but that's the least of the problems as it can be run manually).

Maybe ImageData is a view of the canvas that gets updated in real time? Nope, it's a snapshot. That road is closed too.

I haven't tried using tables with the collision bitmap data and bit manipulation, as I figure it would be too slow to do it several times per frame, depending on the tile sizes. So I thought of using strings, since they are binary byte arrays. But I've searched all places I could imagine, and I didn't see any bitwise string manipulation library for Lua: all of them were for numbers, not strings. In PHP (and in Perl, I think) you can do string|string, string^string and string&string. It would be nice if LÖVE included functions to do that, plus bit shift left/right of strings. That would enable me to do the necessary bit manipulation that would probably provide the speed I need.

But since there's currently no such thing, I wonder if there's any other fast alternative that I'm missing.
[EDIT: I've created it as a loadable module now: https://github.com/pgimeno/lua-strbit - see testsuite.lua for sample usage]

Is it possible, without using ImageData, to check if a canvas is a solid color? Perhaps some clever use of setShader?

Is there any other fast enough method?

[s-ol]

I'm trying to make a pixel-based collision detector, but every path I take has led to a brick wall. I wonder if someone has any recommendations. The problem is finding if a tile mask intersects the sprite mask. That can be done by bitwise ANDing the masks, or by multiplying (setBlendMode) the alphas or the RGBs, and checking if the result is uniform (all zeros, all transparent, all black) or not.

So, first I tried with a canvas and getImageData. Alas, even with a 1x1 canvas, getImageData causes 100% CPU usage:

Code: Select all

function love.load()
  canvas = love.graphics.newCanvas(1, 1)
end

function love.update(dt)
  canvas:getImageData()
end

(not even garbage collection runs, but that's the least of the problems as it can be run manually).

Maybe ImageData is a view of the canvas that gets updated in real time? Nope, it's a snapshot. That road is closed too.

I haven't tried using tables with the collision bitmap data and bit manipulation, as I figure it would be too slow to do it several times per frame, depending on the tile sizes. So I thought of using strings, since they are binary byte arrays. But I've searched all places I could imagine, and I didn't see any bitwise string manipulation library for Lua: all of them were for numbers, not strings. In PHP (and in Perl, I think) you can do string|string, string^string and string&string. It would be nice if LÖVE included functions to do that, plus bit shift left/right of strings. That would enable me to do the necessary bit manipulation that would probably provide the speed I need.

But since there's currently no such thing, I wonder if there's any other fast alternative that I'm missing.

Is it possible, without using ImageData, to check if a canvas is a solid color? Perhaps some clever use of setShader?

Is there any other fast enough method?

I don't know if there is a better way (I think there should be some way to use canvas' and imagedata) but you can use ffi to write fast binary-handling code; if you get your data into raw images or bitmaps of the same dimensions you should be able to perform the bitwise operations that way.

[pgimeno]

Thank you, that idea seems promising but I fail to see how to use ffi for that purpose. It seems to only handle C declarations and constant expressions, not let you write C functions. To my knowledge, there's no built-in C function to handle the ANDing and shifting of byte arrays that this application would require. Am I missing something?

And yes, I also thought that ImageData would be the way to go, but when applied to a canvas it's far, far too slow. When applied to an image it's fast (or should I say normal), so getting the raw data is not a problem.

[pgimeno]

I've noticed that disabling c.window.vsync in love.conf drastically reduces the CPU consumption of canvas:getImageData. However, it's still quite slow even for tile-sized images, to the point that you still have to run garbage collection manually.

I suspect that the problem is that it should actually be asynchronous, and that the time is spent in waiting for the image to be ready in a polling loop (and the image isn't ready until the frame is rendered, which happens at every vsync when c.window.vsync is on). I don't know OpenGL well enough to be sure about whether my hunch is right and whether it's feasible to implement it as a callback, but if so, it would be nice to have. Something like:

Code: Select all

local function receive_image_data(imagedata, userdata)
    ...
end

    ...
    canvas:requestImageData(receive_image_data, userdata)
    ...

There's some info on what the problem seems to be, here: https://www.opengl.org/wiki/Pixel_Buffer_Object#Utility.

[bobbyjones]

There was some talk of making some functions asynchronous but there is of course the issue of OpenGL not being asynchronous iirc.

[pgimeno]

I've now implemented bitwise operators on the bytes of strings, which should help a great deal with this.

https://github.com/pgimeno/lua-strbit