BlueGit

timfa copperfarmer

Files

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

TreeIndex.java

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