From 39cf82e4976f70bf8b8d27216a0284e30d9ae5e4 Mon Sep 17 00:00:00 2001 From: Aaron <51387595+AzureAaron@users.noreply.github.com> Date: Sat, 17 Feb 2024 21:32:15 -0500 Subject: Rename search overlay package to match Java conventions --- .../skyblock/searchOverlay/SplitStringTest.java | 31 ---------------------- .../skyblock/searchoverlay/SplitStringTest.java | 31 ++++++++++++++++++++++ 2 files changed, 31 insertions(+), 31 deletions(-) delete mode 100644 src/test/java/de/hysky/skyblocker/skyblock/searchOverlay/SplitStringTest.java create mode 100644 src/test/java/de/hysky/skyblocker/skyblock/searchoverlay/SplitStringTest.java (limited to 'src/test/java') diff --git a/src/test/java/de/hysky/skyblocker/skyblock/searchOverlay/SplitStringTest.java b/src/test/java/de/hysky/skyblocker/skyblock/searchOverlay/SplitStringTest.java deleted file mode 100644 index c397b5a4..00000000 --- a/src/test/java/de/hysky/skyblocker/skyblock/searchOverlay/SplitStringTest.java +++ /dev/null @@ -1,31 +0,0 @@ -package de.hysky.skyblocker.skyblock.searchOverlay; - -import it.unimi.dsi.fastutil.Pair; -import org.junit.jupiter.api.Assertions; -import org.junit.jupiter.api.Test; - -public class SplitStringTest { - @Test - void testSplitString1() { - String input = "aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa a"; - Pair split = SearchOverManager.splitString(input); - Assertions.assertEquals("aaaaaaaaaaaaaaa", split.left()); - Assertions.assertEquals("aaaaaaaaaaaaaaa", split.right()); - } - - @Test - void testSplitString2() { - String input = "a a a a aaa aa aa aaaa aaa aa aa aa a a aa aaa a aaa aa"; - Pair split = SearchOverManager.splitString(input); - Assertions.assertEquals("a a a a aaa aa", split.left()); - Assertions.assertEquals("aa aaaa aaa aa", split.right()); - } - - @Test - void testSplitString3() { - String input = "aaaaa aaaaa aaaaa"; - Pair split = SearchOverManager.splitString(input); - Assertions.assertEquals("aaaaa aaaaa", split.left()); - Assertions.assertEquals("aaaaa", split.right()); - } -} diff --git a/src/test/java/de/hysky/skyblocker/skyblock/searchoverlay/SplitStringTest.java b/src/test/java/de/hysky/skyblocker/skyblock/searchoverlay/SplitStringTest.java new file mode 100644 index 00000000..a9fd541f --- /dev/null +++ b/src/test/java/de/hysky/skyblocker/skyblock/searchoverlay/SplitStringTest.java @@ -0,0 +1,31 @@ +package de.hysky.skyblocker.skyblock.searchoverlay; + +import it.unimi.dsi.fastutil.Pair; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +public class SplitStringTest { + @Test + void testSplitString1() { + String input = "aaaaaaaaaaaaaaa aaaaaaaaaaaaaaaaa a"; + Pair split = SearchOverManager.splitString(input); + Assertions.assertEquals("aaaaaaaaaaaaaaa", split.left()); + Assertions.assertEquals("aaaaaaaaaaaaaaa", split.right()); + } + + @Test + void testSplitString2() { + String input = "a a a a aaa aa aa aaaa aaa aa aa aa a a aa aaa a aaa aa"; + Pair split = SearchOverManager.splitString(input); + Assertions.assertEquals("a a a a aaa aa", split.left()); + Assertions.assertEquals("aa aaaa aaa aa", split.right()); + } + + @Test + void testSplitString3() { + String input = "aaaaa aaaaa aaaaa"; + Pair split = SearchOverManager.splitString(input); + Assertions.assertEquals("aaaaa aaaaa", split.left()); + Assertions.assertEquals("aaaaa", split.right()); + } +} -- cgit From ca61d618df013434bce4fb6995bc40aec4dc07dc Mon Sep 17 00:00:00 2001 From: Kevinthegreat <92656833+kevinthegreat1@users.noreply.github.com> Date: Fri, 2 Feb 2024 16:40:24 -0500 Subject: Finish silverfish and ice fill solvers --- .../skyblock/dungeon/puzzle/IceFill.java | 171 ++++++++++++++++++++- .../skyblock/dungeon/puzzle/Silverfish.java | 82 ++++------ .../dungeon/puzzle/waterboard/Waterboard.java | 14 +- .../skyblock/dungeon/puzzle/SilverfishTest.java | 40 +++++ 4 files changed, 244 insertions(+), 63 deletions(-) create mode 100644 src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/SilverfishTest.java (limited to 'src/test/java') diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java index 3eee8a7c..7ab96d78 100644 --- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java +++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java @@ -1,32 +1,187 @@ package de.hysky.skyblocker.skyblock.dungeon.puzzle; +import com.google.common.primitives.Booleans; +import com.mojang.brigadier.Command; +import de.hysky.skyblocker.SkyblockerMod; import de.hysky.skyblocker.config.SkyblockerConfigManager; +import de.hysky.skyblocker.debug.Debug; +import de.hysky.skyblocker.skyblock.dungeon.secrets.DungeonManager; +import de.hysky.skyblocker.skyblock.dungeon.secrets.Room; +import de.hysky.skyblocker.utils.Constants; +import de.hysky.skyblocker.utils.render.RenderHelper; +import net.fabricmc.fabric.api.client.command.v2.ClientCommandRegistrationCallback; import net.fabricmc.fabric.api.client.rendering.v1.WorldRenderContext; import net.minecraft.client.MinecraftClient; +import net.minecraft.util.DyeColor; +import net.minecraft.util.math.BlockPos; +import net.minecraft.util.math.Direction; +import net.minecraft.util.math.Vec3d; +import net.minecraft.world.World; +import org.joml.Vector2i; +import org.joml.Vector2ic; + +import java.util.*; +import java.util.concurrent.CompletableFuture; + +import static net.fabricmc.fabric.api.client.command.v2.ClientCommandManager.literal; -// 1: 15, 69, 7 -// 2: 15, 70, 12 -// 3: 15, 71, 19 -// ice -> packed_ice -// polished andesite public class IceFill extends DungeonPuzzle { public static final IceFill INSTANCE = new IceFill(); + private static final float[] RED_COLOR_COMPONENTS = DyeColor.RED.getColorComponents(); + private static final BlockPos BOARD_1_ORIGIN = new BlockPos(16, 70, 9); + private static final BlockPos BOARD_2_ORIGIN = new BlockPos(17, 71, 16); + private static final BlockPos BOARD_3_ORIGIN = new BlockPos(18, 72, 25); + private CompletableFuture solve; + private final boolean[][] iceFillBoard1 = new boolean[3][3]; + private final boolean[][] iceFillBoard2 = new boolean[5][5]; + private final boolean[][] iceFillBoard3 = new boolean[7][7]; + private final List iceFillPath1 = new ArrayList<>(); + private final List iceFillPath2 = new ArrayList<>(); + private final List iceFillPath3 = new ArrayList<>(); - public IceFill() { + private IceFill() { super("ice-fill", "ice-path"); } - public static void init() {} + public static void init() { + if (Debug.debugEnabled()) { + ClientCommandRegistrationCallback.EVENT.register((dispatcher, registryAccess) -> dispatcher.register(literal(SkyblockerMod.NAMESPACE).then(literal("dungeons").then(literal("puzzle").then(literal(INSTANCE.puzzleName) + .then(literal("printBoard1").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(INSTANCE.iceFillBoard1))); + return Command.SINGLE_SUCCESS; + })).then(literal("printBoard2").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(INSTANCE.iceFillBoard2))); + return Command.SINGLE_SUCCESS; + })).then(literal("printBoard3").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(INSTANCE.iceFillBoard3))); + return Command.SINGLE_SUCCESS; + })).then(literal("printPath1").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(INSTANCE.iceFillPath1.toString())); + return Command.SINGLE_SUCCESS; + })).then(literal("printPath2").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(INSTANCE.iceFillPath2.toString())); + return Command.SINGLE_SUCCESS; + })).then(literal("printPath3").executes(context -> { + context.getSource().sendFeedback(Constants.PREFIX.get().append(INSTANCE.iceFillPath3.toString())); + return Command.SINGLE_SUCCESS; + })) + ))))); + } + } + + private static String boardToString(boolean[][] iceFillBoard) { + StringBuilder sb = new StringBuilder(); + for (boolean[] row : iceFillBoard) { + sb.append("\n"); + for (boolean cell : row) { + sb.append(cell ? '#' : '.'); + } + } + return sb.toString(); + } @Override public void tick(MinecraftClient client) { - if (!SkyblockerConfigManager.get().locations.dungeons.solveIceFill) { + if (!SkyblockerConfigManager.get().locations.dungeons.solveIceFill || client.world == null || !DungeonManager.isCurrentRoomMatched() || solve != null && !solve.isDone()) { return; } + Room room = DungeonManager.getCurrentRoom(); + + solve = CompletableFuture.runAsync(() -> { + BlockPos.Mutable pos = new BlockPos.Mutable(); + boolean board1Changed = updateBoard(client.world, room, iceFillBoard1, pos.set(BOARD_1_ORIGIN)); + boolean board2Changed = updateBoard(client.world, room, iceFillBoard2, pos.set(BOARD_2_ORIGIN)); + boolean board3Changed = updateBoard(client.world, room, iceFillBoard3, pos.set(BOARD_3_ORIGIN)); + + if (board1Changed) { + solve(iceFillBoard1, iceFillPath1); + } + if (board2Changed) { + solve(iceFillBoard2, iceFillPath2); + } + if (board3Changed) { + solve(iceFillBoard3, iceFillPath3); + } + }); + } + + private boolean updateBoard(World world, Room room, boolean[][] iceFillBoard, BlockPos.Mutable pos) { + boolean boardChanged = false; + for (int row = 0; row < iceFillBoard.length; pos.move(iceFillBoard[row].length, 0, -1), row++) { + for (int col = 0; col < iceFillBoard[row].length; pos.move(Direction.WEST), col++) { + BlockPos actualPos = room.relativeToActual(pos); + boolean isBlock = !world.getBlockState(actualPos).isAir(); + if (iceFillBoard[row][col] != isBlock) { + iceFillBoard[row][col] = isBlock; + boardChanged = true; + } + } + } + return boardChanged; + } + + private void solve(boolean[][] iceFillBoard, List iceFillPath) { + Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2); + int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum(); + + Queue> queue = new ArrayDeque<>(); + queue.add(List.of(start)); + while (!queue.isEmpty()) { + List path = queue.poll(); + Vector2ic pos = path.get(path.size() - 1); + if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && path.size() == count) { + iceFillPath.clear(); + iceFillPath.addAll(path); + return; + } + + Vector2i posMutable = pos.add(1, 0, new Vector2i()); + if (posMutable.x() < iceFillBoard.length && !iceFillBoard[posMutable.x()][posMutable.y()]) { + addQueue(queue, path, posMutable); + } + + posMutable = pos.add(-1, 0, new Vector2i()); + if (posMutable.x() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) { + addQueue(queue, path, posMutable); + } + + posMutable = pos.add(0, 1, new Vector2i()); + if (posMutable.y() < iceFillBoard[0].length && !iceFillBoard[posMutable.x()][posMutable.y()]) { + addQueue(queue, path, posMutable); + } + + posMutable = pos.add(0, -1, new Vector2i()); + if (posMutable.y() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) { + addQueue(queue, path, posMutable); + } + } + } + + private void addQueue(Queue> queue, List path, Vector2ic newPos) { + if (!path.contains(newPos)) { + List newPath = new ArrayList<>(path); + newPath.add(newPos); + queue.add(newPath); + } } @Override public void render(WorldRenderContext context) { + if (!SkyblockerConfigManager.get().locations.dungeons.solveIceFill || !DungeonManager.isCurrentRoomMatched()) { + return; + } + Room room = DungeonManager.getCurrentRoom(); + renderPath(context, room, iceFillPath1, BOARD_1_ORIGIN); + renderPath(context, room, iceFillPath2, BOARD_2_ORIGIN); + renderPath(context, room, iceFillPath3, BOARD_3_ORIGIN); + } + private void renderPath(WorldRenderContext context, Room room, List iceFillPath, BlockPos originPos) { + BlockPos.Mutable pos = new BlockPos.Mutable(); + for (int i = 0; i < iceFillPath.size() - 1; i++) { + Vec3d start = Vec3d.ofCenter(room.relativeToActual(pos.set(originPos).move(-iceFillPath.get(i).y(), 0, -iceFillPath.get(i).x()))); + Vec3d end = Vec3d.ofCenter(room.relativeToActual(pos.set(originPos).move(-iceFillPath.get(i + 1).y(), 0, -iceFillPath.get(i + 1).x()))); + RenderHelper.renderLinesFromPoints(context, new Vec3d[]{start, end}, RED_COLOR_COMPONENTS, 1f, 5f, true); + } } } diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/Silverfish.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/Silverfish.java index 195e38f7..b5cbc8ee 100644 --- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/Silverfish.java +++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/Silverfish.java @@ -26,35 +26,32 @@ import java.util.*; import static net.fabricmc.fabric.api.client.command.v2.ClientCommandManager.literal; -//right: 7, 66, 8 -//left: 23, 66, 8 -//right back: 7, 66, 24 -//polished andesite public class Silverfish extends DungeonPuzzle { private static final Logger LOGGER = LoggerFactory.getLogger(Silverfish.class); public static final Silverfish INSTANCE = new Silverfish(); - private static final float[] LIME_COLOR_COMPONENTS = DyeColor.LIME.getColorComponents(); - private final boolean[][] silverfishBoard = new boolean[17][17]; - private Vector2ic silverfishPos; - private final List silverfishPath = new ArrayList<>(); + private static final float[] RED_COLOR_COMPONENTS = DyeColor.RED.getColorComponents(); + final boolean[][] silverfishBoard = new boolean[17][17]; + Vector2ic silverfishPos; + final List silverfishPath = new ArrayList<>(); private Silverfish() { super("silverfish", "ice-silverfish-room"); + } + + public static void init() { if (Debug.debugEnabled()) { - ClientCommandRegistrationCallback.EVENT.register((dispatcher, registryAccess) -> dispatcher.register(literal(SkyblockerMod.NAMESPACE).then(literal("dungeons").then(literal("puzzle").then(literal(puzzleName) + ClientCommandRegistrationCallback.EVENT.register((dispatcher, registryAccess) -> dispatcher.register(literal(SkyblockerMod.NAMESPACE).then(literal("dungeons").then(literal("puzzle").then(literal(INSTANCE.puzzleName) .then(literal("printBoard").executes(context -> { - context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(silverfishBoard))); + context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(INSTANCE.silverfishBoard))); return Command.SINGLE_SUCCESS; })).then(literal("printPath").executes(context -> { - context.getSource().sendFeedback(Constants.PREFIX.get().append(silverfishPath.toString())); + context.getSource().sendFeedback(Constants.PREFIX.get().append(INSTANCE.silverfishPath.toString())); return Command.SINGLE_SUCCESS; })) ))))); } } - public static void init() {} - private static String boardToString(boolean[][] silverfishBoard) { StringBuilder sb = new StringBuilder(); for (boolean[] row : silverfishBoard) { @@ -85,13 +82,12 @@ public class Silverfish extends DungeonPuzzle { } } - BlockPos blockPos = room.relativeToActual(new BlockPos(16, 16, 16)); - List entities = client.world.getEntitiesByClass(SilverfishEntity.class, Box.of(Vec3d.ofCenter(blockPos), 32, 32, 32), silverfishEntity -> true); + List entities = client.world.getEntitiesByClass(SilverfishEntity.class, Box.of(Vec3d.ofCenter(room.relativeToActual(new BlockPos(15, 66, 16))), 16, 16, 16), silverfishEntity -> true); if (entities.isEmpty()) { return; } BlockPos newSilverfishBlockPos = room.actualToRelative(entities.get(0).getBlockPos()); - Vector2ic newSilverfishPos = new Vector2i(23 - newSilverfishBlockPos.getX(), 24 - newSilverfishBlockPos.getZ()); + Vector2ic newSilverfishPos = new Vector2i(24 - newSilverfishBlockPos.getZ(), 23 - newSilverfishBlockPos.getX()); if (newSilverfishPos.x() < 0 || newSilverfishPos.x() >= 17 || newSilverfishPos.y() < 0 || newSilverfishPos.y() >= 17) { return; } @@ -104,17 +100,18 @@ public class Silverfish extends DungeonPuzzle { } } - private void solve() { + void solve() { if (silverfishPos == null) { return; } Set visited = new HashSet<>(); Queue> queue = new ArrayDeque<>(); queue.add(List.of(silverfishPos)); + visited.add(silverfishPos); while (!queue.isEmpty()) { List path = queue.poll(); Vector2ic pos = path.get(path.size() - 1); - if (pos.equals(8, 0)) { + if (pos.x() == 0 && pos.y() >= 7 && pos.y() <= 9) { silverfishPath.clear(); silverfishPath.addAll(path); return; @@ -125,48 +122,37 @@ public class Silverfish extends DungeonPuzzle { posMutable.add(1, 0); } posMutable.add(-1, 0); - if (!visited.contains(posMutable)) { - ArrayList newPath = new ArrayList<>(path); - newPath.add(new Vector2i(posMutable)); - queue.add(newPath); - visited.add(posMutable); - } + addQueue(visited, queue, path, posMutable); - posMutable.set(pos); + posMutable = new Vector2i(pos); while (posMutable.x() >= 0 && !silverfishBoard[posMutable.x()][posMutable.y()]) { posMutable.add(-1, 0); } posMutable.add(1, 0); - if (!visited.contains(posMutable)) { - ArrayList newPath = new ArrayList<>(path); - newPath.add(new Vector2i(posMutable)); - queue.add(newPath); - visited.add(posMutable); - } + addQueue(visited, queue, path, posMutable); - posMutable.set(pos); + posMutable = new Vector2i(pos); while (posMutable.y() < 17 && !silverfishBoard[posMutable.x()][posMutable.y()]) { posMutable.add(0, 1); } posMutable.add(0, -1); - if (!visited.contains(posMutable)) { - ArrayList newPath = new ArrayList<>(path); - newPath.add(new Vector2i(posMutable)); - queue.add(newPath); - visited.add(posMutable); - } + addQueue(visited, queue, path, posMutable); - posMutable.set(pos); + posMutable = new Vector2i(pos); while (posMutable.y() >= 0 && !silverfishBoard[posMutable.x()][posMutable.y()]) { posMutable.add(0, -1); } posMutable.add(0, 1); - if (!visited.contains(posMutable)) { - ArrayList newPath = new ArrayList<>(path); - newPath.add(new Vector2i(posMutable)); - queue.add(newPath); - visited.add(posMutable); - } + addQueue(visited, queue, path, posMutable); + } + } + + private void addQueue(Set visited, Queue> queue, List path, Vector2ic newPos) { + if (!visited.contains(newPos)) { + List newPath = new ArrayList<>(path); + newPath.add(newPos); + queue.add(newPath); + visited.add(newPos); } } @@ -178,9 +164,9 @@ public class Silverfish extends DungeonPuzzle { Room room = DungeonManager.getCurrentRoom(); BlockPos.Mutable pos = new BlockPos.Mutable(); for (int i = 0; i < silverfishPath.size() - 1; i++) { - Vec3d start = Vec3d.ofCenter(room.relativeToActual(pos.set(23 - silverfishPath.get(i).x(), 67, 24 - silverfishPath.get(i).y()))); - Vec3d end = Vec3d.ofCenter(room.relativeToActual(pos.set(23 - silverfishPath.get(i + 1).x(), 67, 24 - silverfishPath.get(i + 1).y()))); - RenderHelper.renderLinesFromPoints(context, new Vec3d[]{start, end}, LIME_COLOR_COMPONENTS, 1f, 5f, true); + Vec3d start = Vec3d.ofCenter(room.relativeToActual(pos.set(23 - silverfishPath.get(i).y(), 67, 24 - silverfishPath.get(i).x()))); + Vec3d end = Vec3d.ofCenter(room.relativeToActual(pos.set(23 - silverfishPath.get(i + 1).y(), 67, 24 - silverfishPath.get(i + 1).x()))); + RenderHelper.renderLinesFromPoints(context, new Vec3d[]{start, end}, RED_COLOR_COMPONENTS, 1f, 5f, true); } } diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/waterboard/Waterboard.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/waterboard/Waterboard.java index 3244996a..ba4b9a5f 100644 --- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/waterboard/Waterboard.java +++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/waterboard/Waterboard.java @@ -88,17 +88,20 @@ public class Waterboard extends DungeonPuzzle { private Waterboard() { super("waterboard", "water-puzzle"); - UseBlockCallback.EVENT.register(this::onUseBlock); + } + + public static void init() { + UseBlockCallback.EVENT.register(INSTANCE::onUseBlock); if (Debug.debugEnabled()) { - ClientCommandRegistrationCallback.EVENT.register((dispatcher, registryAccess) -> dispatcher.register(literal(SkyblockerMod.NAMESPACE).then(literal("dungeons").then(literal("puzzle").then(literal(puzzleName) + ClientCommandRegistrationCallback.EVENT.register((dispatcher, registryAccess) -> dispatcher.register(literal(SkyblockerMod.NAMESPACE).then(literal("dungeons").then(literal("puzzle").then(literal(INSTANCE.puzzleName) .then(literal("printBoard").executes(context -> { - context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(cells))); + context.getSource().sendFeedback(Constants.PREFIX.get().append(boardToString(INSTANCE.cells))); return Command.SINGLE_SUCCESS; })).then(literal("printDoors").executes(context -> { context.getSource().sendFeedback(Constants.PREFIX.get().append(Integer.toBinaryString(INSTANCE.doors))); return Command.SINGLE_SUCCESS; })).then(literal("printSimulationResults").then(argument("combination", IntegerArgumentType.integer(0, 63)).executes(context -> { - context.getSource().sendFeedback(Constants.PREFIX.get().append(results[IntegerArgumentType.getInteger(context, "combination")].toString())); + context.getSource().sendFeedback(Constants.PREFIX.get().append(INSTANCE.results[IntegerArgumentType.getInteger(context, "combination")].toString())); return Command.SINGLE_SUCCESS; }))).then(literal("printCurrentCombination").executes(context -> { context.getSource().sendFeedback(Constants.PREFIX.get().append(Integer.toBinaryString(INSTANCE.currentCombination))); @@ -111,9 +114,6 @@ public class Waterboard extends DungeonPuzzle { } } - public static void init() { - } - private static String boardToString(Cell[][] cells) { StringBuilder sb = new StringBuilder(); for (Cell[] row : cells) { diff --git a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/SilverfishTest.java b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/SilverfishTest.java new file mode 100644 index 00000000..cc6178e1 --- /dev/null +++ b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/SilverfishTest.java @@ -0,0 +1,40 @@ +package de.hysky.skyblocker.skyblock.dungeon.puzzle; + +import org.joml.Vector2i; +import org.junit.jupiter.api.Assertions; +import org.junit.jupiter.api.Test; + +import java.util.List; + +public class SilverfishTest { + private static final boolean[][] silverfishBoard = new boolean[][]{ + {false, false, false, false, false, true, false, false, false, false, false, false, false, false, false, false, false}, + {false, true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, true, false, false, false, false, false, false, false, true, false, false, false, false}, + {true, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, true, false}, + {false, true, false, false, false, false, false, false, false, false, true, false, false, false, false, true, false}, + {false, false, true, false, false, false, false, false, false, false, false, true, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false, false}, + {false, false, false, false, false, false, true, false, false, false, true, false, false, false, false, false, false}, + {false, false, true, false, false, false, false, false, false, false, false, false, false, true, false, false, false} + }; + + @Test + void testSilverfishSolve() { + for (int i = 0; i < silverfishBoard.length; i++) { + System.arraycopy(silverfishBoard[i], 0, Silverfish.INSTANCE.silverfishBoard[i], 0, silverfishBoard[i].length); + } + Silverfish.INSTANCE.silverfishPos = new Vector2i(15, 15); + Silverfish.INSTANCE.solve(); + List expectedSilverfishPath = List.of(new Vector2i(15, 15), new Vector2i(15, 11), new Vector2i(16, 11), new Vector2i(16, 3), new Vector2i(0, 3), new Vector2i(0, 4), new Vector2i(1, 4), new Vector2i(1, 2), new Vector2i(10, 2), new Vector2i(10, 9), new Vector2i(0, 9)); + Assertions.assertEquals(expectedSilverfishPath, Silverfish.INSTANCE.silverfishPath); + } +} -- cgit From 2fa902328a4a4a76f5ae300db7810530183b47d2 Mon Sep 17 00:00:00 2001 From: Kevinthegreat <92656833+kevinthegreat1@users.noreply.github.com> Date: Sat, 3 Feb 2024 13:43:41 -0500 Subject: Change IceFill from bfs to dfs --- .../skyblock/dungeon/puzzle/IceFill.java | 137 ++++++++++++++++----- .../skyblock/dungeon/puzzle/IceFillTest.java | 27 ++++ 2 files changed, 136 insertions(+), 28 deletions(-) create mode 100644 src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java (limited to 'src/test/java') diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java index 7ab96d78..166047b2 100644 --- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java +++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java @@ -120,50 +120,131 @@ public class IceFill extends DungeonPuzzle { return boardChanged; } - private void solve(boolean[][] iceFillBoard, List iceFillPath) { + void solve(boolean[][] iceFillBoard, List iceFillPath) { Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2); int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum(); - Queue> queue = new ArrayDeque<>(); - queue.add(List.of(start)); - while (!queue.isEmpty()) { - List path = queue.poll(); - Vector2ic pos = path.get(path.size() - 1); - if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && path.size() == count) { - iceFillPath.clear(); - iceFillPath.addAll(path); - return; - } + List newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start))); + if (newPath != null) { + iceFillPath.clear(); + iceFillPath.addAll(newPath); + } + } - Vector2i posMutable = pos.add(1, 0, new Vector2i()); - if (posMutable.x() < iceFillBoard.length && !iceFillBoard[posMutable.x()][posMutable.y()]) { - addQueue(queue, path, posMutable); + private List solveDfs(boolean[][] iceFillBoard, int count, List path) { + Vector2ic pos = path.get(path.size() - 1); + if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) { + return path; + } + + Vector2ic newPos = pos.add(1, 0, new Vector2i()); + if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + path.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path); + if (newPath != null) { + return newPath; + } else { + path.remove(path.size() - 1); } + } - posMutable = pos.add(-1, 0, new Vector2i()); - if (posMutable.x() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) { - addQueue(queue, path, posMutable); + newPos = pos.add(-1, 0, new Vector2i()); + if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + path.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path); + if (newPath != null) { + return newPath; + } else { + path.remove(path.size() - 1); } + } - posMutable = pos.add(0, 1, new Vector2i()); - if (posMutable.y() < iceFillBoard[0].length && !iceFillBoard[posMutable.x()][posMutable.y()]) { - addQueue(queue, path, posMutable); + newPos = pos.add(0, 1, new Vector2i()); + if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + path.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path); + if (newPath != null) { + return newPath; + } else { + path.remove(path.size() - 1); } + } - posMutable = pos.add(0, -1, new Vector2i()); - if (posMutable.y() >= 0 && !iceFillBoard[posMutable.x()][posMutable.y()]) { - addQueue(queue, path, posMutable); + newPos = pos.add(0, -1, new Vector2i()); + if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + path.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path); + if (newPath != null) { + return newPath; + } else { + path.remove(path.size() - 1); } } + + return null; + } + + /* + void solve(boolean[][] iceFillBoard, List iceFillPath) { + Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2); + int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum(); + + Vector2ic[] newPath = solveDfs(iceFillBoard, count - 1, new Vector2ic[]{start}); + if (newPath != null) { + iceFillPath.clear(); + iceFillPath.addAll(Arrays.asList(newPath)); + } } - private void addQueue(Queue> queue, List path, Vector2ic newPos) { - if (!path.contains(newPos)) { - List newPath = new ArrayList<>(path); - newPath.add(newPos); - queue.add(newPath); + private Vector2ic[] solveDfs(boolean[][] iceFillBoard, int count, Vector2ic[] path) { + Vector2ic pos = path[path.length - 1]; + if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) { + return path; + } + + Vector2ic newPos = pos.add(1, 0, new Vector2i()); + if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { + Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); + newPath[path.length] = newPos; + newPath = solveDfs(iceFillBoard, count - 1, newPath); + if (newPath != null) { + return newPath; + } + } + + newPos = pos.add(-1, 0, new Vector2i()); + if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { + Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); + newPath[path.length] = newPos; + newPath = solveDfs(iceFillBoard, count - 1, newPath); + if (newPath != null) { + return newPath; + } + } + + newPos = pos.add(0, 1, new Vector2i()); + if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { + Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); + newPath[path.length] = newPos; + newPath = solveDfs(iceFillBoard, count - 1, newPath); + if (newPath != null) { + return newPath; + } } + + newPos = pos.add(0, -1, new Vector2i()); + if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { + Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); + newPath[path.length] = newPos; + newPath = solveDfs(iceFillBoard, count - 1, newPath); + if (newPath != null) { + return newPath; + } + } + + return null; } + */ @Override public void render(WorldRenderContext context) { diff --git a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java new file mode 100644 index 00000000..511d1148 --- /dev/null +++ b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java @@ -0,0 +1,27 @@ +package de.hysky.skyblocker.skyblock.dungeon.puzzle; + +import org.joml.Vector2ic; +import org.junit.jupiter.api.Test; + +import java.util.ArrayList; +import java.util.List; + +public class IceFillTest { + private static final boolean[][] iceFillBoard = new boolean[][]{ + {false, false, true, false, false, false, false}, + {false, false, false, false, false, false, false}, + {false, false, false, true, true, false, false}, + {false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false}, + {false, false, false, false, false, false, false}, + {true, false, false, false, false, false, false}, + }; + private static final List iceFillPath = new ArrayList<>(); + + @Test + void testIceFillSolve() { + IceFill.INSTANCE.solve(iceFillBoard, iceFillPath); + System.out.println(iceFillPath); + System.out.println(iceFillPath.size()); + } +} -- cgit From b463261d5d1e70d6f0f350bc2a2507e4483d31c3 Mon Sep 17 00:00:00 2001 From: Kevinthegreat <92656833+kevinthegreat1@users.noreply.github.com> Date: Sat, 3 Feb 2024 16:15:47 -0500 Subject: Optimize ice fill --- .../skyblock/dungeon/puzzle/IceFill.java | 110 ++++++--------------- .../skyblock/dungeon/puzzle/IceFillTest.java | 6 +- 2 files changed, 32 insertions(+), 84 deletions(-) (limited to 'src/test/java') diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java index 166047b2..9b6e7b1f 100644 --- a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java +++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFill.java @@ -124,127 +124,73 @@ public class IceFill extends DungeonPuzzle { Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2); int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum(); - List newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start))); + List newPath = solveDfs(iceFillBoard, count - 1, new ArrayList<>(List.of(start)), new HashSet<>(List.of(start))); if (newPath != null) { iceFillPath.clear(); iceFillPath.addAll(newPath); } } - private List solveDfs(boolean[][] iceFillBoard, int count, List path) { + private List solveDfs(boolean[][] iceFillBoard, int count, List path, Set visited) { Vector2ic pos = path.get(path.size() - 1); - if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) { - return path; + if (count == 0) { + if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2) { + return path; + } else { + return null; + } } Vector2ic newPos = pos.add(1, 0, new Vector2i()); - if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) { path.add(newPos); - List newPath = solveDfs(iceFillBoard, count - 1, path); + visited.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path, visited); if (newPath != null) { return newPath; - } else { - path.remove(path.size() - 1); } + path.remove(path.size() - 1); + visited.remove(newPos); } newPos = pos.add(-1, 0, new Vector2i()); - if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) { path.add(newPos); - List newPath = solveDfs(iceFillBoard, count - 1, path); + visited.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path, visited); if (newPath != null) { return newPath; - } else { - path.remove(path.size() - 1); } + path.remove(path.size() - 1); + visited.remove(newPos); } newPos = pos.add(0, 1, new Vector2i()); - if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) { path.add(newPos); - List newPath = solveDfs(iceFillBoard, count - 1, path); + visited.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path, visited); if (newPath != null) { return newPath; - } else { - path.remove(path.size() - 1); } + path.remove(path.size() - 1); + visited.remove(newPos); } newPos = pos.add(0, -1, new Vector2i()); - if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !path.contains(newPos)) { + if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !visited.contains(newPos)) { path.add(newPos); - List newPath = solveDfs(iceFillBoard, count - 1, path); - if (newPath != null) { - return newPath; - } else { - path.remove(path.size() - 1); - } - } - - return null; - } - - /* - void solve(boolean[][] iceFillBoard, List iceFillPath) { - Vector2ic start = new Vector2i(iceFillBoard.length - 1, iceFillBoard[0].length / 2); - int count = iceFillBoard.length * iceFillBoard[0].length - Arrays.stream(iceFillBoard).mapToInt(Booleans::countTrue).sum(); - - Vector2ic[] newPath = solveDfs(iceFillBoard, count - 1, new Vector2ic[]{start}); - if (newPath != null) { - iceFillPath.clear(); - iceFillPath.addAll(Arrays.asList(newPath)); - } - } - - private Vector2ic[] solveDfs(boolean[][] iceFillBoard, int count, Vector2ic[] path) { - Vector2ic pos = path[path.length - 1]; - if (pos.x() == 0 && pos.y() == iceFillBoard[0].length / 2 && count == 0) { - return path; - } - - Vector2ic newPos = pos.add(1, 0, new Vector2i()); - if (newPos.x() < iceFillBoard.length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { - Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); - newPath[path.length] = newPos; - newPath = solveDfs(iceFillBoard, count - 1, newPath); - if (newPath != null) { - return newPath; - } - } - - newPos = pos.add(-1, 0, new Vector2i()); - if (newPos.x() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { - Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); - newPath[path.length] = newPos; - newPath = solveDfs(iceFillBoard, count - 1, newPath); - if (newPath != null) { - return newPath; - } - } - - newPos = pos.add(0, 1, new Vector2i()); - if (newPos.y() < iceFillBoard[0].length && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { - Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); - newPath[path.length] = newPos; - newPath = solveDfs(iceFillBoard, count - 1, newPath); - if (newPath != null) { - return newPath; - } - } - - newPos = pos.add(0, -1, new Vector2i()); - if (newPos.y() >= 0 && !iceFillBoard[newPos.x()][newPos.y()] && !ArrayUtils.contains(path, newPos)) { - Vector2ic[] newPath = Arrays.copyOf(path, path.length + 1); - newPath[path.length] = newPos; - newPath = solveDfs(iceFillBoard, count - 1, newPath); + visited.add(newPos); + List newPath = solveDfs(iceFillBoard, count - 1, path, visited); if (newPath != null) { return newPath; } + path.remove(path.size() - 1); + visited.remove(newPos); } return null; } - */ @Override public void render(WorldRenderContext context) { diff --git a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java index 511d1148..a3cbb93f 100644 --- a/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java +++ b/src/test/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/IceFillTest.java @@ -1,6 +1,8 @@ package de.hysky.skyblocker.skyblock.dungeon.puzzle; +import org.joml.Vector2i; import org.joml.Vector2ic; +import org.junit.jupiter.api.Assertions; import org.junit.jupiter.api.Test; import java.util.ArrayList; @@ -21,7 +23,7 @@ public class IceFillTest { @Test void testIceFillSolve() { IceFill.INSTANCE.solve(iceFillBoard, iceFillPath); - System.out.println(iceFillPath); - System.out.println(iceFillPath.size()); + List expectedIceFillPath = List.of(new Vector2i(6, 3), new Vector2i(5, 3), new Vector2i(4, 3), new Vector2i(3, 3), new Vector2i(3, 2), new Vector2i(4, 2), new Vector2i(5, 2), new Vector2i(6, 2), new Vector2i(6, 1), new Vector2i(5, 1), new Vector2i(5, 0), new Vector2i(4, 0), new Vector2i(4, 1), new Vector2i(3, 1), new Vector2i(3, 0), new Vector2i(2, 0), new Vector2i(1, 0), new Vector2i(0, 0), new Vector2i(0, 1), new Vector2i(1, 1), new Vector2i(2, 1), new Vector2i(2, 2), new Vector2i(1, 2), new Vector2i(1, 3), new Vector2i(1, 4), new Vector2i(1, 5), new Vector2i(2, 5), new Vector2i(3, 5), new Vector2i(3, 4), new Vector2i(4, 4), new Vector2i(5, 4), new Vector2i(6, 4), new Vector2i(6, 5), new Vector2i(6, 6), new Vector2i(5, 6), new Vector2i(5, 5), new Vector2i(4, 5), new Vector2i(4, 6), new Vector2i(3, 6), new Vector2i(2, 6), new Vector2i(1, 6), new Vector2i(0, 6), new Vector2i(0, 5), new Vector2i(0, 4), new Vector2i(0, 3)); + Assertions.assertEquals(expectedIceFillPath, iceFillPath); } } -- cgit