Shadows!

[Riukuzaki]

The next version of the game that will be going live will have... shadows! Yay!


I actually managed to do this without any noticeable change in loading times (ha!) for chunks. Slick has this really neat thing that lets you pass a "filter" color when rendering an image, like a block. The filter is perfect for things like rendering underwater, rendering special glow effects, and rendering shadows. I stumbled upon it out of necessity today when my previous implementation was too slow.

On another note, can anyone tell me what algorithm this is? I'm not naive enough to believe I was the first to come up with this. It's what I use for rendering the shadows:

    /**
     * A recursive helper for the relaxation algorithm.
     * Note:  There is an optimization available.  We don't need to check the direction
     * that we're coming from.
     * @param superLightMatrix
     * @param x
     * @param y
     */
    private void relaxLightMatrixHelper(int [][]superLightMatrix, int x, int y) {
        // Correct top
        if (y > 0 && superLightMatrix[x][y-1] > superLightMatrix[x][y] + 1) {
            superLightMatrix[x][y-1] = superLightMatrix[x][y] + 1;
            relaxLightMatrixHelper(superLightMatrix, x, y-1);
        }
        
        // Correct bottom
        if (y + 1 < superLightMatrix[x].length && superLightMatrix[x][y+1] > superLightMatrix[x][y] + 1) {
            superLightMatrix[x][y+1] = superLightMatrix[x][y] + 1;
            relaxLightMatrixHelper(superLightMatrix, x, y+1);
        }
        
        // Correct left
        if (x > 0 && superLightMatrix[x-1][y] > superLightMatrix[x][y] + 1) {
            superLightMatrix[x-1][y] = superLightMatrix[x][y] + 1;
            relaxLightMatrixHelper(superLightMatrix, x-1, y);
        }
    }
    
    private void relaxLightMatrix(int [][]superLightMatrix, int x, int y) {
        // Do special case
        for (int i=y; i > 0 && superLightMatrix[x][i-1] > superLightMatrix[x][i] + 1; --i) {
            superLightMatrix[x][i-1] = superLightMatrix[x][i] + 1;
        }
        // Recursively correct top, bottom, and left after moving left
        if (x > 0 && superLightMatrix[x-1][y] > superLightMatrix[x][y] + 1) {
            superLightMatrix[x-1][y] = superLightMatrix[x][y] + 1;
            relaxLightMatrixHelper(superLightMatrix, x-1, y);
        }
    }
    
    /**
     * Populates the light matrix with my own algorithm.  (Does it have a name?)
     * Is this the best way to do it?
     */
    private void populateLightMatrix() {
        final int depth = WorldConstants.WORLD_BLOCK_SHADOW_DEPTH; // The max depth that light penetrates.
        final int chunkWidth = WorldConstants.WORLD_CHUNK_WIDTH;
        final int chunkHeight = WorldConstants.WORLD_CHUNK_HEIGHT;
        int [][]superLightMatrix = new int[chunkWidth + depth * 2 - 2][chunkHeight + depth * 2 - 2];
        TerrainSession ts = Game.getInstance().getClient().getTerrainSession();
        final long baseX = getX() * WorldConstants.WORLD_CHUNK_WIDTH;
        final long baseY = getY() * WorldConstants.WORLD_CHUNK_HEIGHT;
        
        for (int x=0; x < superLightMatrix.length; ++x) {
            for (int y=0; y < superLightMatrix[x].length; ++y) {
                Block b = ts.getBlock(new BoundLocation(baseX + x - depth + 1, baseY + y - depth + 1), false);
                if (b != null && !b.isCollidable()) { // Light source
                    relaxLightMatrix(superLightMatrix, x, y);
                } else { // Not a light source
                    superLightMatrix[x][y] = y > 0 && superLightMatrix[x][y-1] < depth-1 ? 
                            superLightMatrix[x][y-1] + 1 : depth;
                    if (x > 0 && superLightMatrix[x-1][y] < superLightMatrix[x][y]-1) {
                        superLightMatrix[x][y] = superLightMatrix[x-1][y] + 1;
                    }
                }
            }
        }
        // Copy from the super matrix
        for (int i=0; i < lightMatrix.length; ++i) {
            for (int j=0; j < lightMatrix.length; ++j) {
                lightMatrix[i][j] = superLightMatrix[i + depth - 1][j + depth - 1];
            }
        }
    }

Note: I am certainly aware that this method could be improved by keeping track of the source of the light when relaxing the light matrix and then calculating with the hypotenuse instead of just doing +1 and -1. I might do this later, because it makes a big difference on looks (you'll get what you see in the screenshot above) without any change in O-complexity.

[Riukuzaki]

The finished version of my shadow rendering (as of now) can be found below. Let me know what you think.
For now shadows will be enabled by default. Once I get the configuration menu finished, you will be able to enable / disable shadows at will.