Simple Shadow Casting in 2D
Unaccordingly to my plan I spent yesterday rewriting my shadow casting routines.
What I need is a frustum, or flashlight type of light source. Before, I had solved this by first drawing a full circle onto which I drew masking triangles, carving out the frustum pie. This mask was very expensive to draw (imagine a small frustum, then the mask would be huge in order to cover the non-pie circle parts).
Drawing the light
My new approach is far from optimal, but way better. Instead of carving out the view cone, I only draw the cone as the light once, then I apply shadows to this. In order to draw this pie I used line segments, so pie end is not circular, but made up of n line segments covering the light radius. See the jacked arc in image below (outlines by the red line).
Here is the core of drawing the pie:
const rd:int = left.crossDet(right) > 0 ? -1 : 1; const rotDir:int = (lightBody.getFovDeg() > 180) ? -1 * rd : rd; const spinor:Vec2Const = new Vec2(1, 0).rotateSelf(Conv.deg2rad(15) * rotDir); const parts:int = lightBody.getFovDeg() / 15; const g:Graphics = _lightData.graphics; g.beginGradientFill(GradientType.RADIAL, [0xffffff, 0x000000], [0.3, 0], [0, 255], matrix); g.moveTo(0, 0); g.lineTo(right.x, right.y); _tmp.copy(right); while (parts-- > 0) { _tmp.rotateSpinorSelf(spinor); g.lineTo(_tmp.x, _tmp.y); } g.lineTo(left.x, left.y); g.lineTo(0, 0); g.endFill();
In short, the vector left is the left frustum “tentacle” and right the other. The arc is drawn in the while loop. The next segment in the arc is calculated by simply rotating the right vector one step at a time, until we have covered the pie all the way to the left vector (parts times of segments). The nifty thing with spinors is that you don’t have to leave vector space for rotations. The spinor is only created once, in this case with 15 degrees, then each time it’s applied to a vector the vector is rotated by 15 degrees. So instead of fiddling with sin and cos you can just apply it by multiplication. This is more efficient and clean. If you are interested you can find the rotateSpinor methods in my vector 2d class.
Drawing the shadows
Once the light is in place it’s time to apply the shadows over it. This is done by projecting rays through each “extreme” wall vertex as far as the light source can reach. An extreme vertex is one that is the “right or left”-most point with respect to the light source. Then it’s just to draw the shadow between each such ray pair and close it up with the same arc as drawn for the light pie above.
Here are the shadows, outlined with yellow lines:
Here is the algorithm outline:
1. For each obstacle within the frustum view
2. – Find the two extreme points (if we are only looking at Axis Aligned Bounding Boxes the simplest way is probably to check in which octant the light source is.)
3. – Draw a line between those two extreme points
4. – Draw lines from the extremes in the direction of the light passing through until it hits the frustum end.
5. – Connect the end points from (4) by drawing an arc (same way as described under “Drawing the light”).
6. – Fill this area with a shadowy color
Once this has been accomplished, I set the blendMode of the sprite to ADD – in this way two light sources interacts in a decent manner. The problem with setting the blendMode is that it’s very slow.
The result
You can run around with a 360 deg light bulb on your head. Don’t worry about the other bots as you have cleverly disguised yourself as one of them for this experiment. (Use ARROWS)
Possible improvements
The biggest performance hit with this method is due to the blendMode. A solution would probably be to only draw the light (absense of light = shadow) This can be achieved by scanning each vertex in one direction creating a light area while moving along. Imagine standing in front of a couple of walls at different distances – then taking a laser gun that has a burning continuous beam, and while holding the trigger turning. This will leave a burnt lines along the walls and everything it hits – if there are no walls the beam will hit an imaginary frustum back wall. Once you are done with turning you can look at this area, outlined by the burnt lines (and start & stop dir) from above and fill this area with light – and you are done.
With this approach you aren’t drawing any shadows (e.g. black) so interactions with other lightsources in shadows will work (instead of overdrawing a light with a shadow) without having to use a blendMode. You probably have to tweak the alpha values to get this to look decent (perhaps it’s hard to to get it as nice as with blendMode.ADD?).
Well perhaps there is a simpler way of doing this but this is the first I came to think of?
Hey,
I’d like to thank you for this. I am working on a little game myself and this really helped me out planning the algorithm.
Thanks, good luck with your game!
Could you share the full source for this project?
I’m studiyng AS3 at Högskolan på Gotland, and are getting more and more interested in AI and the shadowcasting shown here, but especially the movement of the AI.
Hi, cool! Sorry don’t have time to package the source, it’s kind of using a large code base and I don’t want to share all that right now. I hope you understand. Lycka till!
Ok i understand, no worries! Looking forward to more inspiration from this blog, and would love to see more tutorials.
Keep up the great work you’re doing, och tack 🙂
I have created my very own shadow casting implementation from scratch. I can have multiple lights and everything. But I want to know if there is a way where If the shadows are added to the lights. How can I get the boxes/shadowcasters to be hidden unless their is a light nearby?
Basically I want the player to only see the environment under the light source.
Not sure if I follow, but can’t you just hide stuff (walls, boxes, shadowcasters) that isn’t in light (or in the players frustum)?
Basically, I want all shadowcasters to be on blendMode.multiply.(At least it looks good that way) So when the gradient light graphic is getting closer to the shadowcaster, they slowly fades into view from black(Or whatever the background color is). I can get it that way, but when I do the shadows that are under the shadowcasters “multiply” with the shadowcaster above causing the shadow to appear above the shadowcaster. The shadowcaster fades in nicely it’s just the shadow is still supposed to appear below.
I could mask everything with one big mask and add every light to it, but I don’t really want to do it that way, it doesn’t look as nice and I have to change everything around, because the mask ruins the gradient of the graphic and I’d have twice the light graphics on screen, I’d prefer not to go that way.