Show Posts
The aim is to produce shadow effects for 2D games in realtime. A notable example of this in action would be Gish or Hitlers Must Die. Sadly I have nothing to do with the making of those games though.
A demo of what we'll be making:
Click to go to an interactive version.
I do most stuff with Flash so I'll use Actionscript during this, but the principles are general and it could be applied to whatever you like to work with. If you've never met Actionscript you'll be able to read it just fine. I also make use of Box2D's b2vec2 class in some example code. Again no need for you to be familiar with it; it's a pretty standard class to deal with 2D vectors.
The aim of this tutorial is to explain the concepts in use by means of prose, diagrams and code. It'll not give you a finished shadow-drawing engine at the end but it should teach you how to make one yourself, and that's much more fun!
Casting shadows from polygons
Before we can draw the shadow coming from a shape, we need to have the shape represented somehow. Polygons are a good way to do this - it means we represent the shape as a series of connected lines that form a solid 2D shape. The demo above shows a crowd of regular polygons, but it'll work just as well for irregular and even concave polygons. Plenty of games aren't limited to just geometric shapes, but as with collisions and physics it is often useful to simplify shapes to an approximate polygon.
How you store these polygons is something I'll leave up to you as it will depend a great deal on what libraries you're using or what else you have going on in the game. For instance re-using the shadow-casting polygons as collision-detection polygons will often work out as a good solution. In the demo I have used Box2D to handle the physics, so have also used its own representation of the polygons.
Whatever shape our polygon is and however you represent it in code, it'll be constructed of straight lines. The good thing about straight lines is they're nice and simple. So we'll do the shadow casting on individual lines, and build those up into a shadow for the whole polygon.
Shadowing a Line
Here's how we want the shadow from a single line to look, with the orange circle as the light source, and red line as the shadow casting line:
So our task becomes drawing the shape of the shadow, which is given by the points A, B, C, D. Points A and D are already known as they're just the start and end of the line. B and C are quite easily found:
Think of point B as being point A after being moved. But what direction to move it? Easy! Apply the same movement as would be needed to get from L (where the light source is) to A.
To put it in more mathematical terms:
Take the vector L-to-A, and add it to the position vector of A.
To put it in code terms, using the b2vec2 class from Box2D:
Code:
private function projectPoint(point_:b2Vec2, light_:b2Vec2):b2Vec2
{
var lightToPoint:b2Vec2 = point_.Copy();
lightToPoint.Subtract(light_);
var projectedPoint:b2Vec2 = point_.Copy();
projectedPoint.Add(lightToPoint);
return projectedPoint;
}
{
var lightToPoint:b2Vec2 = point_.Copy();
lightToPoint.Subtract(light_);
var projectedPoint:b2Vec2 = point_.Copy();
projectedPoint.Add(lightToPoint);
return projectedPoint;
}
Of course the very same process can be used to find point C from D.
Drawing out the resulting shadow is a simple enough process. Using the .graphics methods of a shape object for instance:
Code:
var shadows:Shape = new Shape();
var projectedPoint:b2Vec2;
shadows.graphics.lineStyle(1, 0, 0);
shadows.graphics.beginFill(0, 1);
shadows.graphics.moveTo(startVertex.x, startVertex.y);
projectedPoint = projectPoint(startVertex, light);
shadows.graphics.lineTo(projectedPoint.x, projectedPoint.y);
projectedPoint = projectPoint(endVertex, light);
shadows.graphics.lineTo(projectedPoint.x, projectedPoint.y);
shadows.graphics.lineTo(endVertex.x, endVertex.y);
shadows.graphics.endFill();
var projectedPoint:b2Vec2;
shadows.graphics.lineStyle(1, 0, 0);
shadows.graphics.beginFill(0, 1);
shadows.graphics.moveTo(startVertex.x, startVertex.y);
projectedPoint = projectPoint(startVertex, light);
shadows.graphics.lineTo(projectedPoint.x, projectedPoint.y);
projectedPoint = projectPoint(endVertex, light);
shadows.graphics.lineTo(projectedPoint.x, projectedPoint.y);
shadows.graphics.lineTo(endVertex.x, endVertex.y);
shadows.graphics.endFill();
Just repeat this process for every line in every polygon, and you'll have the full shadow of the shapes drawn out. Done! Fantastic!
A first optimisation
Now that it works, we can start on the long road of making it faster. If you look carefully at the shadows in the demo you can see that only the lines that are facing away from the light actually influence the shape of the final shadow. This means that we're processing and drawing the shadows for many lines which we don't actually need to.
Here a shape (shown in red) has shadows cast thanks to a lightsource. See how the shadow lines that I have coloured a lighter grey fall entirely within the larger shadow, and so will not affect the final shadow image? We've spent precious time drawing out those shadows, but the player never actually sees the result - what a waste!
The good news is that it's simpler than you might think to determine if it's worth drawing the shadow from a line.
You might notice that it's the lines facing towards the lightsource that we don't need to draw shadows from. Using a little vector maths we can quite easily find which lines are facing the lightsource, and so which are worth drawing shadows for.
You can consider each line as splitting the world into two parts: the world on the left of the line and the world on the right.
Take note that which side is left and which is right will depend on the direction you're considering the line from. So make sure you always consider the lines of your polygons as going from one point to the next along in a clockwise direction (or counterclockwise if you like - just be consistent.)
In this case we're going clockwise, and we can see that for this particular line the lightsource falls on the left hand side. Check the other lines, and you'll find that only lines where the lightsource falls to their right will cast a shadow that actually needs to be drawn.
We can use a little bit more vector mathematics to determine if the lightsource is to the left or right of any particular line:
First we find the normal of the vector that goes from the start to the end of the line, then take the dot product of that and the vector that goes from the lightsource to the start of the line. The dot product will be a number, but we're only interested in if it's positive or negative, as that will indicate what side the lightsource is on.
I'll not try to fully explain the vector maths that just happened, but I'll give a taste. The normal of a vector is a vector that is at right-angles. It's very easy to find - just swap around the x and y components of the vector, and multiply one of them by -1. Which one you multiply by -1 will determine if you get the normal that points to the left of the vector or to the right. Taking the dot product of two vectors gives us a number (not a vector) which can be used for other clever things, but for now all we're worried about is that it is positive if the two vectors point in the same direction, and negative if they point away from one another (and zero if they're perpendicular.)
Effectively we are drawing a new line at right-angles out of the line we're considering, and asking if it points towards the light source. If it does, we know not to bother drawing the shadow for this line.
In code:
Code:
private function doesEdgeCastShadow(start_:b2Vec2, end_:b2Vec2, light_:b2Vec2):Boolean
{
var startToEnd:b2Vec2 = end_.Copy();
startToEnd.Subtract(start_);
var normal:b2Vec2 = new b2Vec2(startToEnd.y, -1 * startToEnd.x);
var lightToStart:b2Vec2 = start_.Copy();
lightToStart.Subtract(light_);
if (dotProduct(normal, lightToStart) < 0)
{
return true;
}
else
{
return false;
}
}
private function dotProduct(vecA_:b2Vec2, vecB_:b2Vec2):Number
{
return (vecA_.x * vecB_.x + vecA_.y * vecB_.y);
}
{
var startToEnd:b2Vec2 = end_.Copy();
startToEnd.Subtract(start_);
var normal:b2Vec2 = new b2Vec2(startToEnd.y, -1 * startToEnd.x);
var lightToStart:b2Vec2 = start_.Copy();
lightToStart.Subtract(light_);
if (dotProduct(normal, lightToStart) < 0)
{
return true;
}
else
{
return false;
}
}
private function dotProduct(vecA_:b2Vec2, vecB_:b2Vec2):Number
{
return (vecA_.x * vecB_.x + vecA_.y * vecB_.y);
}
End
There's still plenty more to cover on the topic; off the top of my head:
Using BlendMode to make shadows be shadows instead of black voids (which is slightly more Flash-centric, although I'm sure you can get the same effect with OpenGL)
Different ways to determine the length of shadows.
Creating a "torch beam" effect.
Dealing with multiple and coloured light sources.
General graphical consistency considerations.
I hope someone will find this part useful at least. Questions, comments? What part was hardest to understand?
If you like, the source for the simple example is available here. There's a FlashDevelop project in there, but the important stuff is just two .as files that can be opened in any text editor. It uses Box2D for the shapes, so if you're not familiar with that then the source may be needlessly confusing.
) pretty fast.
