BlueGit

timfa copperfarmer

Files

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

TreeIndex.java

TreeIndex.java 18.8 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 (BlockFace face : ALL_SIX) {
283 Block next = current.getRelative(face);
284 if (!isChunkLoaded(next) || next.getType() != logType) continue;
285 if (found.add(BlockRef.of(next))) queue.addLast(next);
286 }
287 }
288 return found;
289 }
290
291 private void enqueueAdjacentLeaves(
292 BlockRef log,
293 Set<Material> allowedLeaves,
294 Set<BlockRef> visitedLeaves,
295 Deque<Block> leafQueue
296 ) {
297 Block block = log.blockIfLoaded();
298 if (block == null) return;
299 for (BlockFace face : ALL_SIX) {
300 Block next = block.getRelative(face);
301 if (!isChunkLoaded(next) || !registry.isNaturalLeaf(next, allowedLeaves)) continue;
302 if (visitedLeaves.add(BlockRef.of(next))) leafQueue.addLast(next);
303 }
304 }
305
306 private Set<BlockRef> feetOf(World world, Set<BlockRef> logs, Material logType) {
307 Set<BlockRef> feet = new HashSet<>();
308 for (BlockRef log : logs) {
309 if (world == null || !world.isChunkLoaded(log.chunkX(), log.chunkZ())) continue;
310 Block below = world.getBlockAt(log.x(), log.y() - 1, log.z());
311 if (below.getType() == logType) continue;
312 if (registry.isValidSoil(below.getType())) feet.add(log);
313 }
314 return feet;
315 }
316
317 private boolean isOtherTree(Set<BlockRef> ourFeet, Set<BlockRef> theirFeet) {
318 if (theirFeet.isEmpty()) return false;
319 for (BlockRef foot : theirFeet) {
320 if (!ourFeet.contains(foot)) return true;
321 }
322 return false;
323 }
324
325 private DetectedTree validate(
326 World world,
327 Material logType,
328 Set<Material> allowedLeaves,
329 Set<BlockRef> logs,
330 Set<BlockRef> seenLeafBlocks
331 ) {
332 if (world == null) return null;
333 Set<Material> seenLeaves = new HashSet<>();
334 for (BlockRef leafRef : seenLeafBlocks) {
335 Block leaf = leafRef.blockIfLoaded();
336 if (leaf != null) seenLeaves.add(leaf.getType());
337 }
338
339 int highestY = Integer.MIN_VALUE;
340 for (BlockRef log : logs) highestY = Math.max(highestY, log.y());
341 boolean topHasLeaves = false;
342
343 for (BlockRef log : logs) {
344 Block block = log.blockIfLoaded();
345 if (block == null || block.getType() != logType) return null;
346 if (strictMode) {
347 for (BlockFace face : HORIZONTAL) {
348 Block neighbour = block.getRelative(face);
349 if (!registry.isAllowedHorizontal(neighbour.getType(), logType, allowedLeaves, neighbour)) {
350 return null;
351 }
352 }
353 }
354 if (log.y() == highestY) {
355 for (BlockFace face : ALL_SIX) {
356 if (registry.isNaturalLeaf(block.getRelative(face), allowedLeaves)) {
357 topHasLeaves = true;
358 seenLeaves.add(block.getRelative(face).getType());
359 break;
360 }
361 }
362 }
363 }
364 if (!topHasLeaves) return null;
365
366 TreeRegistry.Species species = registry.classify(logType, seenLeaves);
367 if (species == null) return null;
368
369 Set<BlockRef> feet = feetOf(world, logs, logType);
370 List<BlockRef> plantSpots = plantSpots(feet, logs);
371 if (plantSpots.isEmpty()) return null;
372
373 List<BlockRef> ordered = new ArrayList<>(logs);
374 return new DetectedTree(species, ordered, plantSpots);
375 }
376
377 private List<BlockRef> plantSpots(Set<BlockRef> feet, Set<BlockRef> logs) {
378 if (feet.isEmpty()) return List.of();
379 List<BlockRef> asList = new ArrayList<>(feet);
380 if (asList.size() == 4 && isTwoByTwo(asList)) return asList;
381 return List.of(primaryFoot(asList, logs));
382 }
383
384 private boolean isTwoByTwo(List<BlockRef> feet) {
385 int minX = Integer.MAX_VALUE, maxX = Integer.MIN_VALUE;
386 int minZ = Integer.MAX_VALUE, maxZ = Integer.MIN_VALUE;
387 Integer y = null;
388 Set<Long> xz = new HashSet<>();
389 for (BlockRef foot : feet) {
390 if (y == null) y = foot.y();
391 if (foot.y() != y) return false;
392 minX = Math.min(minX, foot.x());
393 maxX = Math.max(maxX, foot.x());
394 minZ = Math.min(minZ, foot.z());
395 maxZ = Math.max(maxZ, foot.z());
396 xz.add((((long) foot.x()) << 32) ^ (foot.z() & 0xffffffffL));
397 }
398 return xz.size() == 4 && maxX - minX == 1 && maxZ - minZ == 1;
399 }
400
401 private BlockRef primaryFoot(List<BlockRef> feet, Set<BlockRef> logs) {
402 BlockRef best = feet.getFirst();
403 int bestCount = -1;
404 for (BlockRef foot : feet) {
405 int count = 0;
406 for (BlockRef log : logs) {
407 if (log.x() == foot.x() && log.z() == foot.z()) count++;
408 }
409 if (count > bestCount) {
410 bestCount = count;
411 best = foot;
412 }
413 }
414 return best;
415 }
416
417 private void addTree(DetectedTree tree) {
418 trees.put(tree.id(), tree);
419 for (BlockRef log : tree.logs()) logToTree.put(log, tree.id());
420 }
421
422 private void invalidateTree(DetectedTree tree) {
423 removeTree(tree.id());
424 Set<ChunkKey> dirty = new HashSet<>();
425 for (BlockRef log : tree.logs()) {
426 dirty.add(new ChunkKey(log.worldId(), log.chunkX(), log.chunkZ()));
427 }
428 for (ChunkKey key : dirty) {
429 ChunkScan scan = chunks.get(key);
430 if (scan == null) {
431 scan = new ChunkScan(key);
432 chunks.put(key, scan);
433 }
434 if (scan.status == Status.SCANNING) continue;
435 scan.status = Status.DIRTY;
436 scan.nextColumn = 0;
437 }
438 }
439
440 private void invalidateChunk(UUID worldId, int chunkX, int chunkZ) {
441 ChunkKey key = new ChunkKey(worldId, chunkX, chunkZ);
442 removeTreesTouching(key);
443 ChunkScan scan = chunks.get(key);
444 if (scan == null) {
445 scan = new ChunkScan(key);
446 chunks.put(key, scan);
447 }
448 if (scan.status != Status.SCANNING) {
449 scan.status = Status.DIRTY;
450 scan.nextColumn = 0;
451 }
452 }
453
454 private void forceInvalidateChunk(UUID worldId, int chunkX, int chunkZ) {
455 ChunkKey key = new ChunkKey(worldId, chunkX, chunkZ);
456 removeTreesTouching(key);
457 ChunkScan scan = chunks.get(key);
458 if (scan == null) {
459 scan = new ChunkScan(key);
460 chunks.put(key, scan);
461 }
462 scan.status = Status.DIRTY;
463 scan.nextColumn = 0;
464 }
465
466 private void removeTreesTouching(ChunkKey key) {
467 List<UUID> remove = new ArrayList<>();
468 for (DetectedTree tree : trees.values()) {
469 if (tree.touchesChunk(key.worldId(), key.x(), key.z())) remove.add(tree.id());
470 }
471 for (UUID id : remove) removeTree(id);
472 }
473
474 private void removeTree(UUID id) {
475 DetectedTree tree = trees.remove(id);
476 if (tree == null) return;
477 for (BlockRef log : tree.logs()) logToTree.remove(log, id);
478 }
479
480 private static boolean isChunkLoaded(Block block) {
481 return block.getWorld().isChunkLoaded(block.getX() >> 4, block.getZ() >> 4);
482 }
483
484 private enum Status {
485 SCANNING,
486 READY,
487 DIRTY
488 }
489
490 private record ChunkKey(UUID worldId, int x, int z) {}
491
492 private static final class ChunkScan {
493 final ChunkKey key;
494 Status status = Status.DIRTY;
495 int nextColumn;
496
497 ChunkScan(ChunkKey key) {
498 this.key = key;
499 }
500 }
501}