Here's a tree-based Basic algorithm that reduces the number of multiple visits to cells by about a third.
/*
* 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.lib.fov;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.Set;
abstract public class FieldOfView2dBasic extends FieldOfView2d
{
private static final long serialVersionUID = 1L;
// Rays are precalculated once for each radius and compressed down into
// trees of nodes that we walk along while exploring the field of view.
// This reduces the number of repeat cell visits by about one third.
//
// For speed optimization, we store node trees in a static threadlocal
// map and only calculate them once per thread. The threadlocal allows
// it to be thread-safe without having to deal with lock contention
// issues during map access, even though it uses a little more memory.
// In the future, we might want to let the user select whether to use
// threadlocal maps or a single static synchronized map...
final private static class Fov2dNode
{
private FieldOfView2dCoordinate position;
final private ArrayList<Fov2dNode> leaves = new ArrayList<Fov2dNode>();
}
transient private static ThreadLocal<HashMap<Integer,Fov2dNode>> rootNodes = null;
protected FieldOfView2dBasic()
{
super( true );
}
@Override
final public Set<FieldOfView2dCoordinate> getFieldOfViewFromImpl( FieldOfView2dCoordinate origin, int radius )
{
HashSet<FieldOfView2dCoordinate> results = new HashSet<FieldOfView2dCoordinate>();
initializeNodeTree( radius );
followNode( radius, origin, rootNodes.get().get( radius ), results );
return results;
}
final private void initializeNodeTree( int radius )
{
if( rootNodes == null )
rootNodes = new ThreadLocal<HashMap<Integer,Fov2dNode>>();
HashMap<Integer,Fov2dNode> map = rootNodes.get();
if( map == null )
{
map = new HashMap<Integer,Fov2dNode>();
rootNodes.set( map );
}
Fov2dNode root = map.get( radius );
if( root == null )
{
root = new Fov2dNode();
map.put( radius, root );
root.position = new FieldOfView2dCoordinate( 0, 0 );
// Cast rays, build a sequence of nodes for each ray.
for( int eY = -radius; eY <= radius; eY++ )
{
Fov2dNode currentEast = root;
Fov2dNode currentWest = root;
Fov2dNode currentNorth = root;
Fov2dNode currentSouth = root;
double slope = (double)eY / (double)radius;
for( int x = 0; x <= radius; x++ )
{
int y = (int)( (double)x * slope );
Fov2dNode node;
node = new Fov2dNode();
node.position = new FieldOfView2dCoordinate( x, y );
currentEast.leaves.add( node );
currentEast = node;
node = new Fov2dNode();
node.position = new FieldOfView2dCoordinate( -x, y );
currentWest.leaves.add( node );
currentWest = node;
node = new Fov2dNode();
node.position = new FieldOfView2dCoordinate( y, x );
currentNorth.leaves.add( node );
currentNorth = node;
node = new Fov2dNode();
node.position = new FieldOfView2dCoordinate( y, -x );
currentSouth.leaves.add( node );
currentSouth = node;
}
}
// Recurse through node sequences and merge leaves with duplicate
// coordinates.
mergeNode( root );
}
}
final private static void mergeNode( Fov2dNode node )
{
boolean dup;
do
{
dup = false;
for( Fov2dNode child : node.leaves )
{
for( Fov2dNode dupNode : node.leaves )
{
if( child != dupNode && child.position.equals( dupNode.position ) )
{
for( Fov2dNode n : dupNode.leaves )
child.leaves.add( n );
node.leaves.remove( dupNode );
dup = true;
break;
}
}
if( dup )
break;
}
} while( dup );
for( Fov2dNode child : node.leaves )
mergeNode( child );
}
final private void followNode( int radius, FieldOfView2dCoordinate origin, Fov2dNode node, HashSet<FieldOfView2dCoordinate> results )
{
if( Math.abs( node.position.x() ) <= radius && Math.abs( node.position.y() ) <= radius )
{
FieldOfView2dCoordinate modifiedPosition = new FieldOfView2dCoordinate( origin.x() + node.position.x(), origin.y() + node.position.y() );
results.add( modifiedPosition );
if( !cellIsOpaque( modifiedPosition ) || ( origin.x() == modifiedPosition.x() && origin.y() == modifiedPosition.y() ) )
for( Fov2dNode child : node.leaves )
followNode( radius, origin, child, results );
}
}
}
