Package squidpony.squidgrid

Class MultiSpill

java.lang.Object
squidpony.squidgrid.MultiSpill
public class MultiSpill
extends Object
A randomized flood-fill implementation that can be used for level generation (e.g. filling ponds and lakes), for gas propagation, or for all sorts of fluid-dynamics-on-the-cheap. Created by Tommy Ettinger on 4/7/2015.

  • Field Summary

    Fields 
    Modifier and Type Field Description
    protected GreasedRegion anyFreshMap
    The cells that are filled by the any spiller will be true, others will be false.
    protected GreasedRegion anySpillMap
    The cells that are filled by the any spiller will be true, others will be false.
    int filled
    The amount of cells filled by this Spill, which may be less than the volume passed to start() if the boundaries are reached on all sides and the Spill has no more room to fill.
    int height
    Height of the map.
    Measurement measurement
    This affects how distance is measured on diagonal directions vs.
    boolean[][] physicalMap
    Stores which parts of the map are accessible (with a value of true) and which are not (with a value of false, including both walls and unreachable sections of the map).
    IRNG rng
    The IRNG used to decide how to randomly fill a space; can have its state set and read.
    short[][] spillMap
    The cells that are filled by the a spiller with index n when it reaches its volume or limits will be equal to n; others will be -1.
    ArrayList<ArrayList<Coord>> spreadPattern
    Each key here is an initial point for a spiller passed to start(), and each value corresponds to a list of points that the spiller will randomly fill, starting with the key, in order of when they are reached.
    int width
    Width of the map.

  • Constructor Summary

    Constructors 
    Constructor Description
    MultiSpill()
    Construct a Spill without a level to actually scan.
    MultiSpill​(char[][] level)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile.
    MultiSpill​(char[][] level, char alternateWall)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where one char means a wall and anything else is a walkable tile.
    MultiSpill​(char[][] level, Measurement measurement)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile.
    MultiSpill​(char[][] level, Measurement measurement, IRNG random)
    Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile.
    MultiSpill​(long state)
    Construct a Spill without a level to actually scan.
    MultiSpill​(short[][] level)
    Used to construct a Spill from the output of another.
    MultiSpill​(short[][] level, Measurement measurement)
    Used to construct a Spill from the output of another, specifying a distance calculation.
    MultiSpill​(short[][] level, Measurement measurement, IRNG random)
    Used to construct a Spill from the output of another, specifying a distance calculation and RNG.
    MultiSpill​(IRNG random)
    Construct a Spill without a level to actually scan.
    MultiSpill​(IStatefulRNG random)
    Construct a Spill without a level to actually scan.

  • Method Summary

    Modifier and Type Method Description
    MultiSpill initialize​(char[][] level)
    Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    MultiSpill initialize​(char[][] level, char alternateWall)
    Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
    MultiSpill initialize​(short[][] level)
    Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently.
    void reset()
    Resets this Spill to a state with an empty spillMap and an empty spreadPattern.
    void resetCell​(int x, int y)
    Reverts a cell to an unfilled state (false in spillMap).
    void resetCell​(Coord pt)
    Reverts a cell to an unfilled state (false in spillMap).
    void resetMap()
    Resets the spillMap to being empty.
    protected void setFresh​(int idx, int x, int y)  
    protected void setFresh​(int idx, Coord pt)  
    ArrayList<ArrayList<Coord>> start​(List<Coord> entries, int volume, Collection<Coord> impassable)
    Recalculate the spillMap and return the spreadPattern.
    ArrayList<ArrayList<Coord>> start​(OrderedMap<Coord,​Double> entries, int volume, Collection<Coord> impassable)
    Recalculate the spillMap and return the spreadPattern.

    Methods inherited from class java.lang.Object

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

  • Field Details

    • 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. If you only call Spill.start() once, you should strongly prefer MANHATTAN, even if the rest of the game uses another measurement, because CHEBYSHEV and EUCLIDEAN can produce odd, gap-filled flood-fills. Any case where you have too many gaps can be corrected to varying extent by calling start() more than once with slowly increasing values. Because start() will extend from the existing area of the Spill, holes are likely to be filled after a few calls, but if the last call to start() tries to fill too many more cells than the previous one, it can cause holes on the periphery of the Spill area.

    • physicalMap

      public boolean[][] physicalMap
      Stores which parts of the map are accessible (with a value of true) and which are not (with a value of false, including both walls and unreachable sections of the map). Should not be changed unless the actual physical terrain has changed. You should call initialize() with a new map instead of changing this directly.

    • spillMap

      public short[][] spillMap
      The cells that are filled by the a spiller with index n when it reaches its volume or limits will be equal to n; others will be -1.

    • anySpillMap

      protected GreasedRegion anySpillMap
      The cells that are filled by the any spiller will be true, others will be false.

    • anyFreshMap

      protected GreasedRegion anyFreshMap
      The cells that are filled by the any spiller will be true, others will be false.

    • spreadPattern

      public ArrayList<ArrayList<Coord>> spreadPattern
      Each key here is an initial point for a spiller passed to start(), and each value corresponds to a list of points that the spiller will randomly fill, starting with the key, in order of when they are reached.

    • height

      public int height
      Height of the map. Exciting stuff. Don't change this, instead call initialize().

    • width

      public int width
      Width of the map. Exciting stuff. Don't change this, instead call initialize().

    • filled

      public int filled
      The amount of cells filled by this Spill, which may be less than the volume passed to start() if the boundaries are reached on all sides and the Spill has no more room to fill.

    • rng

      public IRNG rng
      The IRNG used to decide how to randomly fill a space; can have its state set and read.

  • Constructor Details

    • MultiSpill

      public MultiSpill()
      Construct a Spill without a level to actually scan. If you use this constructor, you must call an initialize() method before using this class.

    • MultiSpill

      public MultiSpill​(IRNG random)
      Construct a Spill without a level to actually scan. This constructor allows you to specify an RNG, but the actual RandomnessSource the RNG that this object uses will not be identical to the one passed as random (64 bits will be requested from the passed RNG, and that will be used to seed this class' RNG). If you use this constructor, you must call an initialize() method before using this class.
      Parameters:
      random - an RNG that will be converted to a StatefulRNG if it is not one already

    • MultiSpill

      public MultiSpill​(long state)
      Construct a Spill without a level to actually scan. This constructor allows you to specify the state to be used for the RNG without actually passing an RNG, since this will use its own anyway. If you use this constructor, you must call an initialize() method before using this class.
      Parameters:
      state - the state to use for this class' random number generator

    • MultiSpill

      public MultiSpill​(IStatefulRNG random)
      Construct a Spill without a level to actually scan. This constructor allows you to specify an IStatefulRNG that will be used exactly, without copying the generator. This permits using GWTRNG instead of the default StatefulRNG if optimal performance on GWT is desirable at the expense of some performance on desktop. If you use this constructor, you must call an initialize() method before using this class.
      Parameters:
      random - an IStatefulRNG that will be used exactly, without copying

    • MultiSpill

      public MultiSpill​(short[][] level)
      Used to construct a Spill from the output of another.
      Parameters:
      level - a short[][] that should have been the spillMap of another MultiSpill

    • MultiSpill

      public MultiSpill​(short[][] level, Measurement measurement)
      Used to construct a Spill from the output of another, specifying a distance calculation.
      Parameters:
      level - a short[][] that should have been the spillMap of another MultiSpill
      measurement - a Spill.Measurement that should usually be MANHATTAN

    • MultiSpill

      public MultiSpill​(short[][] level, Measurement measurement, IRNG random)
      Used to construct a Spill from the output of another, specifying a distance calculation and RNG.
      This constructor allows you to specify an RNG, but the actual RandomnessSource the RNG that this object uses will not be identical to the one passed as random (64 bits will be requested from the passed RNG, and that will be used to seed this class' RNG).
      Parameters:
      level - a short[][] that should have been the spillMap of another MultiSpill
      measurement - a Spill.Measurement that should usually be MANHATTAN

    • MultiSpill

      public MultiSpill​(char[][] level)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here.
      Parameters:
      level - a char[][] that should use '#' for walls and '.' for floors

    • MultiSpill

      public MultiSpill​(char[][] level, char alternateWall)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where one char means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. You can specify the character used for walls.
      Parameters:
      level - a char[][] that should use alternateWall for walls and '.' for floors
      alternateWall - the char to use for walls

    • MultiSpill

      public MultiSpill​(char[][] level, Measurement measurement)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. This constructor specifies a distance measurement.
      Parameters:
      level - a char[][] that should use '#' for walls and '.' for floors
      measurement - a Spill.Measurement that should usually be MANHATTAN

    • MultiSpill

      public MultiSpill​(char[][] level, Measurement measurement, IRNG random)
      Constructor meant to take a char[][] returned by DungeonBoneGen.generate(), or any other char[][] where '#' means a wall and anything else is a walkable tile. If you only have a map that uses box-drawing characters, use DungeonUtility.linesToHashes() to get a map that can be used here. This constructor specifies a distance measurement.
      This constructor allows you to specify an RNG, but the actual RandomnessSource the RNG that this object uses will not be identical to the one passed as random (64 bits will be requested from the passed RNG, and that will be used to seed this class' RNG).
      Parameters:
      level - a char[][] that should use '#' for walls and '.' for floors
      measurement - a Spill.Measurement that should usually be MANHATTAN
      random - an RNG that will be converted to a StatefulRNG if it is not one already

  • Method Details

    • initialize

      public MultiSpill initialize​(short[][] level)
      Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently.
      Parameters:
      level - a short[][] that should have been the spillMap of another MultiSpill
      Returns:
      this for chaining

    • initialize

      public MultiSpill initialize​(char[][] level)
      Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ).
      Parameters:
      level - a char[][] that should use '#' for walls and '.' for floors
      Returns:
      this for chaining

    • initialize

      public MultiSpill initialize​(char[][] level, char alternateWall)
      Used to initialize or re-initialize a Spill that needs a new PhysicalMap because it either wasn't given one when it was constructed, or because the contents of the terrain have changed permanently (not if a creature moved; for that you pass the positions of creatures that block paths to scan() or findPath() ). This initialize() method allows you to specify an alternate wall char other than the default character, '#' .
      Parameters:
      level - a char[][] that should use alternateWall for walls and '.' for floors
      alternateWall - the char to use for walls
      Returns:
      this for chaining

    • resetMap

      public void resetMap()
      Resets the spillMap to being empty.

    • reset

      public void reset()
      Resets this Spill to a state with an empty spillMap and an empty spreadPattern.

    • resetCell

      public void resetCell​(int x, int y)
      Reverts a cell to an unfilled state (false in spillMap).
      Parameters:
      x - the x-component of the Coord to revert to an unfilled state
      y - the y-component of the Coord to revert to an unfilled state

    • resetCell

      public void resetCell​(Coord pt)
      Reverts a cell to an unfilled state (false in spillMap).
      Parameters:
      pt - the Coord to revert to an unfilled state

    • setFresh

      protected void setFresh​(int idx, int x, int y)

    • setFresh

      protected void setFresh​(int idx, Coord pt)

    • start

      public ArrayList<ArrayList<Coord>> start​(List<Coord> entries, int volume, Collection<Coord> impassable)
      Recalculate the spillMap and return the spreadPattern. The cell corresponding to a Coord in entries will be true, the cells near each of those will be true if chosen at random from all passable cells adjacent to a filled (true) cell, and all other cells will be false. This takes a total number of cells to attempt to fill (the volume parameter), which can be negative to simply fill the whole map, and will fill less if it has completely exhausted all passable cells from all sources in entries. If the measurement this Spill uses is anything other than MANHATTAN, you can expect many gaps in the first filled area. Subsequent calls to start() with the same entry and a higher volume will expand the area of the Spill, and are likely to fill any gaps after a few subsequent calls. Increasing the volume slowly is the best way to ensure that gaps only exist on the very edge if you use a non-MANHATTAN measurement.
      Parameters:
      entries - the first cell for each spiller to spread from, which should really be passable.
      volume - the total number of cells to attempt to fill; if negative will fill the whole map.
      impassable - a Collection, ideally a Set or GreasedRegion, holding Coord items representing the locations of moving obstacles to a fill that cannot be moved through; null means no obstacles exist.
      Returns:
      an ArrayList of Points that this will enter, in order starting with entry at index 0, until it reaches its volume or fills its boundaries completely.

    • start

      public ArrayList<ArrayList<Coord>> start​(OrderedMap<Coord,​Double> entries, int volume, Collection<Coord> impassable)
      Recalculate the spillMap and return the spreadPattern. The cell corresponding to a key in entries will be true, the cells near each of those will be true if chosen at random from all passable cells adjacent to a filled (true) cell, and all other cells will be false. This takes a total number of cells to attempt to fill (the volume parameter), which can be negative to simply fill the whole map, and will fill less if it has completely exhausted all passable cells from all sources in entries. It uses the values in entries to determine whether it should advance from a particular key in that step or not; this choice is pseudo-random. If you have some values that are at or near 1.0 and some values that are closer to 0.0, you should expect the keys for the higher values to spread further out than the keys associated with lower values.
      If the measurement this Spill uses is anything other than MANHATTAN, you can expect many gaps in the first filled area. Subsequent calls to start() with the same entry and a higher volume will expand the area of the Spill, and are likely to fill any gaps after a few subsequent calls. Increasing the volume slowly is the best way to ensure that gaps only exist on the very edge if you use a non-MANHATTAN measurement.
      The intended purpose for this method is filling contiguous areas of dungeon with certain terrain features, but it has plenty of other uses as well.
      Parameters:
      entries - key: the first cell for each spiller to spread from. value: the bias toward advancing this key; 1.0 will always advance, 0.0 will never advance beyond the key, in between will randomly choose
      volume - the total number of cells to attempt to fill; if negative will fill the whole map.
      impassable - a Collection, ideally a Set or GreasedRegion, holding Coord items representing the locations of moving obstacles to a fill that cannot be moved through; null means no obstacles exist.
      Returns:
      an ArrayList of Points that this will enter, in order starting with entry at index 0, until it reaches its volume or fills its boundaries completely.