BlueGit

timfa copperfarmer

Files

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

TreeIndex.java

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