Physical Queries for the Math Challenged: Real-time Shadows

Posted by Alex Schearer on Sunday, September 28, 2008 · Leave a Comment

Recently I’ve been working on a new game whose gameplay is centered around shadows. This meant that I needed to implement a shadow system which could:

Generate “realistic” shadows for objects
Allow for shadows to be cast at different angles
Be efficient

Of course, I wanted to avoid all the complex math which tends to creep in with real-time shadows. In order to do this I needed to accept some constraints:

Work with shadows, not light sources
Have little control over intensities
Objects simply extend in 3rd dimension

After implementing the system in my game I thought it might be useful for others. This post is going to cover the steps necessary to add simple real-time shadows to your game.

Casting a Shadow

What’s a shadow? For our purposes a shadow is the projection of a 3d object onto a 2d plane. That’s right, a 3d object. Most likely, your game objects are 2d, so you’ll need to add a new property to them. How about doing this formally like so:

interface ShadowCaster {
    /** Returns the object's "depth". */
    public int getZIndex();
    /** Calculate and return the object's shadow. */
    public Shape castShadow(float direction);
}

So, we have an interface which defines any object which can have a shadow. For convenience, I usually let objects with no shadow return null when castShadow is called so I can still easily leverage polymorphism. The z-index is important for two reasons. It is used in calculating the shadow and it is useful for sorting objects along the z-axis.

Next up let’s take a look at an implementation of castShadow. The following is for a square object. Underlying the object is a Shape derived from java.awt.Shape (specifically, it’s a Slick shape).

public Shape castShadow(float direction) {
    Vector2f v = Geom.calculateVector(getZIndex(), direction);

    Transform t = Transform.createTranslateTransform(v.x, v.y);
    Polygon extent = (Polygon) shape.transform(t);

    int index = findKeyPoint(v);

    Polygon shade = new Polygon();
    // adds points to the polygon except the key point
    for (int i = 1; i < 4; i++) {
        int c = (4 + index + i) % 4;
        float[] p = extent.getPoint(c);
        shade.addPoint(p[0], p[1]);
    }
    // as above, except this time with corresponding key point
    for (int i = 3; i > 0; i--) {
        int c = (4 + index + i) % 4;
        float[] p = shape.getPoint(c);
        shade.addPoint(p[0], p[1]);
    }

    return shade;
}

As you can see I project a certain distance based on its z-index and the direction of the light. After that I create a polygon using three points from the shape and from the projection. Let’s take a look at how I determine which points to use:

/**
 * Given two rectangles, a block and its shadow, the key point is the corner
 * on the shadow closest to the block. The second key point is the corner on
 * the block furthest from the shadow. One can be derived from the other.
 */
private int findKeyPoint(Vector2f v) {
    int index = 0;

    if (v.y > 0) { // bottom
        if (v.x > 0) { // right
            index = 0;
        } else { // left
            index = 1;
        }
    } else { // top
        if (v.x > 0) { // right
            index = 3;
        } else { // left
            index = 2;
        }
    }
    return index;
}

Simple, huh? At first I tried to find a mathematical relationship between two points to determine what the key point was but that ended in failure. So I did what any sane person would do and just mapped out what I knew intuitively with conditional statements. I know which points to leave out based on which direction the shadow was projected.

So there you have it. The greater the object’s z-index the longer the shadow it casts, and the direction passed to castShadow determines which way the shadow will be cast.

Creating a Shadowscape

Now that we’ve got objects and shadows we need to start thinking about how to render everything. In Shade most of the game objects were above the shadows. Therefore, I needed to render the shadowscape followed by the game objects. I also wanted to render game objects according to their z-index so that taller ones would be rendered over shorter ones. To accomplish these things I created two data objects.

First, there is the shadowscape. You probably noticed that castShadow returns a Shape. This is so I can collect all the shadows and render them in one pass. After that I make a second pass to render each of the game objects.

At it’s most basic the shadowscape has a single method:

public void render(Graphics g) {
    Color shade = Color.black;
    shade.a = SHADOW_ALPHA;
    g.setColor(shade);
    for (Shape s : shadows) {
        g.fill(s);
    }
    g.setColor(Color.white);
}

Where shadows is a collection containing the product of castShadow for each game object. In addition to a shadowscape I created a ZBuffer. This is a simple collection which orders objects by their z-index. Finally, I put everything together with a ShadowLevel which renders things like so:

public void render(StateBasedGame game, Graphics g) {
    shadowscape.render(g);
    for (ShadowCaster s : buffer) {
        s.render(game, g);
    }
}

This renders the shadowscape first then all of the game objects. This approach works well if your game is top-down like Shade. If you’re working on a platformer you would probalby want to take a different approach. Most likely you’d want to render the object and it’s shadow together instead of separating them into two passes.

That’s that! I hope you’ve found this helpful. If you have more questions or would like to see the source code behind Shade (and referenced in this tutorial) then please see:

Shade Project

As always feel free to use any of the code in this example, and be sure to let me know what comments or thoughts you’ve got!

Tags: