Fork of Poseidon providing Bukkit #1060 to older Beta versions (b1.0-b1.7.3)
keii.dev
1package org.bukkit.util;
2
3import org.bukkit.Location;
4import org.bukkit.World;
5import org.bukkit.block.Block;
6import org.bukkit.block.BlockFace;
7import org.bukkit.entity.LivingEntity;
8
9import java.util.Iterator;
10import java.util.NoSuchElementException;
11
12/**
13 * This class performs ray tracing and iterates along blocks on a line
14 *
15 * @author raphfrk
16 */
17
18public class BlockIterator implements Iterator<Block> {
19
20 private final World world;
21 private final int maxDistance;
22
23 private static final int gridSize = 1 << 24;
24
25 private boolean end = false;
26
27 private Block[] blockQueue = new Block[3];
28 private int currentBlock = 0;
29 private int currentDistance = 0;
30 private int maxDistanceInt;
31
32 private int secondError;
33 private int thirdError;
34
35 private int secondStep;
36 private int thirdStep;
37
38 private BlockFace mainFace;
39 private BlockFace secondFace;
40 private BlockFace thirdFace;
41
42 /**
43 * Constructs the BlockIterator
44 *
45 * @param world The world to use for tracing
46 * @param start A Vector giving the initial location for the trace
47 * @param direction A Vector pointing in the direction for the trace
48 * @param yOffset The trace begins vertically offset from the start vector by this value
49 * @param maxDistance This is the maximum distance in blocks for the trace. Setting this value above 140 may lead to problems with unloaded chunks. A value of 0 indicates no limit
50 */
51
52 public BlockIterator(World world, Vector start, Vector direction, double yOffset, int maxDistance) {
53 this.world = world;
54 this.maxDistance = maxDistance;
55
56 Vector startClone = start.clone();
57
58 startClone.setY(startClone.getY() + yOffset);
59
60 currentDistance = 0;
61
62 double mainDirection = 0;
63 double secondDirection = 0;
64 double thirdDirection = 0;
65
66 double mainPosition = 0;
67 double secondPosition = 0;
68 double thirdPosition = 0;
69
70 Block startBlock = world.getBlockAt((int) Math.floor(startClone.getX()), (int) Math.floor(startClone.getY()), (int) Math.floor(startClone.getZ()));
71
72 if (getXLength(direction) > mainDirection) {
73 mainFace = getXFace(direction);
74 mainDirection = getXLength(direction);
75 mainPosition = getXPosition(direction, startClone, startBlock);
76
77 secondFace = getYFace(direction);
78 secondDirection = getYLength(direction);
79 secondPosition = getYPosition(direction, startClone, startBlock);
80
81 thirdFace = getZFace(direction);
82 thirdDirection = getZLength(direction);
83 thirdPosition = getZPosition(direction, startClone, startBlock);
84 }
85 if (getYLength(direction) > mainDirection) {
86 mainFace = getYFace(direction);
87 mainDirection = getYLength(direction);
88 mainPosition = getYPosition(direction, startClone, startBlock);
89
90 secondFace = getZFace(direction);
91 secondDirection = getZLength(direction);
92 secondPosition = getZPosition(direction, startClone, startBlock);
93
94 thirdFace = getXFace(direction);
95 thirdDirection = getXLength(direction);
96 thirdPosition = getXPosition(direction, startClone, startBlock);
97 }
98 if (getZLength(direction) > mainDirection) {
99 mainFace = getZFace(direction);
100 mainDirection = getZLength(direction);
101 mainPosition = getZPosition(direction, startClone, startBlock);
102
103 secondFace = getXFace(direction);
104 secondDirection = getXLength(direction);
105 secondPosition = getXPosition(direction, startClone, startBlock);
106
107 thirdFace = getYFace(direction);
108 thirdDirection = getYLength(direction);
109 thirdPosition = getYPosition(direction, startClone, startBlock);
110 }
111
112 // trace line backwards to find intercept with plane perpendicular to the main axis
113
114 double d = mainPosition / mainDirection; // how far to hit face behind
115 double secondd = secondPosition - secondDirection * d;
116 double thirdd = thirdPosition - thirdDirection * d;
117
118 // Guarantee that the ray will pass though the start block.
119 // It is possible that it would miss due to rounding
120 // This should only move the ray by 1 grid position
121 secondError = (int) (Math.floor(secondd * gridSize));
122 secondStep = (int) (Math.round(secondDirection / mainDirection * gridSize));
123 thirdError = (int) (Math.floor(thirdd * gridSize));
124 thirdStep = (int) (Math.round(thirdDirection / mainDirection * gridSize));
125
126 if (secondError + secondStep <= 0) {
127 secondError = -secondStep + 1;
128 }
129
130 if (thirdError + thirdStep <= 0) {
131 thirdError = -thirdStep + 1;
132 }
133
134 Block lastBlock;
135
136 lastBlock = startBlock.getRelative(reverseFace(mainFace));
137
138 if (secondError < 0) {
139 secondError += gridSize;
140 lastBlock = lastBlock.getRelative(reverseFace(secondFace));
141 }
142
143 if (thirdError < 0) {
144 thirdError += gridSize;
145 lastBlock = lastBlock.getRelative(reverseFace(thirdFace));
146 }
147
148 // This means that when the variables are positive, it means that the coord=1 boundary has been crossed
149 secondError -= gridSize;
150 thirdError -= gridSize;
151
152 blockQueue[0] = lastBlock;
153 currentBlock = -1;
154
155 scan();
156
157 boolean startBlockFound = false;
158
159 for (int cnt = currentBlock; cnt >= 0; cnt--) {
160 if (blockEquals(blockQueue[cnt], startBlock)) {
161 currentBlock = cnt;
162 startBlockFound = true;
163 break;
164 }
165 }
166
167 if (!startBlockFound) {
168 throw new IllegalStateException("Start block missed in BlockIterator");
169 }
170
171 // Calculate the number of planes passed to give max distance
172 maxDistanceInt = (int) Math.round(maxDistance / (Math.sqrt(mainDirection * mainDirection + secondDirection * secondDirection + thirdDirection * thirdDirection) / mainDirection));
173
174 }
175
176 private boolean blockEquals(Block a, Block b) {
177 return a.getX() == b.getX() && a.getY() == b.getY() && a.getZ() == b.getZ();
178 }
179
180 private BlockFace reverseFace(BlockFace face) {
181 switch (face) {
182 case UP:
183 return BlockFace.DOWN;
184
185 case DOWN:
186 return BlockFace.UP;
187
188 case NORTH:
189 return BlockFace.SOUTH;
190
191 case SOUTH:
192 return BlockFace.NORTH;
193
194 case EAST:
195 return BlockFace.WEST;
196
197 case WEST:
198 return BlockFace.EAST;
199
200 default:
201 return null;
202 }
203 }
204
205 private BlockFace getXFace(Vector direction) {
206 return ((direction.getX() > 0) ? BlockFace.SOUTH : BlockFace.NORTH);
207 }
208
209 private BlockFace getYFace(Vector direction) {
210 return ((direction.getY() > 0) ? BlockFace.UP : BlockFace.DOWN);
211 }
212
213 private BlockFace getZFace(Vector direction) {
214 return ((direction.getZ() > 0) ? BlockFace.WEST : BlockFace.EAST);
215 }
216
217 private double getXLength(Vector direction) {
218 return (Math.abs(direction.getX()));
219 }
220
221 private double getYLength(Vector direction) {
222 return (Math.abs(direction.getY()));
223 }
224
225 private double getZLength(Vector direction) {
226 return (Math.abs(direction.getZ()));
227 }
228
229 private double getPosition(double direction, double position, int blockPosition) {
230 return direction > 0 ? (position - blockPosition) : (blockPosition + 1 - position);
231 }
232
233 private double getXPosition(Vector direction, Vector position, Block block) {
234 return getPosition(direction.getX(), position.getX(), block.getX());
235 }
236
237 private double getYPosition(Vector direction, Vector position, Block block) {
238 return getPosition(direction.getY(), position.getY(), block.getY());
239 }
240
241 private double getZPosition(Vector direction, Vector position, Block block) {
242 return getPosition(direction.getZ(), position.getZ(), block.getZ());
243 }
244
245 /**
246 * Constructs the BlockIterator
247 *
248 * @param loc The location for the start of the ray trace
249 * @param yOffset The trace begins vertically offset from the start vector by this value
250 * @param maxDistance This is the maximum distance in blocks for the trace. Setting this value above 140 may lead to problems with unloaded chunks. A value of 0 indicates no limit
251 */
252
253 public BlockIterator(Location loc, double yOffset, int maxDistance) {
254 this(loc.getWorld(), loc.toVector(), loc.getDirection(), yOffset, maxDistance);
255 }
256
257 /**
258 * Constructs the BlockIterator.
259 *
260 * @param loc The location for the start of the ray trace
261 * @param yOffset The trace begins vertically offset from the start vector by this value
262 */
263
264 public BlockIterator(Location loc, double yOffset) {
265 this(loc.getWorld(), loc.toVector(), loc.getDirection(), yOffset, 0);
266 }
267
268 /**
269 * Constructs the BlockIterator.
270 *
271 * @param loc The location for the start of the ray trace
272 */
273
274 public BlockIterator(Location loc) {
275 this(loc, 0D);
276 }
277
278 /**
279 * Constructs the BlockIterator.
280 *
281 * @param entity Information from the entity is used to set up the trace
282 * @param maxDistance This is the maximum distance in blocks for the trace. Setting this value above 140 may lead to problems with unloaded chunks. A value of 0 indicates no limit
283 */
284
285 public BlockIterator(LivingEntity entity, int maxDistance) {
286 this(entity.getLocation(), entity.getEyeHeight(), maxDistance);
287 }
288
289 /**
290 * Constructs the BlockIterator.
291 *
292 * @param entity Information from the entity is used to set up the trace
293 */
294
295 public BlockIterator(LivingEntity entity) {
296 this(entity, 0);
297 }
298
299 /**
300 * Returns true if the iteration has more elements
301 */
302
303 public boolean hasNext() {
304 scan();
305 return currentBlock != -1;
306 }
307
308 /**
309 * Returns the next Block in the trace
310 *
311 * @return the next Block in the trace
312 */
313
314 public Block next() {
315 scan();
316 if (currentBlock <= -1) {
317 throw new NoSuchElementException();
318 } else {
319 return blockQueue[currentBlock--];
320 }
321 }
322
323 public void remove() {
324 throw new UnsupportedOperationException("[BlockIterator] doesn't support block removal");
325 }
326
327 private void scan() {
328 if (currentBlock >= 0) {
329 return;
330 }
331 if (maxDistance != 0 && currentDistance > maxDistanceInt) {
332 end = true;
333 return;
334 }
335 if (end) {
336 return;
337 }
338
339 currentDistance++;
340
341 secondError += secondStep;
342 thirdError += thirdStep;
343
344 if (secondError > 0 && thirdError > 0) {
345 blockQueue[2] = blockQueue[0].getRelative(mainFace);
346 if (((long) secondStep) * ((long) thirdError) < ((long) thirdStep) * ((long) secondError)) {
347 blockQueue[1] = blockQueue[2].getRelative(secondFace);
348 blockQueue[0] = blockQueue[1].getRelative(thirdFace);
349 } else {
350 blockQueue[1] = blockQueue[2].getRelative(thirdFace);
351 blockQueue[0] = blockQueue[1].getRelative(secondFace);
352 }
353 thirdError -= gridSize;
354 secondError -= gridSize;
355 currentBlock = 2;
356 return;
357 } else if (secondError > 0) {
358 blockQueue[1] = blockQueue[0].getRelative(mainFace);
359 blockQueue[0] = blockQueue[1].getRelative(secondFace);
360 secondError -= gridSize;
361 currentBlock = 1;
362 return;
363 } else if (thirdError > 0) {
364 blockQueue[1] = blockQueue[0].getRelative(mainFace);
365 blockQueue[0] = blockQueue[1].getRelative(thirdFace);
366 thirdError -= gridSize;
367 currentBlock = 1;
368 return;
369 } else {
370 blockQueue[0] = blockQueue[0].getRelative(mainFace);
371 currentBlock = 0;
372 return;
373 }
374 }
375}