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    }