Package squidpony.squidgrid

Class LOS

java.lang.Object
squidpony.squidgrid.LOS
All Implemented Interfaces:
Serializable
public class LOS
extends Object
implements Serializable
Line of Sight (LOS) algorithms find if there is or is not a path between two given points.
The line found between two points will end at either the target, the obstruction closest to the start, or the edge of the map.
For normal line of sight usage, you should prefer Bresenham lines, and these are the default (they can also be specified by passing BRESENHAM to the constructor). For more specialized usage, there are other kinds of LOS in this class, like lines that make no diagonal moves between cells (using ORTHO, or lines that check a wide path (but these use different methods, like thickReachable(Radius)).
Performance-wise, all of these methods are rather fast and about the same speed. RAY is a tiny fraction faster than BRESENHAM but produces rather low-quality lines in comparison. Calculating the visibility of 40,000 lines in a 102x102 dungeon takes within 3% of 950ms (on an Intel i7-4700MQ laptop processor) for every one of BRESENHAM, DDA, ORTHO, and RAY, even with ORTHO finding a different kind of line by design.
Author:
Eben Howard - http://squidpony.com - howard@squidpony.com, Tommy Ettinger Added DDA, ORTHO, and the thick lines; some cleanup, smelC optimized several methods
See Also:
Serialized Form

  • Field Summary

    Fields 
    Modifier and Type Field Description
    static int BRESENHAM
    A Bresenham-based line-of-sight algorithm.
    static int DDA
    Optimized algorithm for Bresenham-like lines.
    static int ELIAS
    Uses Wu's Algorithm as modified by Elias to draw the line.
    static int ORTHO
    Draws a line using only North/South/East/West movement.
    static int RAY
    Uses a series of rays internal to the start and end point to determine visibility.
    static int THICK
    Draws a line as if with a thick brush, going from a point between a corner of the starting cell and the center of the starting cell to the corresponding corner of the target cell, and considers the target visible if any portion of the thick stroke reached it.

  • Constructor Summary

    Constructors 
    Constructor Description
    LOS()
    Constructs an LOS that will draw Bresenham lines and measure distances using the CIRCLE radius strategy.
    LOS​(int type)
    Constructs an LOS with the given type number, which must equal a static field in this class such as BRESENHAM.

  • Method Summary

    Modifier and Type Method Description
    ArrayDeque<Coord> getLastPath()
    Returns the path of the last LOS calculation, with the starting point as the head of the queue.
    Radius getRadiusStrategy()
    Gets the radius strategy this uses.
    boolean isReachable​(char[][] walls, int startx, int starty, int targetx, int targety)
    Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
    boolean isReachable​(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy)
    Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
    boolean isReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety)
    Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
    boolean isReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy)
    Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
    void setRadiusStrategy​(Radius radiusStrategy)
    Set the radius strategy to the given Radius; the default is CIRCLE if this is not called.
    boolean spreadReachable​(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread)
    Returns true if a line can be drawn from the any of the points within spread cells of the start point, to any of the corresponding points at the same direction and distance from the target point, without intervening obstructions.
    boolean spreadReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread)
    Returns true if a line can be drawn from the any of the points within spread cells of the start point, to any of the corresponding points at the same direction and distance from the target point, without intervening obstructions.

    Methods inherited from class java.lang.Object

    clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

  • Field Details

    • BRESENHAM

      public static final int BRESENHAM
      A Bresenham-based line-of-sight algorithm.
      See Also:
      Constant Field Values

    • ELIAS

      public static final int ELIAS
      Uses Wu's Algorithm as modified by Elias to draw the line. Does not end at an obstruction but rather returns one of the possible attempted paths in full.
      See Also:
      Constant Field Values

    • RAY

      public static final int RAY
      Uses a series of rays internal to the start and end point to determine visibility. Appearance is extremely close to DDA, which is also probably a faster algorithm, so BRESENHAM (which can look a little better) and DDA are recommended instead of RAY.
      See Also:
      Constant Field Values

    • ORTHO

      public static final int ORTHO
      Draws a line using only North/South/East/West movement.
      See Also:
      Constant Field Values

    • DDA

      public static final int DDA
      Optimized algorithm for Bresenham-like lines. There are slight differences in many parts of the lines this draws when compared to Bresenham lines, but it may also perform significantly better, and may also be useful as a building block for more complex LOS. Virtually identical in results to RAY, and just a hair slower, but better-tested and more predictable.
      See Also:
      Constant Field Values

    • THICK

      public static final int THICK
      Draws a line as if with a thick brush, going from a point between a corner of the starting cell and the center of the starting cell to the corresponding corner of the target cell, and considers the target visible if any portion of the thick stroke reached it. Will result in 1-width lines for exactly-orthogonal or exactly-diagonal lines and some parts of other lines, but usually is 2 cells wide.
      See Also:
      Constant Field Values

  • Constructor Details

    • LOS

      public LOS()
      Constructs an LOS that will draw Bresenham lines and measure distances using the CIRCLE radius strategy.

    • LOS

      public LOS​(int type)
      Constructs an LOS with the given type number, which must equal a static field in this class such as BRESENHAM.
      Parameters:
      type - an int that must correspond to the value of a static field in this class (such as BRESENHAM)

  • Method Details

    • getRadiusStrategy

      public Radius getRadiusStrategy()
      Gets the radius strategy this uses.
      Returns:
      the current Radius enum used to measure distance; starts at CIRCLE if not specified

    • setRadiusStrategy

      public void setRadiusStrategy​(Radius radiusStrategy)
      Set the radius strategy to the given Radius; the default is CIRCLE if this is not called.
      Parameters:
      radiusStrategy - a Radius enum to determine how distances are measured

    • isReachable

      public boolean isReachable​(char[][] walls, int startx, int starty, int targetx, int targety)
      Returns true if a line can be drawn from the start point to the target point without intervening obstructions. Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy .
      Parameters:
      walls - '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • isReachable

      public boolean isReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety)
      Returns true if a line can be drawn from the start point to the target point without intervening obstructions. Does not take into account resistance less than opaque or distance cost. Uses RadiusStrategy.CIRCLE, or whatever RadiusStrategy was set with setRadiusStrategy .
      Parameters:
      resistanceMap - 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • isReachable

      public boolean isReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy)
      Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
      Parameters:
      resistanceMap - 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      radiusStrategy - the strategy to use in computing unit distance
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • isReachable

      public boolean isReachable​(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy)
      Returns true if a line can be drawn from the start point to the target point without intervening obstructions.
      Parameters:
      walls - '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      radiusStrategy - the strategy to use in computing unit distance
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • spreadReachable

      public boolean spreadReachable​(char[][] walls, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread)
      Returns true if a line can be drawn from the any of the points within spread cells of the start point, to any of the corresponding points at the same direction and distance from the target point, without intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath.
      Parameters:
      walls - '#' is fully opaque, anything else is fully transparent, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      radiusStrategy - the strategy to use in computing unit distance
      spread - the number of cells outward, measured by radiusStrategy, to place extra start and target points
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • spreadReachable

      public boolean spreadReachable​(double[][] resistanceMap, int startx, int starty, int targetx, int targety, Radius radiusStrategy, int spread)
      Returns true if a line can be drawn from the any of the points within spread cells of the start point, to any of the corresponding points at the same direction and distance from the target point, without intervening obstructions. Primarily useful to paint a broad line that can be retrieved with getLastPath.
      Parameters:
      resistanceMap - 0.0 is fully transparent, 1.0 is fully opaque, as always this uses x,y indexing.
      startx - starting x position on the grid
      starty - starting y position on the grid
      targetx - ending x position on the grid
      targety - ending y position on the grid
      radiusStrategy - the strategy to use in computing unit distance
      spread - the number of cells outward, measured by radiusStrategy, to place extra start and target points
      Returns:
      true if a line can be drawn without being obstructed, false otherwise

    • getLastPath

      public ArrayDeque<Coord> getLastPath()
      Returns the path of the last LOS calculation, with the starting point as the head of the queue.
      Returns:
      the last path found during LOS calculation, as a ArrayDeque of Coord with the starting point at the head