001 package org.bukkit.util;
002
003 import static org.bukkit.util.NumberConversions.*;
004
005 import org.bukkit.World;
006 import org.bukkit.Location;
007 import org.bukkit.block.Block;
008 import org.bukkit.block.BlockFace;
009 import org.bukkit.entity.LivingEntity;
010
011 import java.util.Iterator;
012 import java.util.NoSuchElementException;
013
014 /**
015 * This class performs ray tracing and iterates along blocks on a line
016 */
017 public class BlockIterator implements Iterator<Block> {
018
019 private final World world;
020 private final int maxDistance;
021
022 private static final int gridSize = 1 << 24;
023
024 private boolean end = false;
025
026 private Block[] blockQueue = new Block[3];
027 private int currentBlock = 0;
028 private int currentDistance = 0;
029 private int maxDistanceInt;
030
031 private int secondError;
032 private int thirdError;
033
034 private int secondStep;
035 private int thirdStep;
036
037 private BlockFace mainFace;
038 private BlockFace secondFace;
039 private BlockFace thirdFace;
040
041 /**
042 * Constructs the BlockIterator
043 *
044 * @param world The world to use for tracing
045 * @param start A Vector giving the initial location for the trace
046 * @param direction A Vector pointing in the direction for the trace
047 * @param yOffset The trace begins vertically offset from the start vector
048 * by this value
049 * @param maxDistance This is the maximum distance in blocks for the
050 * trace. Setting this value above 140 may lead to problems with
051 * unloaded chunks. A value of 0 indicates no limit
052 *
053 */
054 public BlockIterator(World world, Vector start, Vector direction, double yOffset, int maxDistance) {
055 this.world = world;
056 this.maxDistance = maxDistance;
057
058 Vector startClone = start.clone();
059
060 startClone.setY(startClone.getY() + yOffset);
061
062 currentDistance = 0;
063
064 double mainDirection = 0;
065 double secondDirection = 0;
066 double thirdDirection = 0;
067
068 double mainPosition = 0;
069 double secondPosition = 0;
070 double thirdPosition = 0;
071
072 Block startBlock = this.world.getBlockAt(floor(startClone.getX()), floor(startClone.getY()), floor(startClone.getZ()));
073
074 if (getXLength(direction) > mainDirection) {
075 mainFace = getXFace(direction);
076 mainDirection = getXLength(direction);
077 mainPosition = getXPosition(direction, startClone, startBlock);
078
079 secondFace = getYFace(direction);
080 secondDirection = getYLength(direction);
081 secondPosition = getYPosition(direction, startClone, startBlock);
082
083 thirdFace = getZFace(direction);
084 thirdDirection = getZLength(direction);
085 thirdPosition = getZPosition(direction, startClone, startBlock);
086 }
087 if (getYLength(direction) > mainDirection) {
088 mainFace = getYFace(direction);
089 mainDirection = getYLength(direction);
090 mainPosition = getYPosition(direction, startClone, startBlock);
091
092 secondFace = getZFace(direction);
093 secondDirection = getZLength(direction);
094 secondPosition = getZPosition(direction, startClone, startBlock);
095
096 thirdFace = getXFace(direction);
097 thirdDirection = getXLength(direction);
098 thirdPosition = getXPosition(direction, startClone, startBlock);
099 }
100 if (getZLength(direction) > mainDirection) {
101 mainFace = getZFace(direction);
102 mainDirection = getZLength(direction);
103 mainPosition = getZPosition(direction, startClone, startBlock);
104
105 secondFace = getXFace(direction);
106 secondDirection = getXLength(direction);
107 secondPosition = getXPosition(direction, startClone, startBlock);
108
109 thirdFace = getYFace(direction);
110 thirdDirection = getYLength(direction);
111 thirdPosition = getYPosition(direction, startClone, startBlock);
112 }
113
114 // trace line backwards to find intercept with plane perpendicular to the main axis
115
116 double d = mainPosition / mainDirection; // how far to hit face behind
117 double secondd = secondPosition - secondDirection * d;
118 double thirdd = thirdPosition - thirdDirection * d;
119
120 // Guarantee that the ray will pass though the start block.
121 // It is possible that it would miss due to rounding
122 // This should only move the ray by 1 grid position
123 secondError = floor(secondd * gridSize);
124 secondStep = round(secondDirection / mainDirection * gridSize);
125 thirdError = floor(thirdd * gridSize);
126 thirdStep = round(thirdDirection / mainDirection * gridSize);
127
128 if (secondError + secondStep <= 0) {
129 secondError = -secondStep + 1;
130 }
131
132 if (thirdError + thirdStep <= 0) {
133 thirdError = -thirdStep + 1;
134 }
135
136 Block lastBlock;
137
138 lastBlock = startBlock.getRelative(mainFace.getOppositeFace());
139
140 if (secondError < 0) {
141 secondError += gridSize;
142 lastBlock = lastBlock.getRelative(secondFace.getOppositeFace());
143 }
144
145 if (thirdError < 0) {
146 thirdError += gridSize;
147 lastBlock = lastBlock.getRelative(thirdFace.getOppositeFace());
148 }
149
150 // This means that when the variables are positive, it means that the coord=1 boundary has been crossed
151 secondError -= gridSize;
152 thirdError -= gridSize;
153
154 blockQueue[0] = lastBlock;
155 currentBlock = -1;
156
157 scan();
158
159 boolean startBlockFound = false;
160
161 for (int cnt = currentBlock; cnt >= 0; cnt--) {
162 if (blockEquals(blockQueue[cnt], startBlock)) {
163 currentBlock = cnt;
164 startBlockFound = true;
165 break;
166 }
167 }
168
169 if (!startBlockFound) {
170 throw new IllegalStateException("Start block missed in BlockIterator");
171 }
172
173 // Calculate the number of planes passed to give max distance
174 maxDistanceInt = round(maxDistance / (Math.sqrt(mainDirection * mainDirection + secondDirection * secondDirection + thirdDirection * thirdDirection) / mainDirection));
175
176 }
177
178 private boolean blockEquals(Block a, Block b) {
179 return a.getX() == b.getX() && a.getY() == b.getY() && a.getZ() == b.getZ();
180 }
181
182 private BlockFace getXFace(Vector direction) {
183 return ((direction.getX() > 0) ? BlockFace.EAST : BlockFace.WEST);
184 }
185
186 private BlockFace getYFace(Vector direction) {
187 return ((direction.getY() > 0) ? BlockFace.UP : BlockFace.DOWN);
188 }
189
190 private BlockFace getZFace(Vector direction) {
191 return ((direction.getZ() > 0) ? BlockFace.SOUTH : BlockFace.NORTH);
192 }
193
194 private double getXLength(Vector direction) {
195 return Math.abs(direction.getX());
196 }
197
198 private double getYLength(Vector direction) {
199 return Math.abs(direction.getY());
200 }
201
202 private double getZLength(Vector direction) {
203 return Math.abs(direction.getZ());
204 }
205
206 private double getPosition(double direction, double position, int blockPosition) {
207 return direction > 0 ? (position - blockPosition) : (blockPosition + 1 - position);
208 }
209
210 private double getXPosition(Vector direction, Vector position, Block block) {
211 return getPosition(direction.getX(), position.getX(), block.getX());
212 }
213
214 private double getYPosition(Vector direction, Vector position, Block block) {
215 return getPosition(direction.getY(), position.getY(), block.getY());
216 }
217
218 private double getZPosition(Vector direction, Vector position, Block block) {
219 return getPosition(direction.getZ(), position.getZ(), block.getZ());
220 }
221
222 /**
223 * Constructs the BlockIterator
224 *
225 * @param loc The location for the start of the ray trace
226 * @param yOffset The trace begins vertically offset from the start vector
227 * by this value
228 * @param maxDistance This is the maximum distance in blocks for the
229 * trace. Setting this value above 140 may lead to problems with
230 * unloaded chunks. A value of 0 indicates no limit
231 */
232 public BlockIterator(Location loc, double yOffset, int maxDistance) {
233 this(loc.getWorld(), loc.toVector(), loc.getDirection(), yOffset, maxDistance);
234 }
235
236 /**
237 * Constructs the BlockIterator.
238 *
239 * @param loc The location for the start of the ray trace
240 * @param yOffset The trace begins vertically offset from the start vector
241 * by this value
242 */
243
244 public BlockIterator(Location loc, double yOffset) {
245 this(loc.getWorld(), loc.toVector(), loc.getDirection(), yOffset, 0);
246 }
247
248 /**
249 * Constructs the BlockIterator.
250 *
251 * @param loc The location for the start of the ray trace
252 */
253
254 public BlockIterator(Location loc) {
255 this(loc, 0D);
256 }
257
258 /**
259 * Constructs the BlockIterator.
260 *
261 * @param entity Information from the entity is used to set up the trace
262 * @param maxDistance This is the maximum distance in blocks for the
263 * trace. Setting this value above 140 may lead to problems with
264 * unloaded chunks. A value of 0 indicates no limit
265 */
266
267 public BlockIterator(LivingEntity entity, int maxDistance) {
268 this(entity.getLocation(), entity.getEyeHeight(), maxDistance);
269 }
270
271 /**
272 * Constructs the BlockIterator.
273 *
274 * @param entity Information from the entity is used to set up the trace
275 */
276
277 public BlockIterator(LivingEntity entity) {
278 this(entity, 0);
279 }
280
281 /**
282 * Returns true if the iteration has more elements
283 */
284
285 public boolean hasNext() {
286 scan();
287 return currentBlock != -1;
288 }
289
290 /**
291 * Returns the next Block in the trace
292 *
293 * @return the next Block in the trace
294 */
295
296 public Block next() {
297 scan();
298 if (currentBlock <= -1) {
299 throw new NoSuchElementException();
300 } else {
301 return blockQueue[currentBlock--];
302 }
303 }
304
305 public void remove() {
306 throw new UnsupportedOperationException("[BlockIterator] doesn't support block removal");
307 }
308
309 private void scan() {
310 if (currentBlock >= 0) {
311 return;
312 }
313 if (maxDistance != 0 && currentDistance > maxDistanceInt) {
314 end = true;
315 return;
316 }
317 if (end) {
318 return;
319 }
320
321 currentDistance++;
322
323 secondError += secondStep;
324 thirdError += thirdStep;
325
326 if (secondError > 0 && thirdError > 0) {
327 blockQueue[2] = blockQueue[0].getRelative(mainFace);
328 if (((long) secondStep) * ((long) thirdError) < ((long) thirdStep) * ((long) secondError)) {
329 blockQueue[1] = blockQueue[2].getRelative(secondFace);
330 blockQueue[0] = blockQueue[1].getRelative(thirdFace);
331 } else {
332 blockQueue[1] = blockQueue[2].getRelative(thirdFace);
333 blockQueue[0] = blockQueue[1].getRelative(secondFace);
334 }
335 thirdError -= gridSize;
336 secondError -= gridSize;
337 currentBlock = 2;
338 return;
339 } else if (secondError > 0) {
340 blockQueue[1] = blockQueue[0].getRelative(mainFace);
341 blockQueue[0] = blockQueue[1].getRelative(secondFace);
342 secondError -= gridSize;
343 currentBlock = 1;
344 return;
345 } else if (thirdError > 0) {
346 blockQueue[1] = blockQueue[0].getRelative(mainFace);
347 blockQueue[0] = blockQueue[1].getRelative(thirdFace);
348 thirdError -= gridSize;
349 currentBlock = 1;
350 return;
351 } else {
352 blockQueue[0] = blockQueue[0].getRelative(mainFace);
353 currentBlock = 0;
354 return;
355 }
356 }
357 }