Package squidpony.squidgrid

Class Adjacency

java.lang.Object
squidpony.squidgrid.Adjacency
All Implemented Interfaces:
Serializable
Direct Known Subclasses:
Adjacency.BasicAdjacency, Adjacency.RotationAdjacency
public abstract class Adjacency
extends Object
implements Serializable
Some classes need detailed information about what cells are considered adjacent to other cells, and may need to construct a customized mapping of cells to their neighbors. Implementations of this abstract class provide information about all sorts of things, including the distance metric (from DijkstraMap), but also the maximum number of states that can be moved to in one step (including rotations at the same point in space, in some cases), and whether the type of map uses a "two-step" rule that needs two sequential moves in the same direction to be viable and unobstructed to allow movement (which is important in thin-wall maps).
When CustomDijkstraMap and similar classes need to store more information about a point than just its (x,y) position, they also use implementations of this class to cram more information in a single int. This abstract class provides methods to obtain four different numbers from a single int, though not all implementations may provide all four as viable options. It also provides a utility to get a Coord from an int. X and Y are exactly what they always mean in 2D Coords, R is typically used for rotation, and N is typically used for anything else when it is present. The convention is to use N for the Z-axis when elevation/depth should be tracked, or for any more specialized extensions to the information carried at a point. The composite() method produces a compressed int from X, Y, R, and N values, and the validate() method allows code to quickly check if an int is valid data this class can use. Other information is tracked by fields, such as height, width, rotations, and depths, where the maximum number of possible states is given by height * width * rotations * depths, and the minimum for any of these int fields is 1.
Lastly, the neighborMaps() method produces very important information about what neighbors each cell has, and by modifying the returned int[][], you can produce "portal" effects, wraparound, and other useful concepts. The value it returns consists of an array (with length == maxAdjacent) of arrays (each with the same size, length == width * height * rotations * depth). The values in the inner arrays can be any int between 0 and (width * height * rotations * depth), which refers to the index in any of the inner arrays of a neighboring cell, or can be -1 if there is no neighbor possible here (typically at edges or corners of the map, some of the neighbors are not valid and so use -1). In normal usage, a for loop is used from 0 to maxAdjacent, and in each iteration the same index is looked up (the current cell, encoded as by composite() or obtained as an already-composited neighbor earlier), and this normally gets a different neighbor every time. In methods that do a full-map search or act in a way that can possibly loop back over an existing cell in the presence of wrapping (toroidal or "modulus" maps) or portals, you may want to consider tracking a count of how many cells have been processed and terminate any processing of further cells if the count significantly exceeds the number of cells on the map (terminating when 4 times the cell count is reached may be the most extreme case for very-portal-heavy maps). Created by Tommy Ettinger on 8/12/2016.
See Also:
Serialized Form

  • Nested Class Summary

    Nested Classes 
    Modifier and Type Class Description
    static class  Adjacency.BasicAdjacency  
    static class  Adjacency.RotationAdjacency  
    static class  Adjacency.ThinWallAdjacency  

  • Field Summary

    Fields 
    Modifier and Type Field Description
    int blockingRule
    If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make single-cell diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move.
    IntDoubleOrderedMap costRules
    Used in place of a double[][] of costs in CustomDijkstraMap; allows you to set the costs to enter tiles (via addCostRule(char, double) or addCostRule(char, double, boolean) if the map has rotations).
    int depths
    Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.
    Direction[] directions
    The array of all possible directions this allows, regardless of cost.
    int height
    Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.
    int[] invertAdjacent  
    int maxAdjacent
    The maximum number of states that can be considered adjacent; when rotations are present and have a cost this is almost always 3 (move forward, turn left, turn right), and in most other cases this is 4 (when using Manhattan distance) or 8 (for other distance metrics).
    Measurement measurement
    This affects how distance is measured on diagonal directions vs.
    int rotations
    Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.
    protected boolean standardCost  
    boolean twoStepRule
    Only needed for thin-wall maps; this requires two steps in the same direction to both be valid moves for that direction to be considered, and always moves the pathfinder two steps, typically to cells with even numbers for both x and y (where odd-number-position cells are used for edges or corners between cells, and can still be obstacles or possible to pass through, but not stay on).
    int width
    Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.

  • Constructor Summary

    Constructors 
    Constructor Description
    Adjacency()  

  • Method Summary

    Modifier and Type Method Description
    IntDoubleOrderedMap addCostRule​(char tile, double cost)  
    abstract IntDoubleOrderedMap addCostRule​(char tile, double cost, boolean isRotation)  
    abstract int composite​(int x, int y, int r, int n)
    Encodes up to four components used by this Adjacency, putting them into one int.
    Coord extractCoord​(int data)  
    abstract int extractN​(int data)  
    abstract int extractR​(int data)  
    abstract int extractX​(int data)  
    abstract int extractY​(int data)  
    boolean hasStandardCost()  
    abstract boolean isBlocked​(int start, int direction, int[][][] neighbors, double[] map, double wall)  
    int move​(int start, int x, int y)  
    int move​(int start, int x, int y, int r, int n)  
    abstract int[][][] neighborMaps()  
    abstract void portal​(int[][][] neighbors, int inputPortal, int outputPortal, boolean twoWay)  
    IntDoubleOrderedMap putAllVariants​(IntDoubleOrderedMap map, int key, double value)  
    abstract IntDoubleOrderedMap putAllVariants​(IntDoubleOrderedMap map, int key, double value, int size)  
    void putAllVariants​(IntVLA list, double[] map, int key, double value)  
    abstract void putAllVariants​(IntVLA list, double[] map, int key, double value, int size)  
    void resetAllVariants​(double[] map, int[] keys, double[] values)  
    void resetAllVariants​(double[] map, int[] keys, double[] values, int size)  
    abstract void resetAllVariants​(double[] map, int[] keys, int usable, double[] values, int size)  
    String show​(int data)  
    String showMap​(int[] map, int r)  
    abstract boolean validate​(int data)  

    Methods inherited from class java.lang.Object

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

  • Field Details

    • directions

      public Direction[] directions
      The array of all possible directions this allows, regardless of cost.

    • maxAdjacent

      public int maxAdjacent
      The maximum number of states that can be considered adjacent; when rotations are present and have a cost this is almost always 3 (move forward, turn left, turn right), and in most other cases this is 4 (when using Manhattan distance) or 8 (for other distance metrics).

    • twoStepRule

      public boolean twoStepRule
      Only needed for thin-wall maps; this requires two steps in the same direction to both be valid moves for that direction to be considered, and always moves the pathfinder two steps, typically to cells with even numbers for both x and y (where odd-number-position cells are used for edges or corners between cells, and can still be obstacles or possible to pass through, but not stay on).

    • blockingRule

      public int blockingRule
      If you want obstacles present in orthogonal cells to prevent pathfinding along the diagonal between them, this can be used to make single-cell diagonal walls non-viable to move through, or even to prevent diagonal movement if any one obstacle is orthogonally adjacent to both the start and target cell of a diagonal move.
      If this is 0, as a special case no orthogonal obstacles will block diagonal moves.
      If this is 1, having one orthogonal obstacle adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. This generally blocks movement around corners, the "hard corner" rule used in some games.
      If this is 2, having two orthogonal obstacles adjacent to both the current cell and the cell the pathfinder is trying to diagonally enter will block diagonal moves. As an example, if there is a wall to the north and a wall to the east, then the pathfinder won't be able to move northeast even if there is a floor there.
      A similar effect can be achieved with a little more control by using thin walls, where the presence of a "thin corner" can block diagonal movement through that corner, or the absence of a blocking wall in a corner space allows movement through it.

    • measurement

      public Measurement measurement
      This affects how distance is measured on diagonal directions vs. orthogonal directions. MANHATTAN should form a diamond shape on a featureless map, while CHEBYSHEV and EUCLIDEAN will form a square. EUCLIDEAN does not affect the length of paths, though it will change the DijkstraMap's gradientMap to have many non-integer values, and that in turn will make paths this finds much more realistic and smooth (favoring orthogonal directions unless a diagonal one is a better option).

    • width

      public int width
      Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.

    • height

      public int height
      Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.

    • rotations

      public int rotations
      Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.

    • depths

      public int depths
      Can be changed if the map changes; you should get the neighbors from neighborMaps() again after changing this.

    • standardCost

      protected boolean standardCost

    • costRules

      public IntDoubleOrderedMap costRules
      Used in place of a double[][] of costs in CustomDijkstraMap; allows you to set the costs to enter tiles (via addCostRule(char, double) or addCostRule(char, double, boolean) if the map has rotations). A cost of 1.0 is normal for most implementations; higher costs make a movement harder to perform and take more time if the game uses that mechanic, while lower costs (which should always be greater than 0.0) make a move easier to perform. Most games can do perfectly well with just 1.0 and 2.0, if they use this at all, plus possibly a very high value for impossible moves (say, 9999.0 for something like a submarine trying to enter suburbia).
      You should not alter costRules in most cases except through the Adjacency's addCostRule method; most Adjacency implementations will set a flag if any cost is set through addCostRule that is different from the default, and this flag determines early-stop behavior in pathfinding (it can be checked with hasStandardCost(), but cannot be set directly).
      Adjacency implementations are expected to set a reasonable default value for when missing keys are queried, using IntDoubleOrderedMap.defaultReturnValue(double); there may be a reason for user code to call this as well.

    • invertAdjacent

      public int[] invertAdjacent

  • Constructor Details

  • Method Details