001package squidpony.squidmath;
002
003import squidpony.squidai.graph.DefaultGraph;
004import squidpony.squidai.graph.Heuristic;
005import squidpony.squidgrid.Direction;
006
007import java.util.ArrayList;
008
009/**
010 * Like {@link WobblyLine}, this generates orthogonally-connected paths of {@link Coord} that meander through an area;
011 * unlike WobblyLine, this won't ever generate paths that cross themselves.
012 * <br>
013 * This uses a similar algorithm to {@link squidpony.squidgrid.mapping.GrowingTreeMazeGenerator} to generate a
014 * fully-connected graph for a given rectangular area, then solves it with
015 * {@link DefaultGraph#findShortestPath(Coord, Coord, ArrayList, Heuristic)}.
016 * <br>
017 * Created by Tommy Ettinger on 6/26/2020.
018 */
019public class TwistedLine {
020    public IRNG rng;
021    public final DefaultGraph graph;
022    public final ArrayList<Coord> lastPath;
023
024    public TwistedLine() {
025        this(40, 40, null);
026    }
027
028    public TwistedLine(int width, int height) {
029        this(width, height, null);
030    }
031
032    public TwistedLine(int width, int height, IRNG rng) {
033        graph = new DefaultGraph();
034        graph.width = Math.max(width, 2);
035        graph.height = Math.max(height, 2);
036        this.rng = rng == null ? new RNG() : rng;
037        lastPath = new ArrayList<>(graph.width + graph.height);
038        reinitialize();
039    }
040
041    /**
042     * Called automatically during construction, this sets up a random maze as a {@link DefaultGraph} so a path can be
043     * found. You can call this after construction to change the paths this can find.
044     */
045    public void reinitialize() {
046        graph.removeAllVertices();
047        for (int x = 0; x < graph.width; x++) {
048            for (int y = 0; y < graph.height; y++) {
049                graph.addVertex(Coord.get(x, y));
050            }
051        }
052
053        int x = rng.nextSignedInt(graph.width);
054        int y = rng.nextSignedInt(graph.height);
055
056        OrderedSet<Coord> deck = new OrderedSet<>();
057        deck.add(Coord.get(x, y));
058
059        Direction[] dirs = new Direction[4];
060        System.arraycopy(Direction.CARDINALS, 0, dirs, 0, 4);
061        OUTER:
062        while (!deck.isEmpty()) {
063            int i = deck.size() - 1;
064            Coord p = deck.getAt(i);
065            rng.shuffleInPlace(dirs);
066
067            for (Direction dir : dirs) {
068                x = p.x + dir.deltaX;
069                y = p.y + dir.deltaY;
070                if (x >= 0 && x < graph.width && y >= 0 && y < graph.height) {
071                    Coord c = Coord.get(x, y);
072                    if (graph.getEdges(c).isEmpty() && deck.add(c)) {
073                        graph.addEdge(p, c);
074                        continue OUTER;
075                    }
076                }
077            }
078
079            deck.remove(p);
080        }
081
082    }
083
084    public ArrayList<Coord> line(int startX, int startY, int endX, int endY) {
085        return line(Coord.get(startX, startY), Coord.get(endX, endY));
086    }
087
088    public ArrayList<Coord> line(Coord start, Coord end) {
089        graph.findShortestPath(start, end, lastPath, Heuristic.EUCLIDEAN);
090        return lastPath;
091    }
092
093    public int getWidth() {
094        return graph.width;
095    }
096
097    public int getHeight() {
098        return graph.height;
099    }
100
101    public IRNG getRng() {
102        return rng;
103    }
104
105    public void setRng(IRNG rng) {
106        this.rng = rng;
107    }
108
109    public ArrayList<Coord> getLastPath() {
110        return lastPath;
111    }
112}