Class DrunkenWalk

java.lang.Object
com.github.yellowstonegames.grid.DrunkenWalk
public final class DrunkenWalk extends Object
A drunkard's-walk-like algorithm for line-drawing "wobbly" paths. This produces lines as ObjectDeque of Coord, where Coords that are adjacent in the ObjectDeque are guaranteed to be orthogonally adjacent, but the path as a whole is not guaranteed to have all unique Coords (that is, the line may cross over its previous path). This doesn't implement LineDrawer because it has the restriction that the line can't extend off the bounds of some rectangular grid (usually the map).
The line() methods here use an EnhancedRandom (and will make their own FourWheelRandom if they don't take one as a parameter) to make a choice between orthogonal directions to travel in. Because they can go around the target instead of straight to it, they also need a width and height for the map, so they don't wander over the edge. You can also pass a weight to one of the line() methods, which affects how straight the wobbly path will be (1.0 being just about perfectly straight, 0.5 being very chaotic, and less than 0.5 being almost unrecognizable as a path). Lower weights make the case where the path crosses itself more likely.
Based on Michael Patraw's C code, used for cave carving in his map generator (broken link).

  • Method Summary

    Modifier and Type
    Method
    Description
    static com.github.tommyettinger.ds.ObjectDeque<Coord>
    line(int startX, int startY, int endX, int endY, int width, int height)
    Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm.
    static com.github.tommyettinger.ds.ObjectDeque<Coord>
    line(int startX, int startY, int endX, int endY, int width, int height, float weight, com.github.tommyettinger.random.EnhancedRandom rng)
    Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm.
    static com.github.tommyettinger.ds.ObjectDeque<Coord>
    line(int startX, int startY, int endX, int endY, int width, int height, float weight, com.github.tommyettinger.random.EnhancedRandom rng, com.github.tommyettinger.ds.ObjectDeque<Coord> buffer)
    Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm.
    static com.github.tommyettinger.ds.ObjectDeque<Coord>
    line(Coord start, Coord end, int width, int height)
    Draws a line from start to end using the Drunkard's Walk algorithm.

    Methods inherited from class Object

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

  • Method Details

    • line

      public static com.github.tommyettinger.ds.ObjectDeque<Coord> line(int startX, int startY, int endX, int endY, int width, int height)
      Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm. Returns a List of Coord in order.
      Equivalent to calling line(startX, startY, endX, endY, width, height, 0.75, new RNG()) .
      Parameters:
      startX - x of starting point
      startY - y of starting point
      endX - x of ending point
      endY - y of ending point
      width - maximum map width
      height - maximum map height
      Returns:
      List of Coord, including (startX, startY) and (endX, endY) and all points walked between

    • line

      public static com.github.tommyettinger.ds.ObjectDeque<Coord> line(int startX, int startY, int endX, int endY, int width, int height, float weight, com.github.tommyettinger.random.EnhancedRandom rng)
      Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm. Returns a List of Coord in order.
      Parameters:
      startX - x of starting point
      startY - y of starting point
      endX - x of ending point
      endY - y of ending point
      width - maximum map width
      height - maximum map height
      weight - between 0.5 and 1.0, usually. 0.6 makes very random walks, 0.9 is almost a straight line.
      rng - the random number generator to use
      Returns:
      List of Coord, including (startX, startY) and (endX, endY) and all points walked between

    • line

      public static com.github.tommyettinger.ds.ObjectDeque<Coord> line(int startX, int startY, int endX, int endY, int width, int height, float weight, com.github.tommyettinger.random.EnhancedRandom rng, com.github.tommyettinger.ds.ObjectDeque<Coord> buffer)
      Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm. Returns a List of Coord in order. Modifies buffer if it is non-null, or creates an ObjectDeque if buffer is null.
      Parameters:
      startX - x of starting point
      startY - y of starting point
      endX - x of ending point
      endY - y of ending point
      width - maximum map width
      height - maximum map height
      weight - between 0.5 and 1.0, usually. 0.6 makes very random walks, 0.9 is almost a straight line.
      rng - the random number generator to use
      buffer - an ObjectDeque of Coord that will be appended to if non-null or created if null
      Returns:
      buffer, after changes, including (startX, startY) and (endX, endY) and all points walked between

    • line

      public static com.github.tommyettinger.ds.ObjectDeque<Coord> line(Coord start, Coord end, int width, int height)
      Draws a line from start to end using the Drunkard's Walk algorithm. Returns a List of Coord in order.
      Parameters:
      start - starting point
      end - ending point
      width - maximum map width
      height - maximum map height
      Returns:
      List of Coord, including start and end and all points walked between