001package squidpony.squidmath;
002
003import java.util.ArrayList;
004import java.util.List;
005
006/**
007 * A simple line-drawing algorithm that only takes orthogonal steps; may be useful for LOS in games that use Manhattan
008 * distances for measurements.
009 * Algorithm is from http://www.redblobgames.com/grids/line-drawing.html#stepping , thanks Amit!
010 * Created by Tommy Ettinger on 1/10/2016.
011 */
012public class OrthoLine {
013    /**
014     * Draws a line from (startX, startY) to (endX, endY) using only N/S/E/W movement. Returns a List of Coord in order.
015     *
016     * @param startX x of starting point
017     * @param startY y of starting point
018     * @param endX   x of ending point
019     * @param endY   y of ending point
020     * @return List of Coord, including (startX, startY) and (endX, endY) and all points walked between
021     */
022    public static ArrayList<Coord> line(int startX, int startY, int endX, int endY) {
023        int dx = endX - startX, dy = endY - startY, nx = Math.abs(dx), ny = Math.abs(dy);
024        int signX = (dx > 0) ? 1 : -1, signY = (dy > 0) ? 1 : -1, workX = startX, workY = startY;
025        ArrayList<Coord> drawn = new ArrayList<>(1 + nx + ny);
026        drawn.add(Coord.get(startX, startY));
027        for (int ix = 0, iy = 0; ix < nx || iy < ny; ) {
028            if ((0.5f + ix) / nx < (0.5 + iy) / ny) {
029                workX += signX;
030                ix++;
031            } else {
032                workY += signY;
033                iy++;
034            }
035            drawn.add(Coord.get(workX, workY));
036        }
037        return drawn;
038    }
039
040    /**
041     * Draws a line from start to end using only N/S/E/W movement. Returns a List of Coord in order.
042     * @param start starting point
043     * @param end ending point
044     * @return List of Coord, including start and end and all points walked between
045     */
046    public static ArrayList<Coord> line(Coord start, Coord end)
047    {
048        return line(start.x, start.y, end.x, end.y);
049    }
050    /**
051     * Draws a line from (startX, startY) to (endX, endY) using only N/S/E/W movement. Returns an array of Coord in order.
052     *
053     * @param startX x of starting point
054     * @param startY y of starting point
055     * @param endX   x of ending point
056     * @param endY   y of ending point
057     * @return array of Coord, including (startX, startY) and (endX, endY) and all points walked between
058     */
059    public static Coord[] line_(int startX, int startY, int endX, int endY) {
060        int dx = endX - startX, dy = endY - startY, nx = Math.abs(dx), ny = Math.abs(dy);
061        int signX = (dx > 0) ? 1 : -1, signY = (dy > 0) ? 1 : -1, workX = startX, workY = startY;
062        Coord[] drawn = new Coord[nx + ny + 1];
063        drawn[0] = Coord.get(startX, startY);
064        for (int i = 1, ix = 0, iy = 0; ix < nx || iy < ny; i++) {
065            if ((0.5f + ix) / nx < (0.5 + iy) / ny) {
066                workX += signX;
067                ix++;
068            } else {
069                workY += signY;
070                iy++;
071            }
072            drawn[i] = Coord.get(workX, workY);
073        }
074        return drawn;
075    }
076
077    /**
078     * Draws a line from start to end using only N/S/E/W movement. Returns a List of Coord in order.
079     * @param start starting point
080     * @param end ending point
081     * @return List of Coord, including start and end and all points walked between
082     */
083    public static Coord[] line_(Coord start, Coord end)
084    {
085        return line_(start.x, start.y, end.x, end.y);
086    }
087
088    /**
089     * Given an array of Coord as produced by {@link #line_(Coord, Coord)} or {@link #line_(int, int, int, int)}, this
090     * gets a char array of box-drawing characters that connect when drawn at the corresponding Coord positions in the
091     * given line. This can be useful for drawing highlight lines or showing what path something will take, as long as
092     * it only uses 4-way orthogonal connections between Coords. Any connections that require a diagonal will not be
093     * handled by this method (returning a straight line without much accuracy), and any Coords that aren't adjacent
094     * will cause an {@link IllegalStateException} if this has to draw a line between them. If this method is called on
095     * the result of this class' line_() method, then it should always return a valid result; if it is called on a path
096     * made with some other method, such as from {@link Bresenham#line2D_(Coord, Coord)}, then it shouldn't throw an
097     * exception but may produce a low-quality (disconnected visually) line.
098     * @param line a Coord array where each Coord is orthogonally adjacent to its neighbor(s) in the array; usually
099     *             produced via {@link #line_(Coord, Coord)} or {@link #line_(int, int, int, int)}
100     * @return a char array of box-drawing chars that will connect when drawn at the same points as in line
101     */
102    public static char[] lineChars(Coord[] line)
103    {
104        // ─│┌┐└┘├┤┬┴┼
105        if(line == null) return null;
106        int len = line.length;
107        if(len == 0) return new char[0];
108        if(len == 1) return new char[]{'─'};
109        char[] cs = new char[len];
110        cs[0] = line[0].x == line[1].x ? '│' : '─';
111        cs[len - 1] = line[len - 1].x == line[len - 2].x ? '│' : '─';
112        Coord before, current, next;
113        for (int i = 1; i < len - 1; i++) {
114            before = line[i-1];
115            current = line[i];
116            next = line[i+1];
117            switch (before.toGoTo(current))
118            {
119                case RIGHT:
120                    switch (current.toGoTo(next))
121                    {
122                        case UP: cs[i] = '┘';
123                            break;
124                        case DOWN: cs[i] = '┐';
125                            break;
126                        default: cs[i] = '─';
127                            break;
128                    }
129                    break;
130                case LEFT:
131                    switch (current.toGoTo(next))
132                    {
133                        case UP: cs[i] = '└';
134                            break;
135                        case DOWN: cs[i] = '┌';
136                            break;
137                        default: cs[i] = '─';
138                            break;
139                    }
140                    break;
141                case UP:
142                    switch (current.toGoTo(next))
143                    {
144                        case LEFT: cs[i] = '┐';
145                            break;
146                        case RIGHT: cs[i] = '┌';
147                            break;
148                        default: cs[i] = '│';
149                            break;
150                    }
151                    break;
152                default:
153                    switch (current.toGoTo(next))
154                    {
155                        case LEFT: cs[i] = '┘';
156                            break;
157                        case RIGHT: cs[i] = '└';
158                            break;
159                        default: cs[i] = '│';
160                            break;
161                    }
162            }
163        }
164        return cs;
165    }
166    /**
167     * Given a List of Coord as produced by {@link #line(Coord, Coord)} or {@link #line(int, int, int, int)}, this
168     * gets a char array of box-drawing characters that connect when drawn at the corresponding Coord positions in the
169     * given line. This can be useful for drawing highlight lines or showing what path something will take, as long as
170     * it only uses 4-way orthogonal connections between Coords. Any connections that require a diagonal will not be
171     * handled by this method (returning a straight line without much accuracy), and any Coords that aren't adjacent
172     * will cause an {@link IllegalStateException} if this has to draw a line between them. If this method is called on
173     * the result of this class' line() method, then it should always return a valid result; if it is called on a path
174     * made with some other method, such as from {@link Bresenham#line2D(Coord, Coord)}, then it shouldn't throw an
175     * exception but may produce a low-quality (disconnected visually) line.
176     * @param line a List of Coord where each Coord is orthogonally adjacent to its neighbor(s) in the List; usually
177     *             produced via {@link #line(Coord, Coord)} or {@link #line(int, int, int, int)}
178     * @return a char array of box-drawing chars that will connect when drawn at the same points as in line
179     */
180    public static char[] lineChars(List<Coord> line)
181    {
182        // ─│┌┐└┘├┤┬┴┼
183        if(line == null) return null;
184        int len = line.size();
185        if(len == 0) return new char[0];
186        if(len == 1) return new char[]{'─'};
187        char[] cs = new char[len];
188        cs[0] = line.get(0).x == line.get(1).x ? '│' : '─';
189        cs[len - 1] = line.get(len - 1).x == line.get(len - 2).x ? '│' : '─';
190        Coord before, current, next;
191        for (int i = 1; i < len - 1; i++) {
192            before = line.get(i-1);
193            current = line.get(i);
194            next = line.get(i+1);
195            switch (before.toGoTo(current))
196            {
197                case RIGHT:
198                    switch (current.toGoTo(next))
199                    {
200                        case UP: cs[i] = '┘';
201                            break;
202                        case DOWN: cs[i] = '┐';
203                            break;
204                        default: cs[i] = '─';
205                            break;
206                    }
207                    break;
208                case LEFT:
209                    switch (current.toGoTo(next))
210                    {
211                        case UP: cs[i] = '└';
212                            break;
213                        case DOWN: cs[i] = '┌';
214                            break;
215                        default: cs[i] = '─';
216                            break;
217                    }
218                    break;
219                case UP:
220                    switch (current.toGoTo(next))
221                    {
222                        case LEFT: cs[i] = '┐';
223                            break;
224                        case RIGHT: cs[i] = '┌';
225                            break;
226                        default: cs[i] = '│';
227                            break;
228                    }
229                    break;
230                default:
231                    switch (current.toGoTo(next))
232                    {
233                        case LEFT: cs[i] = '┘';
234                            break;
235                        case RIGHT: cs[i] = '└';
236                            break;
237                        default: cs[i] = '│';
238                            break;
239                    }
240            }
241        }
242        return cs;
243    }
244}