001package squidpony.squidmath; 002 003import java.util.ArrayList; 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 mn = Math.max(nx, ny); 038 ArrayList<Coord> drawn = new ArrayList<>(mn); 039 if(mn == 0) 040 { 041 drawn.add(Coord.get(startX, startY)); 042 return drawn; 043 } 044 if(ny == 0) 045 { 046 if(dx > 0) { 047 for (int x = startX, i = 0; x <= endX; x++, i++) { 048 drawn.add(Coord.get(x, startY)); 049 } 050 } 051 else { 052 for (int x = startX, i = 0; x >= endX; x--, i++) { 053 drawn.add(Coord.get(x, startY)); 054 } 055 } 056 057 return drawn; 058 } 059 if(nx == 0) 060 { 061 if(dy > 0) { 062 for (int y = startY, i = 0; y <= endY; y++, i++) { 063 drawn.add(Coord.get(startX, y)); 064 } 065 } 066 else { 067 for (int y = startY, i = 0; y >= endY; y--, i++) { 068 drawn.add(Coord.get(startX, y)); 069 } 070 } 071 return drawn; 072 } 073 074 switch (octant) 075 { 076 // x positive, y positive 077 case 0: 078 move = (ny << 16)/nx; 079 for (int primary = startX; primary <= endX; primary++, frac+=move) { 080 drawn.add(Coord.get(primary, startY + ((frac+modifierY)>>16))); 081 } 082 break; 083 case 1: 084 move = (nx << 16)/ny; 085 for (int primary = startY; primary <= endY; primary++, frac+=move) { 086 drawn.add(Coord.get(startX + ((frac+modifierX)>>16), primary)); 087 } 088 break; 089 // x negative, y positive 090 case 2: 091 move = (ny << 16)/nx; 092 for (int primary = startX; primary >= endX; primary--, frac+=move) { 093 drawn.add(Coord.get(primary, startY + ((frac+modifierY)>>16))); 094 } 095 break; 096 case 3: 097 move = (nx << 16)/ny; 098 for (int primary = startY; primary <= endY; primary++, frac+=move) { 099 drawn.add(Coord.get(startX - ((frac+modifierX)>>16), primary)); 100 } 101 break; 102 // x negative, y negative 103 case 6: 104 move = (ny << 16)/nx; 105 for (int primary = startX; primary >= endX; primary--, frac+=move) { 106 drawn.add(Coord.get(primary, startY - ((frac+modifierY)>>16))); 107 } 108 break; 109 case 7: 110 move = (nx << 16)/ny; 111 for (int primary = startY; primary >= endY; primary--, frac+=move) { 112 drawn.add(Coord.get(startX - ((frac+modifierX)>>16), primary)); 113 } 114 break; 115 // x positive, y negative 116 case 4: 117 move = (ny << 16)/nx; 118 for (int primary = startX; primary <= endX; primary++, frac+=move) { 119 drawn.add(Coord.get(primary, startY - ((frac+modifierY)>>16))); 120 } 121 break; 122 case 5: 123 move = (nx << 16)/ny; 124 for (int primary = startY; primary >= endY; primary--, frac+=move) { 125 drawn.add(Coord.get(startX + ((frac+modifierX)>>16), primary)); 126 } 127 break; 128 } 129 return drawn; 130 } 131 132 /** 133 * Draws a line from start to end using the DDA algorithm. Returns a List of Coord in order. 134 * @param start starting point 135 * @param end ending point 136 * @return List of Coord, including start and end and all points walked between 137 */ 138 public static List<Coord> line(Coord start, Coord end) 139 { 140 return line(start.x, start.y, end.x, end.y); 141 } 142 /** 143 * Draws a line from (startX, startY) to (endX, endY) using the DDA algorithm. Returns an array of Coord in order. 144 * @param startX x of starting point 145 * @param startY y of starting point 146 * @param endX x of ending point 147 * @param endY y of ending point 148 * @return array of Coord, including (startX, startY) and (endX, endY) and all points walked between 149 */ 150 public static Coord[] line_(int startX, int startY, int endX, int endY) { 151 return line_(startX, startY, endX, endY, 0x7fff, 0x7fff); 152 } 153 154 /** 155 * Not intended for external use; prefer the overloads without a modifier argument. 156 * @param startX x of starting point 157 * @param startY y of starting point 158 * @param endX x of ending point 159 * @param endY y of ending point 160 * @param modifierX an integer that should typically be one of 0x3fff, 0x7fff, or 0xbfff 161 * @param modifierY an integer that should typically be one of 0x3fff, 0x7fff, or 0xbfff 162 * @return array of Coord, including (startX, startY) and (endX, endY) and all points walked between 163 */ 164 public static Coord[] line_(int startX, int startY, int endX, int endY, int modifierX, int modifierY) { 165 int dx = endX - startX, dy = endY - startY, nx = Math.abs(dx), ny = Math.abs(dy), 166 octant = ((dy < 0) ? 4 : 0) | ((dx < 0) ? 2 : 0) | ((ny > nx) ? 1 : 0), move, frac = 0, 167 mn = Math.max(nx, ny); 168 if(mn == 0) 169 { 170 return new Coord[]{Coord.get(startX, startY)}; 171 } 172 Coord[] drawn = new Coord[mn + 1]; 173 if(ny == 0) 174 { 175 if(dx > 0) { 176 for (int x = startX, i = 0; x <= endX; x++, i++) { 177 drawn[i] = Coord.get(x, startY); 178 } 179 } 180 else { 181 for (int x = startX, i = 0; x >= endX; x--, i++) { 182 drawn[i] = Coord.get(x, startY); 183 } 184 } 185 186 return drawn; 187 } 188 if(nx == 0) 189 { 190 if(dy > 0) { 191 for (int y = startY, i = 0; y <= endY; y++, i++) { 192 drawn[i] = Coord.get(startX, y); 193 } 194 } 195 else { 196 for (int y = startY, i = 0; y >= endY; y--, i++) { 197 drawn[i] = Coord.get(startX, y); 198 } 199 } 200 return drawn; 201 } 202 switch (octant) 203 { 204 // x positive, y positive 205 case 0: 206 move = (ny << 16)/nx; 207 for (int i = 0, primary = startX; primary <= endX; primary++, frac+=move, i++) { 208 drawn[i] = Coord.get(primary, startY + ((frac+modifierY)>>16)); 209 } 210 break; 211 case 1: 212 move = (nx << 16)/ny; 213 for (int i = 0, primary = startY; primary <= endY; primary++, frac+=move, i++) { 214 drawn[i] = Coord.get(startX + ((frac+modifierX)>>16), primary); 215 } 216 break; 217 // x negative, y positive 218 case 2: 219 move = (ny << 16)/nx; 220 for (int i = 0, primary = startX; primary >= endX; primary--, frac+=move, i++) { 221 drawn[i] = Coord.get(primary, startY + ((frac+modifierY)>>16)); 222 } 223 break; 224 case 3: 225 move = (nx << 16)/ny; 226 for (int i = 0, primary = startY; primary <= endY; primary++, frac+=move, i++) { 227 drawn[i] = Coord.get(startX - ((frac+modifierX)>>16), primary); 228 } 229 break; 230 // x negative, y negative 231 case 6: 232 move = (ny << 16)/nx; 233 for (int i = 0, primary = startX; primary >= endX; primary--, frac+=move, i++) { 234 drawn[i] = Coord.get(primary, startY - ((frac+modifierY)>>16)); 235 } 236 break; 237 case 7: 238 move = (nx << 16)/ny; 239 for (int i = 0, primary = startY; primary >= endY; primary--, frac+=move, i++) { 240 drawn[i] = Coord.get(startX - ((frac+modifierX)>>16), primary); 241 } 242 break; 243 // x positive, y negative 244 case 4: 245 move = (ny << 16)/nx; 246 for (int i = 0, primary = startX; primary <= endX; primary++, frac+=move, i++) { 247 drawn[i] = Coord.get(primary, startY - ((frac+modifierY)>>16)); 248 } 249 break; 250 case 5: 251 move = (nx << 16)/ny; 252 for (int i = 0, primary = startY; primary >= endY; primary--, frac+=move, i++) { 253 drawn[i] = Coord.get(startX + ((frac+modifierX)>>16), primary); 254 } 255 break; 256 } 257 return drawn; 258 } 259 260 /** 261 * Draws a line from start to end using the DDA algorithm. Returns an array of Coord in order. 262 * @param start starting point 263 * @param end ending point 264 * @return array of Coord, including start and end and all points walked between 265 */ 266 public static Coord[] line_(Coord start, Coord end) 267 { 268 return line_(start.x, start.y, end.x, end.y); 269 } 270 271}