001package squidpony.squidmath;
002
003import java.util.LinkedList;
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 List<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        LinkedList<Coord> drawn = new LinkedList<>();
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 List<Coord> line(Coord start, Coord end)
047    {
048        return line(start.x, start.y, end.x, end.y);
049    }
050}