BOX SOLVER but better

2 files changed, 159 insertions, 77 deletions

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<BoxMove> solution = new LinkedList<BoxMove>();
+    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<BoxMove> solve(byte[][] board, int playerX, int playerY) {
-        for (int i = 10; i < 20; i++) {
-            LinkedList<BoxMove> solvedStateBoxMove = solve(new HashSet<String>(), board, playerX, playerY, 0, i);
-            if (solvedStateBoxMove != null)
-                return solvedStateBoxMove;
-        }
-        return null;
-    }
+    private static final List<Point> 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<Route> routes = new LinkedList<Route>();
+        Set<String> globalStatesBeen = new HashSet<String>();
 
-    private static final java.util.List<Point> directions = Arrays.asList(new Point(-1,0), new Point(1,0), new Point(0,1), new Point(0,-1));
-    private static LinkedList<BoxMove> solve(Set<String> 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<Point> points = new LinkedList<Point>();
-        Set<Point> reached= new HashSet<Point>();
-        List<BoxMove> possibleBoxMoves = new ArrayList<BoxMove>();
-        points.add(new Point(playerX, playerY));
-
-        while (!points.isEmpty()) {
-            Point pt = points.poll();
-            if (pt.y == 0) {
-                return new LinkedList<BoxMove>();
-            }
-            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<Point> points = new LinkedList<Point>();
+            Set<Point> reached= new HashSet<Point>();
+            List<BoxMove> possibleBoxMoves = new ArrayList<BoxMove>();
+            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<BoxMove> 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<BoxMove>(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<BoxMove> boxMoves = new LinkedList<BoxMove>();
+        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<BlockPos>();
+        totalPushedBlocks = new LinkedList<BlockPos>();
+        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<Point> 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<BoxPuzzleSolvingThread.BoxMove> solution;
     private List<BlockPos> pathFound;
+    private List<BlockPos> totalPath;
+    private List<BlockPos> totalPushedBlocks;
     private Point lastPlayer;
 
     private static final java.util.List<Point> 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);
+                }
+            }
         }
 
     }