From 7b240ed30ca76f65deaab751879ecf7e822d6616 Mon Sep 17 00:00:00 2001 From: syeyoung <42869671+cyoung06@users.noreply.github.com> Date: Tue, 1 Dec 2020 00:21:57 +0900 Subject: BOX SOLVER but better --- .../boxpuzzle/BoxPuzzleSolvingThread.java | 145 +++++++++++++-------- .../boxpuzzle/RoomProcessorBoxSolver.java | 91 ++++++++++--- 2 files changed, 159 insertions(+), 77 deletions(-) (limited to 'src/main/java/kr/syeyoung/dungeonsguide') diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java index 010b5470..f4412419 100644 --- a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java +++ b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java @@ -25,18 +25,19 @@ public class BoxPuzzleSolvingThread extends Thread { this.callback = onDone; } - LinkedList solution = new LinkedList(); + Route solution = null; private boolean solved = false; @Override public void run() { solved = false; - solution = solve(data,playerX,playerY); + solution = solve(data,playerX,playerY, 20); callback.run(); solved = true; } + public static String stateString(byte[][] array) { StringBuilder sb = new StringBuilder(); for (int y = 0; y < array.length; y++) @@ -47,72 +48,76 @@ public class BoxPuzzleSolvingThread extends Thread { } - private static LinkedList solve(byte[][] board, int playerX, int playerY) { - for (int i = 10; i < 20; i++) { - LinkedList solvedStateBoxMove = solve(new HashSet(), board, playerX, playerY, 0, i); - if (solvedStateBoxMove != null) - return solvedStateBoxMove; - } - return null; - } + private static final List directions = Arrays.asList(new Point(-1,0), new Point(1,0), new Point(0,1), new Point(0,-1)); + private static Route solve(byte[][] boardStart, int playerX, int playerY, int maxRecursion) { // result:: playerY == 0 + Queue routes = new LinkedList(); + Set globalStatesBeen = new HashSet(); - private static final java.util.List directions = Arrays.asList(new Point(-1,0), new Point(1,0), new Point(0,1), new Point(0,-1)); - private static LinkedList solve(Set prevStates, byte[][] board, int playerX, int playerY, int recursionLevel, int maxRecursion) { // result:: playerY == 0 - String stateId = stateString(board); - if (maxRecursion < recursionLevel) return null; - if (prevStates.contains(stateId)) return null; - - java.util.Queue points = new LinkedList(); - Set reached= new HashSet(); - List possibleBoxMoves = new ArrayList(); - points.add(new Point(playerX, playerY)); - - while (!points.isEmpty()) { - Point pt = points.poll(); - if (pt.y == 0) { - return new LinkedList(); - } - if (reached.contains(pt)) continue; - reached.add(pt); - for (Point dir:directions) { - int resX= pt.x + dir.x; - int resY = pt.y + dir.y; - if (resX < 0 || resY < 0 || resX >= board[0].length || resY >= board.length) { - continue; + Route r = new Route(); + r.currentState = boardStart; + routes.add(r); + + while (!routes.isEmpty()) { + Route route = routes.poll(); + + if (routes.size() > 3000000) return null; + + String stateId = stateString(route.currentState); + if (maxRecursion < route.boxMoves.size()) continue; + if (globalStatesBeen.contains(stateId)) continue; + + Queue points = new LinkedList(); + Set reached= new HashSet(); + List possibleBoxMoves = new ArrayList(); + points.add(new Point(playerX, playerY)); + + while (!points.isEmpty()) { + Point pt = points.poll(); + if (pt.y == 0) { + return route; } - if (board[resY][resX] > 0) { - possibleBoxMoves.add(new BoxMove(resX, resY, dir.x, dir.y)); - continue; + if (reached.contains(pt)) continue; + reached.add(pt); + for (Point dir:directions) { + int resX= pt.x + dir.x; + int resY = pt.y + dir.y; + if (resX < 0 || resY < 0 || resX >= route.currentState[0].length || resY >= route.currentState.length) { + continue; + } + if (route.currentState[resY][resX] > 0) { + possibleBoxMoves.add(new BoxMove(resX, resY, dir.x, dir.y)); + continue; + } + points.add(new Point(resX, resY)); } - points.add(new Point(resX, resY)); } - } - prevStates.add(stateId); - for (BoxMove possibleBoxMove : possibleBoxMoves) { - byte[][] copied = new byte[board.length][]; - for (int y = 0; y < copied.length; y++) - copied[y] = board[y].clone(); - - if (push(copied, possibleBoxMove.x, possibleBoxMove.y, possibleBoxMove.dx, possibleBoxMove.dy)){ -// System.out.println("------testing "+recursionLevel+" "+possibleBoxMove.x+","+possibleBoxMove.y); -// print(copied); - - prevStates.add(stateId); - LinkedList moves = solve(prevStates, copied, possibleBoxMove.x, possibleBoxMove.y, recursionLevel +1, maxRecursion); - if (moves != null) { - moves.addFirst(possibleBoxMove); - return moves; + globalStatesBeen.add(stateId); + for (BoxMove possibleBoxMove : possibleBoxMoves) { + byte[][] copied = new byte[route.currentState.length][]; + for (int y = 0; y < copied.length; y++) + copied[y] = route.currentState[y].clone(); + + if (push(copied, possibleBoxMove.x, possibleBoxMove.y, possibleBoxMove.dx, possibleBoxMove.dy)){ + String stateId2 = stateString(copied); + if (globalStatesBeen.contains(stateId2)) continue; + + Route route2 = new Route(); + route2.boxMoves = new ArrayList(route.boxMoves); + route2.boxMoves.add(possibleBoxMove); + route2.currentState = copied; + + routes.add(route2); } } } - prevStates.remove(stateId); + return null; } - private static boolean push(byte[][] board, int x,int y,int dx,int dy) { + public static boolean push(byte[][] board, int x,int y,int dx,int dy) { if (board[y][x] != 1) return false; int resultingX= x + dx; int resultingY = y +dy; @@ -124,12 +129,38 @@ public class BoxPuzzleSolvingThread extends Thread { return true; } - @Data - @AllArgsConstructor public static class BoxMove { int x; int y; int dx; int dy; + + public BoxMove(int x, int y, int dx, int dy) { + this.x = x; + this.y = y; + this.dx = dx; + this.dy = dy; + } + + public int getX() { + return x; + } + + public int getY() { + return y; + } + + public int getDx() { + return dx; + } + + public int getDy() { + return dy; + } + } + + public static class Route { + List boxMoves = new LinkedList(); + byte[][] currentState; } } diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java index 715252d1..05a8e474 100644 --- a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java +++ b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java @@ -10,6 +10,7 @@ import lombok.Data; import net.minecraft.block.Block; import net.minecraft.client.Minecraft; import net.minecraft.client.gui.FontRenderer; +import net.minecraft.client.renderer.entity.RenderIronGolem; import net.minecraft.init.Blocks; import net.minecraft.util.BlockPos; import net.minecraft.util.ChatComponentText; @@ -105,16 +106,19 @@ public class RoomProcessorBoxSolver extends GeneralRoomProcessor { boolean pathFindReq = false; if (calcDone2) { - this.solution = puzzleSolvingThread.solution; + BoxPuzzleSolvingThread.Route semi_solution = puzzleSolvingThread.solution; if (solution == null) { - Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: §cCouldn't find solution involving less than 20 box moves")); + Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: §cCouldn't find solution involving less than 20 box moves within 3m concurrent possibility")); } else{ + solution = semi_solution.boxMoves; Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: Solution Found!")); } step = 0; lastState = currboard; calcDone2 = false; pathFindReq = true; + + calcTotalPath(); } if (lastState == null) return; @@ -131,9 +135,6 @@ public class RoomProcessorBoxSolver extends GeneralRoomProcessor { if (moved) { step++; - if (step == solution.size()) { - Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: Congratulations! box puzzle is now solved")); - } } Point player = getPlayerPos(currboard); @@ -155,6 +156,41 @@ public class RoomProcessorBoxSolver extends GeneralRoomProcessor { } } + + public void calcTotalPath() { + Point player = new Point(0,5); + totalPath = new LinkedList(); + totalPushedBlocks = new LinkedList(); + byte[][] currboard = buildCurrentState(); + for (int i = 0; i <= solution.size(); i++) { + Point target = null; + BoxPuzzleSolvingThread.BoxMove boxMove = null; + if (i < solution.size()) { + boxMove = solution.get(i); + target = new Point(boxMove.x - boxMove.dx, boxMove.y - boxMove.dy); + } + List semi_pathFound = pathfind(currboard, player, target); + for (Point point : semi_pathFound) { + totalPath.add(poses[point.y][point.x].add(0, -1, 0)); + } + + player = target; + if (boxMove != null) { + BoxPuzzleSolvingThread.push(currboard, boxMove.x, boxMove.y, boxMove.dx, boxMove.dy); + int fromX = boxMove.x - boxMove.dx; + int fromY = boxMove.y - boxMove.dy; + + BlockPos pos = poses[fromY][fromX]; + BlockPos pos2 = poses[boxMove.y][boxMove.x]; + BlockPos dir = pos.subtract(pos2); + dir = new BlockPos(MathHelper.clamp_int(dir.getX(), -1,1), 0, MathHelper.clamp_double(dir.getZ(), -1, 1)); + + BlockPos highlight = pos2.add(dir); + totalPushedBlocks.add(highlight); + } + } + } + private boolean yState = true; public Point getPlayerPos(byte[][] map) { BlockPos playerPos = Minecraft.getMinecraft().thePlayer.getPosition(); @@ -175,6 +211,8 @@ public class RoomProcessorBoxSolver extends GeneralRoomProcessor { private List solution; private List pathFound; + private List totalPath; + private List totalPushedBlocks; private Point lastPlayer; private static final java.util.List directions = Arrays.asList(new Point(-1,0), new Point(1,0), new Point(0,1), new Point(0,-1)); @@ -258,22 +296,35 @@ public class RoomProcessorBoxSolver extends GeneralRoomProcessor { if (bugged) return; if (!calcDone) return; if (solution == null) return; - if (step < solution.size()) { - BoxPuzzleSolvingThread.BoxMove boxMove = solution.get(step); - int fromX = boxMove.x - boxMove.dx; - int fromY = boxMove.y - boxMove.dy; - - BlockPos pos = poses[fromY][fromX]; - BlockPos pos2 = poses[boxMove.y][boxMove.x]; - BlockPos dir = pos.subtract(pos2); - dir = new BlockPos(MathHelper.clamp_int(dir.getX(), -1,1), 0, MathHelper.clamp_double(dir.getZ(), -1, 1)); - - BlockPos highlight = pos2.add(dir); - RenderUtils.highlightBlock(highlight, new Color(0,255,0,MathHelper.clamp_int((int) (255 - Minecraft.getMinecraft().thePlayer.getPosition().distanceSq(highlight)),50,255)), partialTicks, false); - } + if (Minecraft.getMinecraft().thePlayer.getPosition().getY() < 68) { + if (step < solution.size()) { + BoxPuzzleSolvingThread.BoxMove boxMove = solution.get(step); + int fromX = boxMove.x - boxMove.dx; + int fromY = boxMove.y - boxMove.dy; + + BlockPos pos = poses[fromY][fromX]; + BlockPos pos2 = poses[boxMove.y][boxMove.x]; + BlockPos dir = pos.subtract(pos2); + dir = new BlockPos(MathHelper.clamp_int(dir.getX(), -1, 1), 0, MathHelper.clamp_double(dir.getZ(), -1, 1)); - if (pathFound != null) { - RenderUtils.drawLines(pathFound, new Color(0,255,0,255), partialTicks, true); + BlockPos highlight = pos2.add(dir); + RenderUtils.highlightBlock(highlight, new Color(0, 255, 0, MathHelper.clamp_int((int) (255 - Minecraft.getMinecraft().thePlayer.getPosition().distanceSq(highlight)), 50, 255)), partialTicks, false); + } + + if (pathFound != null) { + RenderUtils.drawLines(pathFound, new Color(0, 255, 0, 255), partialTicks, true); + } + } else { + if (totalPath != null) { + RenderUtils.drawLines(totalPath, new Color(0, 255, 0, 255), partialTicks, false); + } + if (totalPushedBlocks != null) { + for (int i = 0; i < totalPushedBlocks.size(); i++) { + BlockPos pos = totalPushedBlocks.get(i); + RenderUtils.highlightBlock(pos, new Color(0, 255, 255, 255), partialTicks, false); + RenderUtils.drawTextAtWorld("#"+i, pos.getX()+0.5f, pos.getY() +0.5f, pos.getZ() + 0.5f, 0xFF00000, 1.5f, false, false, partialTicks); + } + } } } -- cgit