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}