The Bitmap has transparency, and only non-transparent pixels are solid and used for hit detection for the physics engine and gameplay.
I have seen some versions done with convex hulls, but for multiple reasons I am not using convex hulls to build the levels in my game.
How can I implement 2d shadows on a level made out of a Dynamic Bitmap?
The answer jpaver posted is good, but I am sure there are some other ways to do this. Does anyone else have any more information on this question?
This is only one way to approach the problem.
For each source pixel in your bitmap, ray march towards the pixel that currently represents the light source. If you hit a non-transparent pixel along the way, stop marching and assign a shadow value to your source pixel. If you reach the light pixel, the source pixel is lit.
As you can probably tell, marching and testing every pixel along the way for every source pixel can get expensive, especially when adding multiple lights. Fortunately, there are things that can be done:
assign a bounding circle to your light. Before marching, test if the pixel is inside or outside of this circle radius. If it's outside, it's considered in shadow by default and there is no need to march. If it's inside, do the ray march. If the ray march yields that the pixel is lit, use a falloff function to determine how bright it is. (side note: interesting falloff functions can be derived to make your lights flicker and animate)
To avoid marching and testing every pixel, pre-compute a distance field for your static bitmap. The distance field simply stores the distance to the closest opaque pixel for every pixel. Then when marching along a ray, you look at the distance field, and are guaranteed to hit no opaque pixels by stepping that amount. (side note: you can use these distance fields for your physics too).
EDIT: to answer comment about dynamic updating problem:
If you have a dynamic bitmap field, updating the distance field is a bit of a pain. I'm sure there are clever techniques for doing this out there, I'm just not versed in them. Someone else is free to comment here if they are in the know! :)
An alternative technique to accelerate your ray marching is to use an tiled hierarchy that encodes your empty space in a much more efficient way. You can precompute the hierarchy from your original level bitmap, and only need to update parts of it when you add or remove opaque pixels.
So what does the hierarchy look like? If your original data of size MxN is mip0, then:
The higher mips store whether there is any opaque geometry in the lower mip level pixels. If you wanted to update mip[k] at pixel(i,j), you'd probably do something like this:
mip[k].opaque[i][j] = mip[k-1].opaque[i*2][j*2] ||
mip[k-1].opaque[i*2+1][j*2] ||
mip[k-1].opaque[i*2][j*2+1] ||
mip[k-1].opaque[i*2+1][j*2+1];
Once you have the data structure computed, you can march your ray directly to the edge of a tile if that tile contains no opaque pixels. Your algorithm would look like this:
(extreme pseudo-code)
void StepOnce(int &x, int &y, int xDir, int yDir)
{
int k = COARSEST_MIP;
while (k > 0)
{
int x_in_mip = x >> k;
int y_in_mip = y >> k;
if (!mip[k].opaque[i_in_mip][j_in_mip])
{
// Here we can step (i,j) to the next tile for mip(k)
// (I'll leave the math as an exercise to the reader)
return; // exit since we've stepped once
}
else
{
// go to a finer level tile.
k--;
}
}
// do the math to step once.
return
}
Updating this structure is simply a matter of tracking a dirty region (ie. rectangle) for level 0 every frame. Once you've accumulated all changes, just update those pixels falling in the dirty region and update higher levels that touch that region too.
Note: if you're doing this on CPU, you may want to:
The answer to the following question has a link you might find very useful : How is 2D lighting implemented?
