001package squidpony.squidmath; 002 003import squidpony.squidgrid.Direction; 004 005import java.util.ArrayList; 006import java.util.List; 007 008/** 009 * A drunkard's-walk-like algorithm for line drawing "wobbly" paths. 010 * The line() methods here use an RNG (and will make their own if they don't take one as a parameter) to make a choice 011 * between orthogonal directions to travel in. Because they can go around the target instead of straight to it, they 012 * 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 013 * line() methods, which affects how straight the wobbly path will be (1.0 being just about perfectly straight, 0.5 014 * being very chaotic, and less than 0.5 being almost unrecognizable as a path). 015 * <br> 016 * Based on Michael Patraw's C code, used for cave carving in his map generator. http://mpatraw.github.io/libdrunkard/ 017 * Created by Tommy Ettinger on 1/10/2016. 018 */ 019public class WobblyLine { 020 /** 021 * Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm. Returns a List of Coord 022 * in order. 023 * <br> 024 * Equivalent to calling {@code line(startX, startY, endX, endY, width, height, 0.75, new RNG())} . 025 * @param startX x of starting point 026 * @param startY y of starting point 027 * @param endX x of ending point 028 * @param endY y of ending point 029 * @param width maximum map width 030 * @param height maximum map height 031 * @return List of Coord, including (startX, startY) and (endX, endY) and all points walked between 032 */ 033 public static List<Coord> line(int startX, int startY, int endX, int endY, int width, int height) { 034 return line(startX, startY, endX, endY, width, height, 0.75, new RNG()); 035 } 036 /** 037 * Draws a line from (startX, startY) to (endX, endY) using the Drunkard's Walk algorithm. Returns a List of Coord 038 * in order. 039 * @param startX x of starting point 040 * @param startY y of starting point 041 * @param endX x of ending point 042 * @param endY y of ending point 043 * @param width maximum map width 044 * @param height maximum map height 045 * @param weight between 0.5 and 1.0, usually. 0.6 makes very random walks, 0.9 is almost a straight line. 046 * @param rng the random number generator to use 047 * @return List of Coord, including (startX, startY) and (endX, endY) and all points walked between 048 */ 049 public static List<Coord> line(int startX, int startY, int endX, int endY, 050 int width, int height, double weight, RNG rng) { 051 List<Coord> pts = new ArrayList<>(); 052 Coord start = Coord.get(startX, startY); 053 Direction dir; 054 do { 055 pts.add(start); 056 dir = stepWobbly(start.x, start.y, endX, endY, weight, width, height, rng); 057 start = start.translate(dir); 058 if(start.x < 1 || start.y < 1 || start.x >= width - 1 || start.y >= height - 1) 059 break; 060 }while (dir != Direction.NONE); 061 return pts; 062 } 063 064 /** 065 * Internal use. Drunkard's walk algorithm, single step. Based on Michael Patraw's C code, used for cave carving. 066 * http://mpatraw.github.io/libdrunkard/ 067 * @param currentX the x coordinate of the current point 068 * @param currentY the y coordinate of the current point 069 * @param targetX the x coordinate of the point to wobble towards 070 * @param targetY the y coordinate of the point to wobble towards 071 * @param weight between 0.5 and 1.0, usually. 0.6 makes very random walks, 0.9 is almost a straight line. 072 * @param width maximum map width 073 * @param height maximum map height 074 * @param rng the random number generator to use 075 * @return a Direction, either UP, DOWN, LEFT, or RIGHT if we should move, or NONE if we have reached our target 076 */ 077 private static Direction stepWobbly(int currentX, int currentY, int targetX, int targetY, double weight, 078 int width, int height, RNG rng) 079 { 080 int dx = targetX - currentX; 081 int dy = targetY - currentY; 082 083 if (dx > 1) dx = 1; 084 if (dx < -1) dx = -1; 085 if (dy > 1) dy = 1; 086 if (dy < -1) dy = -1; 087 088 double r = rng.nextDouble(); 089 Direction dir; 090 if (dx == 0 && dy == 0) 091 { 092 return Direction.NONE; 093 } 094 else if (dx == 0 || dy == 0) 095 { 096 int dx2 = (dx == 0) ? dx : dy, dy2 = (dx == 0) ? dy : dx; 097 if (r >= (weight * 0.5)) 098 { 099 r -= weight * 0.5; 100 if (r < weight * (1.0 / 6) + (1 - weight) * (1.0 / 3)) 101 { 102 dx2 = -1; 103 dy2 = 0; 104 } 105 else if (r < weight * (2.0 / 6) + (1 - weight) * (2.0 / 3)) 106 { 107 dx2 = 1; 108 dy2 = 0; 109 } 110 else 111 { 112 dx2 = 0; 113 dy2 *= -1; 114 } 115 } 116 dir = Direction.getCardinalDirection(dx2, -dy2); 117 118 } 119 else 120 { 121 if (r < weight * 0.5) 122 { 123 dy = 0; 124 } 125 else if (r < weight) 126 { 127 dx = 0; 128 } 129 else if (r < weight + (1 - weight) * 0.5) 130 { 131 dx *= -1; 132 dy = 0; 133 } 134 else 135 { 136 dx = 0; 137 dy *= -1; 138 } 139 dir = Direction.getCardinalDirection(dx, -dy); 140 } 141 if(currentX + dir.deltaX <= 0 || currentX + dir.deltaX >= width - 1) { 142 if (currentY < targetY) dir = Direction.DOWN; 143 else if (currentY > targetY) dir = Direction.UP; 144 } 145 else if(currentY + dir.deltaY <= 0 || currentY + dir.deltaY >= height - 1) { 146 if (currentX < targetX) dir = Direction.RIGHT; 147 else if (currentX > targetX) dir = Direction.LEFT; 148 } 149 return dir; 150 } 151 152 /** 153 * Draws a line from start to end using the Drunkard's Walk algorithm. Returns a List of Coord in order. 154 * @param start starting point 155 * @param end ending point 156 * @param width maximum map width 157 * @param height maximum map height 158 * @return List of Coord, including start and end and all points walked between 159 */ 160 public static List<Coord> line(Coord start, Coord end, int width, int height) 161 { 162 return line(start.x, start.y, end.x, end.y, width, height); 163 } 164}