001package squidpony.squidmath;
002
003import java.util.LinkedList;
004import java.util.List;
005
006/**
007 * A fixed-point line-drawing algorithm that should have good performance; may be useful for LOS.
008 * Algorithm is from https://hbfs.wordpress.com/2009/07/28/faster-than-bresenhams-algorithm/
009 * Created by Tommy Ettinger on 1/10/2016.
010 */
011public class DDALine {
012    /**
013     * Draws a line from (startX, startY) to (endX, endY) using the DDA algorithm. Returns a List of Coord in order.
014     * @param startX x of starting point
015     * @param startY y of starting point
016     * @param endX   x of ending point
017     * @param endY   y of ending point
018     * @return List of Coord, including (startX, startY) and (endX, endY) and all points walked between
019     */
020    public static List<Coord> line(int startX, int startY, int endX, int endY) {
021        return line(startX, startY, endX, endY, 0x7fff, 0x7fff);
022    }
023
024    /**
025     * Not intended for external use; prefer the overloads without a modifier argument.
026     * @param startX x of starting point
027     * @param startY y of starting point
028     * @param endX   x of ending point
029     * @param endY   y of ending point
030     * @param modifierX an integer that should typically be one of 0x3fff, 0x7fff, or 0xbfff
031     * @param modifierY an integer that should typically be one of 0x3fff, 0x7fff, or 0xbfff
032     * @return List of Coord, including (startX, startY) and (endX, endY) and all points walked between
033     */
034    public static List<Coord> line(int startX, int startY, int endX, int endY, int modifierX, int modifierY) {
035        int dx = endX - startX, dy = endY - startY, nx = Math.abs(dx), ny = Math.abs(dy),
036                octant = ((dy < 0) ? 4 : 0) | ((dx < 0) ? 2 : 0) | ((ny > nx) ? 1 : 0), move, frac = 0;
037
038        LinkedList<Coord> drawn = new LinkedList<>();
039        switch (octant)
040        {
041            // x positive, y positive
042            case 0:
043                move = (ny << 16)/nx;
044                for (int primary = startX; primary <= endX; primary++, frac+=move) {
045                    drawn.add(Coord.get(primary, startY + ((frac+modifierY)>>16)));
046                }
047                break;
048            case 1:
049                move = (nx << 16)/ny;
050                for (int primary = startY; primary <= endY; primary++, frac+=move) {
051                    drawn.add(Coord.get(startX + ((frac+modifierX)>>16), primary));
052                }
053                break;
054            // x negative, y positive
055            case 2:
056                move = (ny << 16)/nx;
057                for (int primary = startX; primary >= endX; primary--, frac+=move) {
058                    drawn.add(Coord.get(primary, startY + ((frac+modifierY)>>16)));
059                }
060                break;
061            case 3:
062                move = (nx << 16)/ny;
063                for (int primary = startY; primary <= endY; primary++, frac+=move) {
064                    drawn.add(Coord.get(startX - ((frac+modifierX)>>16), primary));
065                }
066                break;
067            // x negative, y negative
068            case 6:
069                move = (ny << 16)/nx;
070                for (int primary = startX; primary >= endX; primary--, frac+=move) {
071                    drawn.add(Coord.get(primary, startY - ((frac+modifierY)>>16)));
072                }
073                break;
074            case 7:
075                move = (nx << 16)/ny;
076                for (int primary = startY; primary >= endY; primary--, frac+=move) {
077                    drawn.add(Coord.get(startX - ((frac+modifierX)>>16), primary));
078                }
079                break;
080            // x positive, y negative
081            case 4:
082                move = (ny << 16)/nx;
083                for (int primary = startX; primary <= endX; primary++, frac+=move) {
084                    drawn.add(Coord.get(primary, startY - ((frac+modifierY)>>16)));
085                }
086                break;
087            case 5:
088                move = (nx << 16)/ny;
089                for (int primary = startY; primary >= endY; primary--, frac+=move) {
090                    drawn.add(Coord.get(startX + ((frac+modifierX)>>16), primary));
091                }
092                break;
093        }
094        return drawn;
095    }
096
097    /**
098     * Draws a line from start to end using the DDA algorithm. Returns a List of Coord in order.
099     * @param start starting point
100     * @param end ending point
101     * @return List of Coord, including start and end and all points walked between
102     */
103    public static List<Coord> line(Coord start, Coord end)
104    {
105        return line(start.x, start.y, end.x, end.y);
106    }
107}