next »

[stevesan]

Hi folks,
Just wondering, are there any clever vision-cone algorithms people use for 2D games, like Monaco?



I'm just talking about how the light parts, parts in vision, are affected by the geometry of the level. Are they basically just doing 2D shadow volumes (ie. for each object on-screen that isn't already in-shadow, extrude out a pyramid/trapezoid behind it), or is there a more clever algorithm that people typically use? I know games like Dread and Gateways have similar real-time "vision shadow" cone type things...and they're pretty cool.

--Steve

[owendeery]

This is usually an often cited resource: http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/index.html

[Schrompf]

I'm not sure if there's a "standard" way to do these things. I think you mean how to make things cast shadows on the places behind it. You can do this by extruding edges of occluders, but I didn't like those solutions as the shadows tend to be very sharp.

My game (Splatter) uses a image-based technique vaguely based on Cryteks Radial Blur. In addition to the surface color I also render out the "height" of everything into a separate buffer. The light height minus the surface height divided by the distance gives a "shadow edge" which I can use to test other pixels. If the pixel height is lower than the height of the prolonged edge, the pixel is shadowed. The problem is now that - for a single pixel - you'd need to test all pixels in front of it to know if any of them cast a shadow on the pixel. This is where the "Radial Blur" idea comes into play. I have one shader to check the first 8 pixel heights on the way to the lightsource, and store the largest shadow edge I found in a texture. Then I apply a second pass, but now check every 4th pixels, then another pass with every 16th pixel, and so on. With just 4 passes I get stable shadows across a whole fullHD screen in a 4:1 screen to shadow resolution. And it's so fast that even laptop or onboard GPUs can handle a few shadows.

And with a few more samples you'd even get mostly correct penumbra regions for volume light sources. I've made some tests and collected the results on this image - it's huge, therefore I just put a link. I'm really happy about this technique so please take my words with a grain of salt.

[stevesan]

This is usually an often cited resource: http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/index.html

Great, thanks!

@Schrompf - that sounds cool. I'm not familiar with Radial Blur, but I'll come back to this thread if I ever need sof shadows. Your game looks frikkin awesome btw! A unique look amongst 2D shooters.

[Nix]

Also take a look at the source code of left 4k dead: http://www.mojang.com/notch/j4k/l4kd/

And if you want to see how it might be done in a tile-based environment, roguebasin is a wonderful resource: http://roguebasin.roguelikedevelopment.org/index.php/Field_of_Vision

[rivon]

Here's the explanation of Monaco lighting algorithm straight from Andy Schatz: https://www.facebook.com/note.php?note_id=411301481995

[Fallsburg]

I'm not sure if there's a "standard" way to do these things. I think you mean how to make things cast shadows on the places behind it. You can do this by extruding edges of occluders, but I didn't like those solutions as the shadows tend to be very sharp.

My game (Splatter) uses a image-based technique vaguely based on Cryteks Radial Blur. In addition to the surface color I also render out the "height" of everything into a separate buffer. The light height minus the surface height divided by the distance gives a "shadow edge" which I can use to test other pixels. If the pixel height is lower than the height of the prolonged edge, the pixel is shadowed. The problem is now that - for a single pixel - you'd need to test all pixels in front of it to know if any of them cast a shadow on the pixel. This is where the "Radial Blur" idea comes into play. I have one shader to check the first 8 pixel heights on the way to the lightsource, and store the largest shadow edge I found in a texture. Then I apply a second pass, but now check every 4th pixels, then another pass with every 16th pixel, and so on. With just 4 passes I get stable shadows across a whole fullHD screen in a 4:1 screen to shadow resolution. And it's so fast that even laptop or onboard GPUs can handle a few shadows.

And with a few more samples you'd even get mostly correct penumbra regions for volume light sources. I've made some tests and collected the results on this image - it's huge, therefore I just put a link. I'm really happy about this technique so please take my words with a grain of salt.

A similarish method is described here.  It is an image based method that does jump flooding, so it takes log2(n) (where n is your resolution) passes.  It will typically be slower than the standard geometry based method, but if you either have very complex geometry (i.e. a lot of edges to check) or a lot of objects that will cast shadows then the image based method will shine because it is agnostic of those things.

[stevesan]

Here's the explanation of Monaco lighting algorithm straight from Andy Schatz: https://www.facebook.com/note.php?note_id=411301481995

Awesome - that's exactly what I was looking for.

[Schrompf]

A similarish method is described here.  It is an image based method that does jump flooding, so it takes log2(n) (where n is your resolution) passes.  It will typically be slower than the standard geometry based method, but if you either have very complex geometry (i.e. a lot of edges to check) or a lot of objects that will cast shadows then the image based method will shine because it is agnostic of those things.

Interesting find, thank you! Albeit not exactly what I'm doing - my technique doesn't need a distortion pass, and I get proper penumbra regions for volume light sources, but both techniques end up with O(log n). It's a good job for GPUs, but I reckon it's a bit uncomfortable if you need the exact same information on the CPU for gameplay. I do the gameplay-relevant shadow checks as separate ray casts on the CPU.