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}