BlueGit

timfa copperfarmer

Files

copperfarmer / src / main / java / nl / timfalken / copperfarmer / TreeIndex.java

TreeIndex.java

b3f01c29 History
TreeIndex.java 17.5 KiB Download Raw
1package nl.timfalken.copperfarmer;
2
3import org.bukkit.Bukkit;
4import org.bukkit.HeightMap;
5import org.bukkit.Material;
6import org.bukkit.World;
7import org.bukkit.block.Block;
8import org.bukkit.block.BlockFace;
9import org.bukkit.event.world.StructureGrowEvent;
10import org.bukkit.plugin.Plugin;
11
12import java.util.ArrayDeque;
13import java.util.ArrayList;
14import java.util.Deque;
15import java.util.HashMap;
16import java.util.HashSet;
17import java.util.List;
18import java.util.Map;
19import java.util.Set;
20import java.util.UUID;
21
22final class TreeIndex {
23 private static final BlockFace[] ALL_SIX = {
24 BlockFace.UP, BlockFace.DOWN, BlockFace.NORTH, BlockFace.SOUTH, BlockFace.EAST, BlockFace.WEST
25 };
26 private static final BlockFace[] HORIZONTAL = {
27 BlockFace.NORTH, BlockFace.SOUTH, BlockFace.EAST, BlockFace.WEST
28 };
29
30 private final TreeRegistry registry;
31 private final int columnsPerTick;
32 private final int detectsPerTick;
33 private final int maxChunksPerTick;
34 private final int maxLogs;
35 private final int maxLeafVisits;
36 private final int scanAboveGround;
37
38 private final Map<ChunkKey, ChunkScan> chunks = new HashMap<>();
39 private final Map<UUID, DetectedTree> trees = new HashMap<>();
40 private final Map<BlockRef, UUID> logToTree = new HashMap<>();
41
42 TreeIndex(Plugin plugin, TreeRegistry registry) {
43 this.registry = registry;
44 this.columnsPerTick = Math.max(1, plugin.getConfig().getInt("tree-scan-columns-per-tick", 32));
45 this.detectsPerTick = Math.max(1, plugin.getConfig().getInt("tree-detects-per-tick", 2));
46 this.maxChunksPerTick = Math.max(1, plugin.getConfig().getInt("tree-scan-max-chunks-per-tick", 2));
47 this.maxLogs = Math.max(8, plugin.getConfig().getInt("tree-max-logs", 64));
48 this.maxLeafVisits = Math.max(32, plugin.getConfig().getInt("tree-max-leaf-visits", 128));
49 this.scanAboveGround = Math.max(8, plugin.getConfig().getInt("tree-scan-above-ground", 40));
50 }
51
52 void tick() {
53 int columnsLeft = columnsPerTick * maxChunksPerTick;
54 int detectsLeft = detectsPerTick * maxChunksPerTick;
55 int chunksWorked = 0;
56 for (ChunkScan scan : chunks.values()) {
57 if (scan.status != Status.SCANNING) continue;
58 if (chunksWorked >= maxChunksPerTick) break;
59 World world = Bukkit.getWorld(scan.key.worldId());
60 if (world == null || !world.isChunkLoaded(scan.key.x(), scan.key.z())) continue;
61
62 chunksWorked++;
63 int started = scan.nextColumn;
64 while (scan.nextColumn < 256 && columnsLeft > 0 && detectsLeft > 0) {
65 columnsLeft--;
66 if (scanColumn(world, scan, scan.nextColumn)) detectsLeft--;
67 scan.nextColumn++;
68 }
69 if (scan.nextColumn >= 256) {
70 scan.status = Status.READY;
71 } else if (scan.nextColumn == started) {
72 break;
73 }
74 }
75 }
76
77 void requestChunk(World world, int chunkX, int chunkZ) {
78 if (world == null || !world.isChunkLoaded(chunkX, chunkZ)) return;
79 ChunkKey key = new ChunkKey(world.getUID(), chunkX, chunkZ);
80 ChunkScan scan = chunks.get(key);
81 if (scan == null) {
82 scan = new ChunkScan(key);
83 chunks.put(key, scan);
84 }
85 if (scan.status == Status.READY) return;
86 if (scan.status == Status.DIRTY) {
87 removeTreesTouching(key);
88 scan.nextColumn = 0;
89 }
90 scan.status = Status.SCANNING;
91 }
92
93 void requestAround(Block origin, int radius) {
94 if (origin == null) return;
95 World world = origin.getWorld();
96 int chunkRadius = (radius >> 4) + 2;
97 int centerX = origin.getChunk().getX();
98 int centerZ = origin.getChunk().getZ();
99 for (int cx = centerX - chunkRadius; cx <= centerX + chunkRadius; cx++) {
100 for (int cz = centerZ - chunkRadius; cz <= centerZ + chunkRadius; cz++) {
101 requestChunk(world, cx, cz);
102 }
103 }
104 }
105
106 boolean isScanningAround(Block origin, int radius) {
107 if (origin == null) return false;
108 int chunkRadius = (radius >> 4) + 2;
109 int centerX = origin.getChunk().getX();
110 int centerZ = origin.getChunk().getZ();
111 UUID worldId = origin.getWorld().getUID();
112 for (int cx = centerX - chunkRadius; cx <= centerX + chunkRadius; cx++) {
113 for (int cz = centerZ - chunkRadius; cz <= centerZ + chunkRadius; cz++) {
114 ChunkScan scan = chunks.get(new ChunkKey(worldId, cx, cz));
115 if (scan != null && scan.status == Status.SCANNING) return true;
116 }
117 }
118 return false;
119 }
120
121 DetectedTree findAvailable(Block origin, int radius, UUID golemId, Set<UUID> unreachable) {
122 if (origin == null) return null;
123 DetectedTree best = null;
124 double bestDistance = Double.MAX_VALUE;
125 for (DetectedTree tree : trees.values()) {
126 if (!tree.isAvailableFor(golemId)) continue;
127 if (unreachable.contains(tree.id())) continue;
128 if (!tree.hasLogWithin(origin, radius)) continue;
129 if (!tree.stillPresent(origin.getWorld())) {
130 invalidateTree(tree);
131 continue;
132 }
133 BlockRef first = tree.standOrder().getFirst();
134 double dx = first.x() + 0.5 - origin.getX();
135 double dz = first.z() + 0.5 - origin.getZ();
136 double distance = dx * dx + dz * dz;
137 if (distance < bestDistance) {
138 bestDistance = distance;
139 best = tree;
140 }
141 }
142 return best;
143 }
144
145 DetectedTree tree(UUID id) {
146 return id == null ? null : trees.get(id);
147 }
148
149 void invalidateExpectedLog(BlockRef ref) {
150 UUID treeId = logToTree.get(ref);
151 if (treeId == null) {
152 invalidateChunk(ref.worldId(), ref.chunkX(), ref.chunkZ());
153 return;
154 }
155 DetectedTree tree = trees.get(treeId);
156 if (tree != null) invalidateTree(tree);
157 }
158
159 void onStructureGrow(StructureGrowEvent event) {
160 Set<ChunkKey> dirty = new HashSet<>();
161 World world = event.getWorld();
162 for (org.bukkit.block.BlockState state : event.getBlocks()) {
163 dirty.add(new ChunkKey(world.getUID(), state.getX() >> 4, state.getZ() >> 4));
164 }
165 dirty.add(new ChunkKey(world.getUID(), event.getLocation().getBlockX() >> 4, event.getLocation().getBlockZ() >> 4));
166 for (ChunkKey key : dirty) invalidateChunk(key.worldId(), key.x(), key.z());
167 }
168
169 void onBlockChanged(Block block) {
170 if (block == null) return;
171 BlockRef ref = BlockRef.of(block);
172 if (logToTree.containsKey(ref)) invalidateExpectedLog(ref);
173 }
174
175 void onLogGone(BlockRef ref) {
176 invalidateExpectedLog(ref);
177 }
178
179 private boolean scanColumn(World world, ChunkScan scan, int column) {
180 int x = (scan.key.x() << 4) + (column & 15);
181 int z = (scan.key.z() << 4) + (column >> 4);
182 int surface = world.getHighestBlockYAt(x, z, HeightMap.MOTION_BLOCKING_NO_LEAVES);
183 int maxY = Math.min(world.getMaxHeight() - 1, surface + scanAboveGround);
184 if (surface < world.getMinHeight()) return false;
185
186 Block surfaceBlock = world.getBlockAt(x, surface, z);
187 if (tryDetect(surfaceBlock)) return true;
188
189 for (int y = surface + 1; y <= maxY; y++) {
190 Block block = world.getBlockAt(x, y, z);
191 if (tryDetect(block)) return true;
192 }
193 return false;
194 }
195
196 private boolean tryDetect(Block block) {
197 if (!registry.isLog(block.getType())) return false;
198 BlockRef ref = BlockRef.of(block);
199 if (logToTree.containsKey(ref)) return false;
200 DetectedTree tree = detect(block);
201 if (tree == null) return true;
202 addTree(tree);
203 return true;
204 }
205
206 private DetectedTree detect(Block start) {
207 Material logType = start.getType();
208 if (!registry.isLog(logType)) return null;
209 Set<Material> allowedLeaves = registry.leavesForLog(logType);
210
211 Set<BlockRef> trunk = floodLogs(start, logType, maxLogs);
212 if (trunk.isEmpty() || trunk.size() > maxLogs) return null;
213
214 Set<BlockRef> ourFeet = feetOf(start.getWorld(), trunk, logType);
215 Set<BlockRef> allLogs = new HashSet<>(trunk);
216 Set<BlockRef> foreign = new HashSet<>();
217 Set<BlockRef> visitedLeaves = new HashSet<>();
218 Deque<Block> leafQueue = new ArrayDeque<>();
219
220 for (BlockRef log : trunk) enqueueAdjacentLeaves(log, allowedLeaves, visitedLeaves, leafQueue);
221
222 int leafVisits = 0;
223 while (!leafQueue.isEmpty() && leafVisits < maxLeafVisits && allLogs.size() <= maxLogs) {
224 Block leaf = leafQueue.pollFirst();
225 leafVisits++;
226 for (BlockFace face : ALL_SIX) {
227 Block next = leaf.getRelative(face);
228 if (!isChunkLoaded(next)) continue;
229 if (registry.isNaturalLeaf(next, allowedLeaves)) {
230 if (visitedLeaves.add(BlockRef.of(next))) leafQueue.addLast(next);
231 continue;
232 }
233 if (next.getType() != logType) continue;
234 BlockRef nextRef = BlockRef.of(next);
235 if (allLogs.contains(nextRef) || foreign.contains(nextRef)) continue;
236
237 Set<BlockRef> component = floodLogs(next, logType, maxLogs);
238 if (component.size() > maxLogs) {
239 foreign.addAll(component);
240 continue;
241 }
242 Set<BlockRef> theirFeet = feetOf(start.getWorld(), component, logType);
243 if (isOtherTree(ourFeet, theirFeet)) {
244 foreign.addAll(component);
245 continue;
246 }
247 allLogs.addAll(component);
248 for (BlockRef log : component) enqueueAdjacentLeaves(log, allowedLeaves, visitedLeaves, leafQueue);
249 }
250 }
251
252 if (allLogs.isEmpty() || allLogs.size() > maxLogs) return null;
253 return validate(start.getWorld(), logType, allowedLeaves, allLogs, visitedLeaves);
254 }
255
256 private Set<BlockRef> floodLogs(Block start, Material logType, int limit) {
257 Set<BlockRef> found = new HashSet<>();
258 Deque<Block> queue = new ArrayDeque<>();
259 queue.add(start);
260 found.add(BlockRef.of(start));
261 while (!queue.isEmpty() && found.size() <= limit) {
262 Block current = queue.pollFirst();
263 for (BlockFace face : ALL_SIX) {
264 Block next = current.getRelative(face);
265 if (!isChunkLoaded(next) || next.getType() != logType) continue;
266 if (found.add(BlockRef.of(next))) queue.addLast(next);
267 }
268 }
269 return found;
270 }
271
272 private void enqueueAdjacentLeaves(
273 BlockRef log,
274 Set<Material> allowedLeaves,
275 Set<BlockRef> visitedLeaves,
276 Deque<Block> leafQueue
277 ) {
278 Block block = log.blockIfLoaded();
279 if (block == null) return;
280 for (BlockFace face : ALL_SIX) {
281 Block next = block.getRelative(face);
282 if (!isChunkLoaded(next) || !registry.isNaturalLeaf(next, allowedLeaves)) continue;
283 if (visitedLeaves.add(BlockRef.of(next))) leafQueue.addLast(next);
284 }
285 }
286
287 private Set<BlockRef> feetOf(World world, Set<BlockRef> logs, Material logType) {
288 Set<BlockRef> feet = new HashSet<>();
289 for (BlockRef log : logs) {
290 if (world == null || !world.isChunkLoaded(log.chunkX(), log.chunkZ())) continue;
291 Block below = world.getBlockAt(log.x(), log.y() - 1, log.z());
292 if (below.getType() == logType) continue;
293 if (registry.isValidSoil(below.getType())) feet.add(log);
294 }
295 return feet;
296 }
297
298 private boolean isOtherTree(Set<BlockRef> ourFeet, Set<BlockRef> theirFeet) {
299 if (theirFeet.isEmpty()) return false;
300 for (BlockRef foot : theirFeet) {
301 if (!ourFeet.contains(foot)) return true;
302 }
303 return false;
304 }
305
306 private DetectedTree validate(
307 World world,
308 Material logType,
309 Set<Material> allowedLeaves,
310 Set<BlockRef> logs,
311 Set<BlockRef> seenLeafBlocks
312 ) {
313 if (world == null) return null;
314 Set<Material> seenLeaves = new HashSet<>();
315 for (BlockRef leafRef : seenLeafBlocks) {
316 Block leaf = leafRef.blockIfLoaded();
317 if (leaf != null) seenLeaves.add(leaf.getType());
318 }
319
320 int highestY = Integer.MIN_VALUE;
321 for (BlockRef log : logs) highestY = Math.max(highestY, log.y());
322 boolean topHasLeaves = false;
323
324 for (BlockRef log : logs) {
325 Block block = log.blockIfLoaded();
326 if (block == null || block.getType() != logType) return null;
327 for (BlockFace face : HORIZONTAL) {
328 Block neighbour = block.getRelative(face);
329 if (!registry.isAllowedHorizontal(neighbour.getType(), logType, allowedLeaves, neighbour)) {
330 return null;
331 }
332 }
333 if (log.y() == highestY) {
334 for (BlockFace face : ALL_SIX) {
335 if (registry.isNaturalLeaf(block.getRelative(face), allowedLeaves)) {
336 topHasLeaves = true;
337 seenLeaves.add(block.getRelative(face).getType());
338 break;
339 }
340 }
341 }
342 }
343 if (!topHasLeaves) return null;
344
345 TreeRegistry.Species species = registry.classify(logType, seenLeaves);
346 if (species == null) return null;
347
348 Set<BlockRef> feet = feetOf(world, logs, logType);
349 List<BlockRef> plantSpots = plantSpots(feet, logs);
350 if (plantSpots.isEmpty()) return null;
351
352 List<BlockRef> ordered = new ArrayList<>(logs);
353 return new DetectedTree(species, ordered, plantSpots);
354 }
355
356 private List<BlockRef> plantSpots(Set<BlockRef> feet, Set<BlockRef> logs) {
357 if (feet.isEmpty()) return List.of();
358 List<BlockRef> asList = new ArrayList<>(feet);
359 if (asList.size() == 4 && isTwoByTwo(asList)) return asList;
360 return List.of(primaryFoot(asList, logs));
361 }
362
363 private boolean isTwoByTwo(List<BlockRef> feet) {
364 int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
365 int minZ = Integer.MAX_VALUE, maxZ = Integer.MIN_VALUE;
366 Integer y = null;
367 Set<Long> xz = new HashSet<>();
368 for (BlockRef foot : feet) {
369 if (y == null) y = foot.y();
370 if (foot.y() != y) return false;
371 minX = Math.min(minX, foot.x());
372 maxX = Math.max(maxX, foot.x());
373 minZ = Math.min(minZ, foot.z());
374 maxZ = Math.max(maxZ, foot.z());
375 xz.add((((long) foot.x()) << 32) ^ (foot.z() & 0xffffffffL));
376 }
377 return xz.size() == 4 && maxX - minX == 1 && maxZ - minZ == 1;
378 }
379
380 private BlockRef primaryFoot(List<BlockRef> feet, Set<BlockRef> logs) {
381 BlockRef best = feet.getFirst();
382 int bestCount = -1;
383 for (BlockRef foot : feet) {
384 int count = 0;
385 for (BlockRef log : logs) {
386 if (log.x() == foot.x() && log.z() == foot.z()) count++;
387 }
388 if (count > bestCount) {
389 bestCount = count;
390 best = foot;
391 }
392 }
393 return best;
394 }
395
396 private void addTree(DetectedTree tree) {
397 trees.put(tree.id(), tree);
398 for (BlockRef log : tree.logs()) logToTree.put(log, tree.id());
399 }
400
401 private void invalidateTree(DetectedTree tree) {
402 removeTree(tree.id());
403 Set<ChunkKey> dirty = new HashSet<>();
404 for (BlockRef log : tree.logs()) {
405 dirty.add(new ChunkKey(log.worldId(), log.chunkX(), log.chunkZ()));
406 }
407 for (ChunkKey key : dirty) {
408 ChunkScan scan = chunks.get(key);
409 if (scan == null) {
410 scan = new ChunkScan(key);
411 chunks.put(key, scan);
412 }
413 if (scan.status == Status.SCANNING) continue;
414 scan.status = Status.DIRTY;
415 scan.nextColumn = 0;
416 }
417 }
418
419 private void invalidateChunk(UUID worldId, int chunkX, int chunkZ) {
420 ChunkKey key = new ChunkKey(worldId, chunkX, chunkZ);
421 removeTreesTouching(key);
422 ChunkScan scan = chunks.get(key);
423 if (scan == null) {
424 scan = new ChunkScan(key);
425 chunks.put(key, scan);
426 }
427 if (scan.status != Status.SCANNING) {
428 scan.status = Status.DIRTY;
429 scan.nextColumn = 0;
430 }
431 }
432
433 private void removeTreesTouching(ChunkKey key) {
434 List<UUID> remove = new ArrayList<>();
435 for (DetectedTree tree : trees.values()) {
436 if (tree.touchesChunk(key.worldId(), key.x(), key.z())) remove.add(tree.id());
437 }
438 for (UUID id : remove) removeTree(id);
439 }
440
441 private void removeTree(UUID id) {
442 DetectedTree tree = trees.remove(id);
443 if (tree == null) return;
444 for (BlockRef log : tree.logs()) logToTree.remove(log, id);
445 }
446
447 private static boolean isChunkLoaded(Block block) {
448 return block.getWorld().isChunkLoaded(block.getX() >> 4, block.getZ() >> 4);
449 }
450
451 private enum Status {
452 SCANNING,
453 READY,
454 DIRTY
455 }
456
457 private record ChunkKey(UUID worldId, int x, int z) {}
458
459 private static final class ChunkScan {
460 final ChunkKey key;
461 Status status = Status.DIRTY;
462 int nextColumn;
463
464 ChunkScan(ChunkKey key) {
465 this.key = key;
466 }
467 }
468}