Related:<p>1) a tutorial on the same topic by Red Blob Games: <a href="http://www.redblobgames.com/articles/visibility/" rel="nofollow">http://www.redblobgames.com/articles/visibility/</a><p>2) a public domain Javascript visibility polygon library that runs in O(n log n), which is actually used in the Nothing to Hide game: <a href="https://code.google.com/p/visibility-polygon-js/" rel="nofollow">https://code.google.com/p/visibility-polygon-js/</a><p>3) a blog post by author of said library discussing the algorithm: <a href="http://byronknoll.blogspot.ca/2013/05/on-log-n.html" rel="nofollow">http://byronknoll.blogspot.ca/2013/05/on-log-n.html</a><p>Shooting a ray to every vertex and then naively computing intersections takes O(n^2) since there are n rays with up to O(n) intersections each. It is interesting to read and think about O(n log n) algorithms for computing the visibility polygon.
You, sir, must be from the future, what with the uncopyrighted, bitcoin-based crowdfunding campaign. Backing this effort is a no-brainer.<p><a href="https://back.nothingtohide.cc/" rel="nofollow">https://back.nothingtohide.cc/</a>
Nice article. However I think there's a better algorithm: the one actually used in Doom from Id Software.<p>First the scene must be put into a 2d bsp (that requires slicing some edge). After that, the bsp must be traversed front-to-back and that gives the edges in the right order. Just keep track of which angles are occluded then while traversing. During the process, when an edge is proccessed, cast/create the shadow accordingly. The algorithm stop when the field of vision is fully occluded - and not farther.
Very cool article. Providing actual working demos for each step makes the technique a lot easier to explain to others.<p>I had fun implementing this effect a long time, in a pre-graphics-shader era [1].<p>[1] <a href="https://github.com/shurcooL/eX0#screenshots" rel="nofollow">https://github.com/shurcooL/eX0#screenshots</a>
Really cool tutorial. It also looks like the author has a pledge drive ending today, and he/she is really close to hitting their funding goal. Would be a shame to miss it while being so close, especially for something that looks so promising.<p>(Note: I have no connection to this developer. Just thought it was worth mentioning.)
Nice example, but ray casting like this is overkill for this effect and with a low number of rays it's pretty inaccurate.<p>I prefer using the technique shown in this classic article on 2D soft shadows:
<a href="http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/" rel="nofollow">http://archive.gamedev.net/archive/reference/programming/fea...</a><p>The basic idea is to project the geometry, rather than ray cast. I've implemented this sort of technique in the past and it works well.
I have an open source XNA/MonoGame implementation of a similar lighting technique available here:<p><a href="https://github.com/sq/Illuminant" rel="nofollow">https://github.com/sq/Illuminant</a><p>It's hardware-accelerated and has a few other useful features; we're using it in Escape Goat 2 and it works on Windows/Linux/Mac on pretty much any D3D9-spec hardware. You can see some of the levels using it here: <a href="https://www.youtube.com/watch?v=-9s1PyotS18#t=1m20s" rel="nofollow">https://www.youtube.com/watch?v=-9s1PyotS18#t=1m20s</a><p>For EG2 we have a pair of separate lighting environments; one for the foreground plane and one for the background plane. Most light sources exist on both planes but have different parameters in order to create a depth effect; some light sources are only on the background plane. We apply a customized ramp texture to the light sources in order to replace the smooth attenuation with quantized attenuation, and we don't use soft shadows (though we do render lighting at a lower resolution and upscale it, because that softens things a little.) We also do a simple HDR camera model by sampling lighting intensity across the scene's foreground/background planes and using that to adjust the range of the final lightmap so that we can automatically tune exposure/white point etc to highlight certain parts of a level.<p>I also have a similar pure-software-rendering lighting library from around ~8 years ago available here, in C++:<p><a href="https://github.com/kg/Fury2/blob/master/libraries/SoftFX/module/Fury2.cpp#L2708" rel="nofollow">https://github.com/kg/Fury2/blob/master/libraries/SoftFX/mod...</a><p>That one's garbage, but may still be of some use.<p>I'll note that the author's approach (needing extra intersection points at +- 0.00001 radian) is a little perplexing. I'm not sure why that is needed; I've never needed it.<p>A better approach for 'fuzzy' shadows is to model the penumbra; you can render it as a single triangle that borders on the actual shadow umbra and then make it smooth by using a simple lookup texture. This technique is described here:<p><a href="http://archive.gamedev.net/archive/reference/programming/features/2dsoftshadow/page4.html" rel="nofollow">http://archive.gamedev.net/archive/reference/programming/fea...</a><p>Another great option for 2D lighting is to associate normal maps with your sprites and do per-pixel lighting against each light source using the normal map. This can produce some really great results. I think that SpriteLamp, <a href="http://snakehillgames.com/spritelamp/" rel="nofollow">http://snakehillgames.com/spritelamp/</a> does this; the Fury2 library I linked above also did per-pixel sprite lighting with normal maps. The upcoming game Full Bore (<a href="http://www.wholehog-games.com/fullbore/" rel="nofollow">http://www.wholehog-games.com/fullbore/</a>) is using per-pixel lighting on its sprites and environment art, and I believe Spelunky for PC/XBLA uses it on environment art.
I'm kinda tired of the "cone-of-vision" mechanic and associated visual effect common in modern 2D games. In traditional 2D games, being able to see things that are not visible to the player's avatar is, IMO, a significant part of the charm. Not being restricted to a realistic viewpoint lets you become the larger-than-life hero of cartoons and cheesy action movies that does impossible things like leaping into a room full of bad guys and shooting them all before they have a chance to react, or "sensing" someone behind him and dodging the arrow at the last second. When you make a 2D game that tries to "realistically" limit the player's view, you're getting the downsides of <i>both</i> 2D and 3D games. It says to me, "I really wanted to make an FPS but I don't know how."<p>No criticism is intended towards OP's game; the "un-stealth game" is a different and interesting idea. I'm just throwing it out there for those dreaming up yet another top-down cone-of-vision stealth shooter to chew on.
this is interesting (although this sort of effect has never mystified me) - i can't help but think how this can be optimised. the steps gone through here are things i never would have done and the final solution is about where i would start...<p>just blindly tracing to all of the verts 'feels wrong' its the sort of thing that is intuitively unreasonable with large data sets and is quite obviously going to be constrained by available horsepower at some size.<p>precomputed vis data is the obvious optimisation and removes the O(n) behaviour. not only do you not have to test everypoint but your raycast itself need not test every edge. i wrote something ages ago about generating PVS in 2d as an example of how to approach the problem in 3D...<p>(<a href="http://jheriko-rtw.blogspot.co.uk/2011/05/visibility-determination-with-convex.html" rel="nofollow">http://jheriko-rtw.blogspot.co.uk/2011/05/visibility-determi...</a>)<p>the other thing that bugs me here is the jitter. it is the classic 'lazy' way to soften shadows... a better effect can be gotten for less - if you offset the light position perpendicular to the direction toward the test vert, in both directions by the same amount then you can generate two ray casts. triangulating the resulting mesh might be a little painful (unless you cut the world into convex chunks - then it is nearly trivial) but you will get the outline for both edges of the shadow and can then do something like vertex interpolated colour to give you the same visual result as infinite raycasts for the price of two...