Package squidpony.squidmath

Class PoissonDisk

java.lang.Object
squidpony.squidmath.PoissonDisk
public class PoissonDisk
extends Object
This provides a Uniform Poisson Disk Sampling technique that can be used to generate random points that have a uniform minimum distance between each other. Due to Coord in SquidLib using ints and most Poisson Disk algorithms using floating-point numbers, some imprecision is to be expected from rounding to the nearest integers x and y. The algorithm is from the "Fast Poisson Disk Sampling in Arbitrary Dimensions" paper by Robert Bridson http://www.cs.ubc.ca/~rbridson/docs/bridson-siggraph07-poissondisk.pdf Adapted from C# by Renaud Bedard, which was adapted from Java source by Herman Tulleken http://theinstructionlimit.com/fast-uniform-poisson-disk-sampling-in-c Created by Tommy Ettinger on 10/20/2015.

  • Method Summary

    Modifier and Type Method Description
    static Coord randomUnblockedTile​(Coord minPosition, Coord maxPosition, char[][] map, IRNG rng, HashSet<Character> blocked)
    Finds a random Coord where the x and y match up to a [x][y] location on map that has any value not in blocking.
    static OrderedSet<Coord> sampleCircle​(Coord center, float radius, float minimumDistance, int maxX, int maxY)
    Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list.
    static OrderedSet<Coord> sampleCircle​(Coord center, float radius, float minimumDistance, int maxX, int maxY, int pointsPerIteration, IRNG rng)
    Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list.
    static OrderedSet<Coord> sampleMap​(char[][] map, float minimumDistance, IRNG rng, Character... blocking)  
    static OrderedSet<Coord> sampleMap​(Coord minPosition, Coord maxPosition, char[][] map, float minimumDistance, IRNG rng, Character... blocking)  
    static OrderedSet<Coord> sampleRectangle​(Coord minPosition, Coord maxPosition, float minimumDistance, int maxX, int maxY)
    Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and maxPosition, but with the given minimum distance from any other Coord in the list.
    static OrderedSet<Coord> sampleRectangle​(Coord minPosition, Coord maxPosition, float minimumDistance, int maxX, int maxY, int pointsPerIteration, IRNG rng)
    Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and maxPosition, but with the given minimum distance from any other Coord in the list.

    Methods inherited from class java.lang.Object

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

  • Method Details

    • sampleCircle

      public static OrderedSet<Coord> sampleCircle​(Coord center, float radius, float minimumDistance, int maxX, int maxY)
      Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list. The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have negative x or y.
      Parameters:
      center - the center of the circle to spray Coords into
      radius - the radius of the circle to spray Coords into
      minimumDistance - the minimum distance between Coords, in Euclidean distance as a float.
      maxX - one more than the highest x that can be assigned; typically an array length
      maxY - one more than the highest y that can be assigned; typically an array length
      Returns:
      an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary

    • sampleCircle

      public static OrderedSet<Coord> sampleCircle​(Coord center, float radius, float minimumDistance, int maxX, int maxY, int pointsPerIteration, IRNG rng)
      Get a list of Coords, each randomly positioned around the given center out to the given radius (measured with Euclidean distance, so a true circle), but with the given minimum distance from any other Coord in the list. The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have negative x or y.
      Parameters:
      center - the center of the circle to spray Coords into
      radius - the radius of the circle to spray Coords into
      minimumDistance - the minimum distance between Coords, in Euclidean distance as a float.
      maxX - one more than the highest x that can be assigned; typically an array length
      maxY - one more than the highest y that can be assigned; typically an array length
      pointsPerIteration - with small radii, this can be around 5; with larger ones, 30 is reasonable
      rng - an IRNG to use for all random sampling.
      Returns:
      an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary

    • sampleRectangle

      public static OrderedSet<Coord> sampleRectangle​(Coord minPosition, Coord maxPosition, float minimumDistance, int maxX, int maxY)
      Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and maxPosition, but with the given minimum distance from any other Coord in the list. The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have negative x or y.
      Parameters:
      minPosition - the Coord with the lowest x and lowest y to be used as a corner for the bounding box
      maxPosition - the Coord with the highest x and highest y to be used as a corner for the bounding box
      minimumDistance - the minimum distance between Coords, in Euclidean distance as a float.
      maxX - one more than the highest x that can be assigned; typically an array length
      maxY - one more than the highest y that can be assigned; typically an array length
      Returns:
      an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary

    • sampleRectangle

      public static OrderedSet<Coord> sampleRectangle​(Coord minPosition, Coord maxPosition, float minimumDistance, int maxX, int maxY, int pointsPerIteration, IRNG rng)
      Get a list of Coords, each randomly positioned within the rectangle between the given minPosition and maxPosition, but with the given minimum distance from any other Coord in the list. The parameters maxX and maxY should typically correspond to the width and height of the map; no points will have positions with x equal to or greater than maxX and the same for y and maxY; similarly, no points will have negative x or y.
      Parameters:
      minPosition - the Coord with the lowest x and lowest y to be used as a corner for the bounding box
      maxPosition - the Coord with the highest x and highest y to be used as a corner for the bounding box
      minimumDistance - the minimum distance between Coords, in Euclidean distance as a float.
      maxX - one more than the highest x that can be assigned; typically an array length
      maxY - one more than the highest y that can be assigned; typically an array length
      pointsPerIteration - with small areas, this can be around 5; with larger ones, 30 is reasonable
      rng - an IRNG to use for all random sampling.
      Returns:
      an ArrayList of Coord that satisfy the minimum distance; the length of the array can vary

    • sampleMap

      public static OrderedSet<Coord> sampleMap​(char[][] map, float minimumDistance, IRNG rng, Character... blocking)

    • sampleMap

      public static OrderedSet<Coord> sampleMap​(Coord minPosition, Coord maxPosition, char[][] map, float minimumDistance, IRNG rng, Character... blocking)

    • randomUnblockedTile

      public static Coord randomUnblockedTile​(Coord minPosition, Coord maxPosition, char[][] map, IRNG rng, HashSet<Character> blocked)
      Finds a random Coord where the x and y match up to a [x][y] location on map that has any value not in blocking. Uses the given IRNG for pseudo-random number generation.
      Parameters:
      minPosition - the Coord with the lowest x and lowest y to be used as a corner for the bounding box
      maxPosition - the Coord with the highest x and highest y to be used as a corner for the bounding box
      map - a dungeon map or something, x then y
      rng - a IRNG to generate random choices
      blocked - a Set of Characters that block a tile from being chosen
      Returns:
      a Coord that corresponds to a map element equal to tile, or null if tile cannot be found or if map is too small.