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