Recursive shadowcasting wrong in wiki?

[DavidD]

Hey there! I just registered so I'd like to say hey to the roguelike community!

Anyway, I read this article on the wiki. However, it seems that there's a bug in there somewhere. If you look at this picture I'm sure you'd understand:

http://imgur.com/okvVB

In the top picture, the algorithm works as expected, but when 2 tiles are added like in the second picture (the vertical wall doesn't matter, i exaggerated it) it acts weird and that's not at all the way I'd like it to look.

It's the same on all 4 sides. So it's the code posted in my link that's a bit faulty as a whole.

Is there an updated version or is it just like that?

This is my first octant just to show my syntax, all the other ones are the same except for a few other values

Code: [Select]

           int x = 0;
            int y = 0;

            switch (octant)
            {
                case 1:
                    y = playerPosition.Y - depth;
                    x = (int)Math.Round(playerPosition.X - startSlope * depth);

                    if (x < 0)
                        break;
                    if (x >= mapDimensions.X)
                        break;
                    if (y < 0)
                        break;
                    if (y >= mapDimensions.Y)
                        break;
                    
                    while (GetSlope(x, y, playerPosition.X, playerPosition.Y) >= endSlope)
                    {
                        if (IsWithinVisualRange(playerPosition.X, playerPosition.Y, x, y))
                        {
                            if (map[y][x].BlocksVision)
                            {
                                //if (TestCell(x - 1, y, playerPosition.X, playerPosition.Y, false, depth))
                                if(!map[y][x - 1].BlocksVision)
                                    RecursiveScan(playerPosition, depth + 1, octant, startSlope, GetSlope(x - 0.5, y + 0.5, playerPosition.X, playerPosition.Y));

                                lightMap[y][x] = 1;
                                visitedMap[y][x] = true;
                            }
                            else
                            {
                                //if (TestCell(x - 1, y, playerPosition.X, playerPosition.Y, true, depth))
                                if(map[y][x - 1].BlocksVision)
                                    startSlope = GetSlope(x - 0.5, y - 0.5, playerPosition.X, playerPosition.Y);

                                lightMap[y][x] = 1;
                                visitedMap[y][x] = true;
                            }
                        }
                        x++;
                    }
                    x--;

[Leaf]

Shadow casting is weird like that...  It's a tradeoff between accuracy and visual appeal.

You may have better luck with restrictive precise angle shadow casting.  Java, but I am sure you can adapt it to the language of your choice.  This code is not thread-safe (unless of course you use a different instance in each thread).

Don't forget to post-process to make visible any walls adjacent to any visible floors.

Code: (java) [Select]

/*
 * Copyright (c) 2011, L. Adamson / Dizzy Dragon Games. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * We'd love to hear from you if you're using this software for something or
 * have any questions or comments. You can contact us at via email at
 * support@dizzydragon.net.
 */

package retrocrawl.engine.game.visionandmovement;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.Set;

abstract public class FieldOfView2dRpas extends FieldOfView2d
{
private static final long serialVersionUID = 1L;

// This value can be 1, 2, or 3.  It indicates the number of angles that
// must be blocked before a cell is considered opaque.
final private static int PERMISSIVENESS = 2;

// This value spreads the start and end angles a little wider than usual.
// This acts somewhat like permissiveness, but is a more fine-grained
// control.  It helps to eliminate some visual artifacts.
final private static float OUTER_ANGLE_SWEEP = 0.2f;

final private static class AngleRange
{
private float startAngle;
private float endAngle;

private AngleRange( float startAngle, float endAngle )
{
this.startAngle = startAngle;
this.endAngle = endAngle;
}
}

protected FieldOfView2dRpas()
{
super( true );
}

final private ArrayList<AngleRange> blockedAngles = new ArrayList<AngleRange>();

final private boolean isBlockedAngle( float angle )
{
for( AngleRange ar : blockedAngles )
{
if( angle >= ar.startAngle && angle <= ar.endAngle )
{
return true;
}
}
return false;
}

@Override
final public Set<FieldOfView2dCoordinate> getFieldOfViewFromImpl( FieldOfView2dCoordinate origin, int radius )
{
HashSet<FieldOfView2dCoordinate> results = new HashSet<FieldOfView2dCoordinate>();
results.add( origin );
for( boolean flip = false; ; flip = true )
{
for( int xdir = -1; xdir <= 1; xdir += 2 )
{
for( int ydir = -1; ydir <= 1; ydir += 2 )
{
blockedAngles.clear();
boolean lineOpen = true;
for( int line = 1; line <= radius && lineOpen; line++ )
{
lineOpen = false;
for( int cell = 0; cell <= line; cell++ )
{
int x;
int y;
if( flip )
{
x = line*xdir;
y = cell*ydir;
}
else
{
x = cell*xdir;
y = line*ydir;
}
float range = 1.0f/(float)(line+1);
float startAngle = range * (float)(cell);
float midAngle = startAngle + range*0.5f;
float endAngle = startAngle + range;
startAngle -= range * OUTER_ANGLE_SWEEP;
endAngle += range * OUTER_ANGLE_SWEEP;
int nBlockedAngles = 0;
if( isBlockedAngle(startAngle) )
nBlockedAngles++;
if( isBlockedAngle(midAngle) )
nBlockedAngles++;
if( isBlockedAngle(endAngle) )
nBlockedAngles++;
FieldOfView2dCoordinate coordinate = new FieldOfView2dCoordinate(origin.x()+x, origin.y()+y);
if( nBlockedAngles < PERMISSIVENESS )
{
results.add( coordinate );
lineOpen = true;
}
if( cellIsOpaque(coordinate) )
blockedAngles.add( new AngleRange(startAngle,endAngle) );
}
}
}
}
if( flip )
break;
}
return results;
}
}
(This parent class just does some caching and the post-process filtering.  The algorithm in the first class is the one you want.)

Code: (java) [Select]

/*
 * Copyright (c) 2011, L. Adamson / Dizzy Dragon Games. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 *
 * Redistributions of source code must retain the above copyright notice, this
 * list of conditions and the following disclaimer.
 *
 * Redistributions in binary form must reproduce the above copyright notice,
 * this list of conditions and the following disclaimer in the documentation
 * and/or other materials provided with the distribution.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS"
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT HOLDER OR CONTRIBUTORS BE
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE)
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE
 * POSSIBILITY OF SUCH DAMAGE.
 *
 * We'd love to hear from you if you're using this software for something or
 * have any questions or comments. You can contact us at via email at
 * support@dizzydragon.net.
 */

package retrocrawl.engine.game.visionandmovement;

import java.io.Serializable;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;

abstract public class FieldOfView2d implements Serializable
{
private static final long serialVersionUID = 1L;

final public static class FieldOfView2dCoordinate implements Serializable
{
private static final long serialVersionUID = 1L;

private int x;
private int y;

/**
* Instantiates a new FieldOfView2dCoordinate with the specified x and y values.
*
* @param x
*            the x coordinate
* @param y
*            the y coordinate
*/
public FieldOfView2dCoordinate( int x, int y )
{
this.x = x;
this.y = y;
}

/**
* @return the x value of this coordinate.
*/
public int x()
{
return x;
}

/**
* @return the y value of this coordinate.
*/
public int y()
{
return y;
}

@Override
public int hashCode()
{
return x ^ Integer.reverse( y );
}

@Override
public boolean equals( Object o )
{
if( o instanceof FieldOfView2dCoordinate )
return ( (FieldOfView2dCoordinate)o ).x == x && ( (FieldOfView2dCoordinate)o ).y == y;
return false;
}

@Override
public String toString()
{
return x + "," + y;
}
}

private boolean requiresPostProcessing = false;
final private HashMap<FieldOfView2dCoordinate,Boolean> opaqueCells = new HashMap<FieldOfView2dCoordinate,Boolean>();
final private HashMap<FieldOfView2dCoordinate,Boolean> cellContainsData = new HashMap<FieldOfView2dCoordinate,Boolean>();

protected FieldOfView2d( boolean requiresPostProcessing )
{
this.requiresPostProcessing = requiresPostProcessing;
}

abstract protected Set<FieldOfView2dCoordinate> getFieldOfViewFromImpl( FieldOfView2dCoordinate origin, int radius );

abstract protected boolean cellIsOpaqueImpl( FieldOfView2dCoordinate coordinate );

abstract protected boolean cellContainsDataImpl( FieldOfView2dCoordinate coordinate );

final protected boolean cellIsOpaque( int x, int y )
{
return cellIsOpaque( new FieldOfView2dCoordinate(x,y) );
}

final protected boolean cellIsOpaque( FieldOfView2dCoordinate coordinate )
{
Boolean isOpaque = opaqueCells.get( coordinate );
if( isOpaque == null )
{
isOpaque = cellIsOpaqueImpl( coordinate );
opaqueCells.put( coordinate, isOpaque );
}
return isOpaque;
}

final protected boolean cellContainsData( int x, int y )
{
return cellContainsData( new FieldOfView2dCoordinate(x,y) );
}

final protected boolean cellContainsData( FieldOfView2dCoordinate coordinate )
{
Boolean containsData = cellContainsData.get( coordinate );
if( containsData == null )
{
containsData = cellContainsDataImpl( coordinate );
cellContainsData.put( coordinate, containsData );
}
return containsData;
}

final public Set<FieldOfView2dCoordinate> getFieldOfViewFrom( FieldOfView2dCoordinate origin, int radius )
{
opaqueCells.clear();
cellContainsData.clear();
Set<FieldOfView2dCoordinate> results = getFieldOfViewFromImpl( origin, radius );
if( requiresPostProcessing )
{
// This filter ensures that opaque cells cardinally adjacent to
// non-opaque cells are drawn.
HashSet<FieldOfView2dCoordinate> resultsBuf = new HashSet<FieldOfView2dCoordinate>( results );
for( FieldOfView2dCoordinate c : resultsBuf )
{
if( !cellIsOpaque(c) )
{
for( int d = -1; d<=1; d += 2 )
{
FieldOfView2dCoordinate c2;
c2 = new FieldOfView2dCoordinate(c.x()+d,c.y());
if( cellIsOpaque(c2) && cellContainsData(c2) )
results.add( c2 );
c2 = new FieldOfView2dCoordinate(c.x(),c.y()+d);
if( cellIsOpaque(c2) && cellContainsData(c2) )
results.add( c2 );
}
}
}
// This filter ensures that ordinal corners next to two adjacent
// cardinal opaque cells which are next to a non-opaque cell in
// a convex fashion are drawn.  (That is, it gets rid of the
// missing corner syndrome.)
resultsBuf = new HashSet<FieldOfView2dCoordinate>( results );
for( FieldOfView2dCoordinate c : resultsBuf )
{
if( !cellIsOpaque(c) )
{
for( int dy=-1; dy<=1; dy+=2 )
{
for( int dx=-1; dx<=1; dx+=2 )
{
FieldOfView2dCoordinate c2 = new FieldOfView2dCoordinate(c.x()+dx,c.y()+dy);
if( cellContainsData(c2) && cellIsOpaque(c2) )
{
FieldOfView2dCoordinate c3a = new FieldOfView2dCoordinate(c2.x()-dx,c2.y());
FieldOfView2dCoordinate c3b = new FieldOfView2dCoordinate(c2.x(),c2.y()-dy);
if( cellIsOpaque(c3a) && resultsBuf.contains( c3a ) && cellContainsData(c3a) && cellIsOpaque(c3b) && resultsBuf.contains( c3b ) && cellContainsData(c3b) )
results.add( c2 );
}
}
}
}
}
}
opaqueCells.clear(); // Allow entries to be GCed.
cellContainsData.clear(); // Allow entries to be GCed.
return results;
}

final public Set<FieldOfView2dCoordinate> getFieldOfViewFrom( int x, int y, int radius )
{
return getFieldOfViewFrom( new FieldOfView2dCoordinate(x,y), radius );
}
}

[corremn]

I am more interested in your graphics? Your own?

[DavidD]

Thank you Leaf! It's very nice of you to provide a code sample! Is it as fast as the recursive method?

Yes corremn, I made those. They're more of a placeholder until we can get a better graphics artist,  though this is a school project so they don't really have to be top-notch. I'm not really a great artist but I wanted to try it out since I'll have to make my own because I don't know anyone who can draw. Practice makes perfect, eh?

[Leaf]

It should be faster in general than a similar implementation done recursively.  Iteration is almost always faster than recursion (every time you call or return from a method, a stack frame gets either pushed on or popped off the runtime stack behind the scenes.  This is a relatively expensive operation compared to the simple integer increments usually associated with iterative operations.

A bigger factor will be the access time of the structures you are storing your data in.  The algorithm I posted is suboptimal from the standpoint of adding all the visible points to a results collection that has to be iterated over again when you draw the cells, and that it makes calls to abstract methods to look into your data structures.

I wrote it that way so it'd be pretty much plug-n-play into other people's code, though.  Extend the class, implement a couple of abstract methods, bang done.

If you wanted to optimize for speed, you could instead process the points as soon as they are found, rather than adding them to the results set (this will make it process the |1.0| slope diagonals twice, though).  You could also inline the stuff that is currently being handled by those abstract *Impl methods to remove some more stack overhead (though I suspect that the optimizer is probably inlining them anyway).  Small gains could probably also be made if you were clever enough to convert the whole thing to use integer math instead of floats, though the prospect of doing that makes my head hurt too much for the small gains I think it would produce.

If ya want my (possibly stinky) opinion though, be careful to avoid falling into the premature optimization pit.   Write your game using the clearest, most straightforward code possible to begin with, even if it's slower.  Then later on run it through a profiler if you have to, identify the parts that are actually producing bottlenecks, and optimize only those parts, and only as much as gives a real efficiency improvement at a fair tradeoff of readability.  It's a heck of a lot easier to maintain slower but clearly written code 12 months later after you've forgotten how it works, resulting in fewer bugs over the life of the product....

Indeed, I like to make a copy of the clean code before I optimize it.  Typically I leave it in the same source file, commented out.  Then if a bug needs fixed in there later, I roll back to the unoptimized code, fix the bug, and then reoptimize it.

Anyway, that's the Leaf Rant for today. ;P  Sorry for rambling on at such length, lol.

[Leaf]

They're more of a placeholder until we can get a better graphics artist,  though this is a school project so they don't really have to be top-notch. I'm not really a great artist but I wanted to try it out since I'll have to make my own because I don't know anyone who can draw. Practice makes perfect, eh?

I think your graphics look pretty cool.  But if you really don't like them, google "rltiles".  Decent-ish public domain 32x32 tiles for Crawl and Nethack.

[DavidD]

It should be faster in general than a similar implementation done recursively.  ... Sorry for rambling on at such length, lol.

I do just that! No worries. We're using SVN so I just commit before making any big changes and then I can just revert if the shit hits the fan. Thanks for the tips though!

[corremn]

yeah I like your tiles too. I've never had the guts to try, it sure beats having a game that looks like someone elses.

[DavidD]

yeah I like your tiles too. I've never had the guts to try, it sure beats having a game that looks like someone elses.

Oh? Really? I think they're really ugly... I just filled it with a dark gray, then I painted with some brighter gray, added noise and voilà! Same with the wall.

[tiger_eye]

Shadow casting is weird like that...  It's a tradeoff between accuracy and visual appeal.

No, it's not.  The original post is correct: the recursive shadowcasting code on the wiki is apparently incorrect if it behaves as he showed.  Also, if you're doing recursive shadowcasting in C, then there is no reason whatsoever to switch to a different algorithm based on speed alone.  It should be amply fast enough (even if you don't do the fastest possible implementation).

Anyway, here are a couple quick fixes to your code that should bring you closer to a properly working recursive shadowcasting algorithm:

Code: [Select]

            int x = 0;
            int y = 0;

            switch (octant)
            {
                case 1:
                    y = playerPosition.Y - depth;
                    x = (int)Math.Round(playerPosition.X - startSlope * depth);

                    if (x < 0)
                        break;
                    if (x >= mapDimensions.X)
                        break;
                    if (y < 0)
                        break;
                    if (y >= mapDimensions.Y)
                        break;

                    while (GetSlope(x, y, playerPosition.X, playerPosition.Y) >= endSlope)
                    {
                        if (IsWithinVisualRange(playerPosition.X, playerPosition.Y, x, y))
                        {
                            if (map[y][x].BlocksVision)
                            {
                                //if (TestCell(x - 1, y, playerPosition.X, playerPosition.Y, false, depth))
                                if(!map[y][x - 1].BlocksVision)  // TODO!  Don't do the below on the very first iteration.
                                    RecursiveScan(playerPosition, depth + 1, octant, startSlope, GetSlope(x - 0.5, y + 0.5, playerPosition.X, playerPosition.Y));

                                lightMap[y][x] = 1;
                                visitedMap[y][x] = true;
                            }
                            else
                            {
                                //if (TestCell(x - 1, y, playerPosition.X, playerPosition.Y, true, depth))

                                // MODIFIED!
                                if(map[y][x - 1].BlocksVision)
                                {
                                    startSlopeNext = GetSlope(x - 0.5, y - 0.5, playerPosition.X, playerPosition.Y);
                                    if (startSlope < startSlopeNext)
                                    {
                                        startSlope = startSlopeNext;
                                        if (startSlope > endSlope)
                                            break;
                                    }
                                }
                                lightMap[y][x] = 1;
                                visitedMap[y][x] = true;
                            }
                        }
                        x++;
                    }

                    // ADDED!
                    if(!map[y][x].BlocksVision)
                    {
                        if (map[y][x + 1].BlocksVision)
                        {
                            endSlopeNext = GetSlope(x + 0.5, y + 0.5, playerPosition.X, playerPosition.Y);
                            if (endSlopeNext < endSlope)
                                endSlope = endSlopeNext;
                        }
                        RecursiveScan(playerPosition, depth + 1, octant, startSlope, endSlope, playerPosition.X, playerPosition.Y));
                    }


[DavidD]

Code: [Select]

RecursiveScan(playerPosition, depth + 1, octant, startSlope, endSlope, playerPosition.X, playerPosition.Y));
Are you sure about that? The method looks like this:

Code: [Select]

public static void RecursiveScan(Point playerPosition, int depth, int octant, double startSlope, double endSlope)
Here's another call earlier

Code: [Select]

RecursiveScan(playerPosition, depth + 1, octant, startSlope, GetSlope(x - 0.5, y + 0.5, playerPosition.X, playerPosition.Y));
Should I use the same slope as earlier in the code?

[tiger_eye]

Nope and nope.  Copy/paste error on my part.  I guess the end of the case should probably be:

Code: [Select]

                        }
                        x++;
                    }
                    x--;
                   
                    // ADDED!
                    if (map[y][x + 1].BlocksVision)
                    {   
                        endSlopeNext = GetSlope(x + 0.5, y + 0.5, playerPosition.X, playerPosition.Y);
                        if (endSlopeNext < endSlope)
                            endSlope = endSlopeNext;
                    }since the recursive call is done after all the switch/cases in the example code on the wiki.  This is a minor check, but still necessary for fully proper behavior.  I think with the way you're doing the rounding, you iterate over a grid if the constraining slope intersects with a full-width diamond within a tile.  Obstructions, on the other hand, are treated as squares.  This code checks whether endSlope intersects with a blocked tile (full square) that it didn't otherwise iterate over b/c it didn't intersect with the diamond within the tile and adjusts endSlope as necessary.