Add room matching

4 files changed, 210 insertions, 18 deletions

diff --git a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonMapUtils.java b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonMapUtils.java
index 75bcf86a..dc785084 100644
--- a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonMapUtils.java
+++ b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonMapUtils.java
@@ -3,6 +3,7 @@ package me.xmrvizzy.skyblocker.skyblock.dungeon.secrets;
 import net.minecraft.block.MapColor;
 import net.minecraft.item.map.MapIcon;
 import net.minecraft.item.map.MapState;
+import net.minecraft.util.math.BlockPos;
 import net.minecraft.util.math.MathHelper;
 import net.minecraft.util.math.Vec3d;
 import org.jetbrains.annotations.NotNull;
@@ -130,6 +131,24 @@ public class DungeonMapUtils {
         return new Vector2i(mapPos).sub(mapEntrancePos).div(mapRoomSize + 4).mul(32).add(physicalEntrancePos);
     }
 
+    public static Vector2ic getPhysicalCornerPos(Room.Direction direction, SortedSet<Integer> segmentsX, SortedSet<Integer> segmentsY) {
+        return switch (direction) {
+            case NW -> new Vector2i(segmentsX.first(), segmentsY.first());
+            case NE -> new Vector2i(segmentsX.last() + 30, segmentsY.first());
+            case SW -> new Vector2i(segmentsX.first(), segmentsY.last() + 30);
+            case SE -> new Vector2i(segmentsX.last() + 30, segmentsY.last() + 30);
+        };
+    }
+
+    public static BlockPos actualToRelative(Vector2ic physicalCornerPos, Room.Direction direction, BlockPos pos) {
+        return switch (direction) {
+            case NW -> new BlockPos(pos.getX() - physicalCornerPos.x(), pos.getY(), pos.getZ() - physicalCornerPos.y());
+            case NE -> new BlockPos(pos.getZ() - physicalCornerPos.y(), pos.getY(), -pos.getX() + physicalCornerPos.x());
+            case SW -> new BlockPos(-pos.getZ() + physicalCornerPos.y(), pos.getY(), pos.getX() - physicalCornerPos.x());
+            case SE -> new BlockPos(-pos.getX() + physicalCornerPos.x(), pos.getY(), -pos.getZ() + physicalCornerPos.y());
+        };
+    }
+
     public static Room.Type getRoomType(MapState map, Vector2ic mapPos) {
         return switch (getColor(map, mapPos)) {
             case 30 -> Room.Type.ENTRANCE;
diff --git a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonSecrets.java b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonSecrets.java
index ac92e834..04e30d0e 100644
--- a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonSecrets.java
+++ b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonSecrets.java
@@ -38,14 +38,36 @@ public class DungeonSecrets {
      * All access to this map must check {@link #isRoomsLoaded()} to prevent concurrent modification.
      */
     @SuppressWarnings("JavadocReference")
-    private static final HashMap<String, HashMap<String, HashMap<String, int[]>>> ROOMS_DATA = new HashMap<>();
+    protected static final HashMap<String, HashMap<String, HashMap<String, int[]>>> ROOMS_DATA = new HashMap<>();
     /**
      * Maps the block identifier string to a custom numeric block id used in dungeon rooms data.
      *
      * @implNote Not using {@link net.minecraft.registry.Registry#getId(Object) Registry#getId(Block)} and {@link net.minecraft.block.Blocks Blocks} since this is also used by {@link me.xmrvizzy.skyblocker.skyblock.dungeon.secrets.DungeonRoomsDFU DungeonRoomsDFU}, which runs outside of Minecraft.
      */
     @SuppressWarnings("JavadocReference")
-    protected static final Map<String, Byte> NUMERIC_ID = Map.ofEntries(Map.entry("minecraft:stone", (byte) 1), Map.entry("minecraft:diorite", (byte) 2), Map.entry("minecraft:polished_diorite", (byte) 3), Map.entry("minecraft:andesite", (byte) 4), Map.entry("minecraft:polished_andesite", (byte) 5), Map.entry("minecraft:grass_block", (byte) 6), Map.entry("minecraft:dirt", (byte) 7), Map.entry("minecraft:coarse_dirt", (byte) 8), Map.entry("minecraft:cobblestone", (byte) 9), Map.entry("minecraft:bedrock", (byte) 10), Map.entry("minecraft:oak_leaves", (byte) 11), Map.entry("minecraft:gray_wool", (byte) 12), Map.entry("minecraft:double_stone_slab", (byte) 13), Map.entry("minecraft:mossy_cobblestone", (byte) 14), Map.entry("minecraft:clay", (byte) 15), Map.entry("minecraft:stone_bricks", (byte) 16), Map.entry("minecraft:mossy_stone_bricks", (byte) 17), Map.entry("minecraft:chiseled_stone_bricks", (byte) 18), Map.entry("minecraft:gray_terracotta", (byte) 19), Map.entry("minecraft:cyan_terracotta", (byte) 20), Map.entry("minecraft:black_terracotta", (byte) 21));
+    protected static final Map<String, Byte> NUMERIC_ID = Map.ofEntries(
+            Map.entry("minecraft:stone", (byte) 1),
+            Map.entry("minecraft:diorite", (byte) 2),
+            Map.entry("minecraft:polished_diorite", (byte) 3),
+            Map.entry("minecraft:andesite", (byte) 4),
+            Map.entry("minecraft:polished_andesite", (byte) 5),
+            Map.entry("minecraft:grass_block", (byte) 6),
+            Map.entry("minecraft:dirt", (byte) 7),
+            Map.entry("minecraft:coarse_dirt", (byte) 8),
+            Map.entry("minecraft:cobblestone", (byte) 9),
+            Map.entry("minecraft:bedrock", (byte) 10),
+            Map.entry("minecraft:oak_leaves", (byte) 11),
+            Map.entry("minecraft:gray_wool", (byte) 12),
+            Map.entry("minecraft:double_stone_slab", (byte) 13),
+            Map.entry("minecraft:mossy_cobblestone", (byte) 14),
+            Map.entry("minecraft:clay", (byte) 15),
+            Map.entry("minecraft:stone_bricks", (byte) 16),
+            Map.entry("minecraft:mossy_stone_bricks", (byte) 17),
+            Map.entry("minecraft:chiseled_stone_bricks", (byte) 18),
+            Map.entry("minecraft:gray_terracotta", (byte) 19),
+            Map.entry("minecraft:cyan_terracotta", (byte) 20),
+            Map.entry("minecraft:black_terracotta", (byte) 21)
+    );
     private static JsonObject roomsJson;
     private static JsonObject waypointsJson;
     @Nullable
diff --git a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/Room.java b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/Room.java
index 4be60c52..ff397098 100644
--- a/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/Room.java
+++ b/src/main/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/Room.java
@@ -1,19 +1,48 @@
 package me.xmrvizzy.skyblocker.skyblock.dungeon.secrets;
 
+import com.google.common.collect.ImmutableSortedSet;
 import net.minecraft.block.MapColor;
+import net.minecraft.client.MinecraftClient;
+import net.minecraft.client.network.ClientPlayerEntity;
+import net.minecraft.client.world.ClientWorld;
+import net.minecraft.registry.Registries;
+import net.minecraft.util.math.BlockPos;
+import org.joml.Vector2i;
 import org.joml.Vector2ic;
 
-import java.util.Arrays;
-import java.util.Set;
+import java.util.*;
+import java.util.concurrent.CompletableFuture;
 
 public class Room {
     private final Type type;
-    private String name;
     private final Set<Vector2ic> segments;
+    private final SortedSet<Integer> segmentsX;
+    private final SortedSet<Integer> segmentsY;
+    private final Shape shape;
+    private final HashMap<String, int[]> roomsData;
+    private final HashMap<Direction, List<String>> possibleRooms = new HashMap<>();
+    private final Set<BlockPos> checkedBlocks = new HashSet<>();
+    private CompletableFuture<Void> findRoom;
+    private String name;
+    private Direction direction;
 
     public Room(Type type, Vector2ic... physicalPositions) {
         this.type = type;
-        this.segments = Set.of(physicalPositions);
+        segments = Set.of(physicalPositions);
+        ImmutableSortedSet.Builder<Integer> segmentsXBuilder = ImmutableSortedSet.naturalOrder();
+        ImmutableSortedSet.Builder<Integer> segmentsYBuilder = ImmutableSortedSet.naturalOrder();
+        for (Vector2ic physicalPos : physicalPositions) {
+            segmentsXBuilder.add(physicalPos.x());
+            segmentsYBuilder.add(physicalPos.y());
+        }
+        segmentsX = segmentsXBuilder.build();
+        segmentsY = segmentsYBuilder.build();
+        shape = getShape();
+        roomsData = DungeonSecrets.ROOMS_DATA.get("catacombs").get(shape.shape);
+        List<String> possibleDirectionRooms = new ArrayList<>(roomsData.keySet());
+        for (Direction direction : getPossibleDirections()) {
+            this.possibleRooms.replace(direction, possibleDirectionRooms);
+        }
     }
 
     public Type getType() {
@@ -29,19 +58,139 @@ public class Room {
         return "Room{type=" + type + ", name='" + name + "'" + ", segments=" + Arrays.toString(segments.toArray()) + "}";
     }
 
+    private Shape getShape() {
+        int segmentsSize = segments.size();
+        if (segmentsSize == 1) {
+            return Shape.ONE_BY_ONE;
+        }
+        if (segmentsSize == 2) {
+            return Shape.ONE_BY_TWO;
+        }
+        if (segmentsSize == 3) {
+            if (segmentsX.size() == 2 && segmentsY.size() == 2) {
+                return Shape.L_SHAPE;
+            }
+            return Shape.ONE_BY_THREE;
+        }
+        if (segmentsSize == 4) {
+            if (segmentsX.size() == 2 && segmentsY.size() == 2) {
+                return Shape.TWO_BY_TWO;
+            }
+            return Shape.ONE_BY_FOUR;
+        }
+        throw new IllegalArgumentException("There are no matching room shapes with this set of physical positions: " + Arrays.toString(segments.toArray()));
+    }
+
+    private Direction[] getPossibleDirections() {
+        return switch (shape) {
+            case ONE_BY_ONE, TWO_BY_TWO -> Direction.values();
+            case ONE_BY_TWO, ONE_BY_THREE, ONE_BY_FOUR -> {
+                if (segmentsX.size() > 1 && segmentsY.size() == 1) {
+                    yield new Direction[]{Direction.NW, Direction.SE};
+                } else if (segmentsX.size() == 1 && segmentsY.size() > 1) {
+                    yield new Direction[]{Direction.NE, Direction.SW};
+                }
+                throw new IllegalStateException("Shape " + shape.shape + " does not match segments: " + Arrays.toString(segments.toArray()));
+            }
+            case L_SHAPE -> {
+                if (!segments.contains(new Vector2i(segmentsX.first(), segmentsY.first()))) {
+                    yield new Direction[]{Direction.SW};
+                } else if (!segments.contains(new Vector2i(segmentsX.first(), segmentsY.last()))) {
+                    yield new Direction[]{Direction.SE};
+                } else if (!segments.contains(new Vector2i(segmentsX.last(), segmentsY.first()))) {
+                    yield new Direction[]{Direction.NW};
+                } else if (!segments.contains(new Vector2i(segmentsX.last(), segmentsY.last()))) {
+                    yield new Direction[]{Direction.NE};
+                }
+                throw new IllegalArgumentException("Shape " + shape.shape + " does not match segments: " + Arrays.toString(segments.toArray()));
+            }
+        };
+    }
+
+    public void update() {
+        // Logical AND has higher precedence than logical OR
+        if (name != null && direction != null || findRoom != null && !findRoom.isDone()) {
+            return;
+        }
+        MinecraftClient client = MinecraftClient.getInstance();
+        ClientPlayerEntity player = client.player;
+        ClientWorld world = client.world;
+        if (player == null || world == null) {
+            return;
+        }
+        findRoom = CompletableFuture.runAsync(() -> {
+            long startTime = System.currentTimeMillis();
+            for (BlockPos pos : BlockPos.iterate(player.getBlockPos().add(-5, -5, -5), player.getBlockPos().add(5, 5, 5))) {
+                if (checkedBlocks.add(pos) && checkBlock(world, pos)) {
+                    break;
+                }
+            }
+            long endTime = System.currentTimeMillis();
+            DungeonSecrets.LOGGER.info("[Skyblocker] Processed room in {} ms", endTime - startTime); // TODO change to debug
+        });
+    }
+
+    private boolean checkBlock(ClientWorld world, BlockPos pos) {
+        for (Map.Entry<Direction, List<String>> directionRooms : possibleRooms.entrySet()) {
+            Direction direction = directionRooms.getKey();
+            BlockPos relative = DungeonMapUtils.actualToRelative(DungeonMapUtils.getPhysicalCornerPos(direction, segmentsX, segmentsY), direction, pos);
+            int block = posIdToInt(relative, DungeonSecrets.NUMERIC_ID.get(Registries.BLOCK.getId(world.getBlockState(pos).getBlock()).toString()));
+            List<String> possibleDirectionRooms = new ArrayList<>();
+            for (String room : directionRooms.getValue()) {
+                if (Arrays.binarySearch(roomsData.get(room), block) >= 0) {
+                    possibleDirectionRooms.add(room);
+                }
+            }
+            possibleRooms.put(direction, possibleDirectionRooms);
+        }
+
+        int matchingRoomsSize = possibleRooms.values().stream().mapToInt(Collection::size).sum();
+        if (matchingRoomsSize == 0) {
+            DungeonSecrets.LOGGER.warn("[Skyblocker] No dungeon room matches after checking {} block(s)", checkedBlocks.size());
+            return true;
+        } else if (matchingRoomsSize == 1) {
+            for (Map.Entry<Direction, List<String>> directionRoomEntry : possibleRooms.entrySet()) {
+                if (directionRoomEntry.getValue().size() == 1) {
+                    name = directionRoomEntry.getValue().get(0);
+                    direction = directionRoomEntry.getKey();
+                }
+            }
+            DungeonSecrets.LOGGER.info("[Skyblocker] Room {} matched after checking {} block(s)", name, checkedBlocks.size()); // TODO change to debug
+            return true;
+        } else {
+            DungeonSecrets.LOGGER.info("[Skyblocker] {} rooms remaining after checking {} block(s)", matchingRoomsSize, checkedBlocks.size()); // TODO change to debug
+            return false;
+        }
+    }
+
+    private int posIdToInt(BlockPos pos, byte id) {
+        return pos.getX() << 24 | pos.getY() << 16 | pos.getZ() << 8 | id;
+    }
+
     public enum Type {
-        ENTRANCE(MapColor.DARK_GREEN.getRenderColorByte(MapColor.Brightness.HIGH)),
-        ROOM(MapColor.ORANGE.getRenderColorByte(MapColor.Brightness.LOWEST)),
-        PUZZLE(MapColor.MAGENTA.getRenderColorByte(MapColor.Brightness.HIGH)),
-        TRAP(MapColor.ORANGE.getRenderColorByte(MapColor.Brightness.HIGH)),
-        MINIBOSS(MapColor.YELLOW.getRenderColorByte(MapColor.Brightness.HIGH)),
-        FAIRY(MapColor.PINK.getRenderColorByte(MapColor.Brightness.HIGH)),
-        BLOOD(MapColor.BRIGHT_RED.getRenderColorByte(MapColor.Brightness.HIGH)),
-        UNKNOWN(MapColor.GRAY.getRenderColorByte(MapColor.Brightness.NORMAL));
+        ENTRANCE(MapColor.DARK_GREEN.getRenderColorByte(MapColor.Brightness.HIGH)), ROOM(MapColor.ORANGE.getRenderColorByte(MapColor.Brightness.LOWEST)), PUZZLE(MapColor.MAGENTA.getRenderColorByte(MapColor.Brightness.HIGH)), TRAP(MapColor.ORANGE.getRenderColorByte(MapColor.Brightness.HIGH)), MINIBOSS(MapColor.YELLOW.getRenderColorByte(MapColor.Brightness.HIGH)), FAIRY(MapColor.PINK.getRenderColorByte(MapColor.Brightness.HIGH)), BLOOD(MapColor.BRIGHT_RED.getRenderColorByte(MapColor.Brightness.HIGH)), UNKNOWN(MapColor.GRAY.getRenderColorByte(MapColor.Brightness.NORMAL));
         final byte color;
 
         Type(byte color) {
             this.color = color;
         }
     }
+
+    public enum Shape {
+        ONE_BY_ONE("1x1"), ONE_BY_TWO("1x2"), ONE_BY_THREE("1x3"), ONE_BY_FOUR("1x4"), L_SHAPE("L-shape"), TWO_BY_TWO("2x2");
+        final String shape;
+
+        Shape(String shape) {
+            this.shape = shape;
+        }
+
+        @Override
+        public String toString() {
+            return shape;
+        }
+    }
+
+    public enum Direction {
+        NW, NE, SW, SE
+    }
 }
diff --git a/src/test/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonRoomsDFU.java b/src/test/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonRoomsDFU.java
index 7e85d721..613f642c 100644
--- a/src/test/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonRoomsDFU.java
+++ b/src/test/java/me/xmrvizzy/skyblocker/skyblock/dungeon/secrets/DungeonRoomsDFU.java
@@ -104,6 +104,8 @@ public class DungeonRoomsDFU {
         for (int i = 0; i < oldRoom.length; i++) {
             room[i] = updateBlock(oldRoom[i]);
         }
+        // Technically not needed, as the long array should be sorted already.
+        Arrays.sort(room);
         return room;
     }
 
@@ -114,9 +116,9 @@ public class DungeonRoomsDFU {
      * @return the new block state in the new format
      */
     private static int updateBlock(long oldBlock) {
-        short x = (short) ((oldBlock >> 48) & 0xFFFF);
-        short y = (short) ((oldBlock >> 32) & 0xFFFF);
-        short z = (short) ((oldBlock >> 16) & 0xFFFF);
+        short x = (short) (oldBlock >> 48 & 0xFFFF);
+        short y = (short) (oldBlock >> 32 & 0xFFFF);
+        short z = (short) (oldBlock >> 16 & 0xFFFF);
         // Blocks should be within the range 0 to 256, since a dungeon room is at most around 128 blocks long and around 150 blocks tall.
         if (x < 0 || x > 0xFF || y < 0 || y > 0xFF || z < 0 || z > 0xFF) {
             throw new IllegalArgumentException("Invalid block: " + oldBlock);
@@ -127,7 +129,7 @@ public class DungeonRoomsDFU {
         if (newId == null) {
             newId = ItemIdFix.fromId(oldId / 100);
         }
-        return (x << 24) | (y << 16) | (z << 8) | DungeonSecrets.NUMERIC_ID.get(newId);
+        return x << 24 | y << 16 | z << 8 | DungeonSecrets.NUMERIC_ID.get(newId);
     }
 
     private static CompletableFuture<Void> save() {