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}