diff options
Diffstat (limited to 'src/main/java')
4 files changed, 427 insertions, 222 deletions
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/ProcessorFactory.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/ProcessorFactory.java index 33196531..44bc9fb6 100644 --- a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/ProcessorFactory.java +++ b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/ProcessorFactory.java @@ -1,6 +1,6 @@ package kr.syeyoung.dungeonsguide.roomprocessor; -import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom; +import kr.syeyoung.dungeonsguide.roomprocessor.boxpuzzle.RoomProcessorBoxSolver; import kr.syeyoung.dungeonsguide.roomprocessor.waterpuzzle.RoomProcessorWaterPuzzle; import java.util.HashMap; diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/RoomProcessorBoxSolver.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/RoomProcessorBoxSolver.java deleted file mode 100644 index 5d2d479d..00000000 --- a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/RoomProcessorBoxSolver.java +++ /dev/null @@ -1,221 +0,0 @@ -package kr.syeyoung.dungeonsguide.roomprocessor; - -import kr.syeyoung.dungeonsguide.dungeon.data.OffsetPointSet; -import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom; -import kr.syeyoung.dungeonsguide.utils.RenderUtils; -import lombok.AllArgsConstructor; -import lombok.Data; -import net.minecraft.block.Block; -import net.minecraft.client.Minecraft; -import net.minecraft.init.Blocks; -import net.minecraft.util.BlockPos; -import net.minecraft.world.World; - -import java.awt.*; -import java.util.ArrayList; -import java.util.Arrays; -import java.util.LinkedList; -import java.util.List; - -public class RoomProcessorBoxSolver extends GeneralRoomProcessor { - - - private BlockPos[][] poses = new BlockPos[6][7]; - private boolean bugged= true; - public RoomProcessorBoxSolver(DungeonRoom dungeonRoom) { - super(dungeonRoom); - - OffsetPointSet ops = (OffsetPointSet) dungeonRoom.getDungeonRoomInfo().getProperties().get("board"); - try { - if (ops != null) { - for (int y = 0; y < 6; y++) { - for (int x = 0; x < 7; x++) { - poses[y][x] = ops.getOffsetPointList().get(y * 7 + x).getBlockPos(dungeonRoom); - } - } - bugged = false; - } - } catch (Exception e) { - e.printStackTrace(); - } - } - - private byte[][] buildCurrentState() { - World w = getDungeonRoom().getContext().getWorld(); - byte[][] board = new byte[poses.length][poses[0].length]; - for (int y = 0; y < poses.length; y++) { - for (int x = 0; x < poses[0].length; x++) { - BlockPos pos = poses[y][x]; - Block b = w.getChunkFromBlockCoords(pos).getBlock(pos); - if (b == Blocks.air) - board[y][x] = 0; - else - board[y][x] = 1; - } - } - return board; - } - - private byte[][] lastboard; - - private static final List<Point> directions = Arrays.asList(new Point(0,-1), new Point(-1,0), new Point(1,0), new Point(0,1)); - private LinkedList<Action> solve(byte[][] board, int playerX, int playerY) { // result:: playerY == 0 - if (playerY == 0) { - LinkedList<Action> moves = new LinkedList<Action>(); - return moves; - } - for (Point dir:directions) { - int resX = playerX + dir.x; - int resY = playerY + dir.y; - if (resX < 0 || resY < 0 || resX >= board[0].length|| resY>=board.length || (board[resY][resX] > 1 && resY > 0) ||(board[resY][resX] > 3)) continue; - byte[][] copied = new byte[board.length][]; - for (int y = 0; y < copied.length; y++) - copied[y] = board[y].clone(); - - LinkedList<Action> solved = null; - boolean pushed = false; - if (board[resY][resX] == 1) { - if (!push(copied, resX, resY, dir.x, dir.y)) { - continue; - } - pushed = true; - solved = solve(copied, playerX, playerY); - } else { - copied[playerY][playerX] += 2; - solved = solve(copied, resX, resY); - } - if (solved != null) { - if (pushed) { - solved.addFirst(new Push(dir.x, dir.y)); - } else { - solved.addFirst(new Move(resX, resY)); - } - return solved; - } - } - return null; - } - - public static interface Action { } - @Data - @AllArgsConstructor - public static class Move implements Action { - private int x; - private int y; - } - @Data - @AllArgsConstructor - public static class Push implements Action { - private int dx; - private int dy; - } - - private 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; - if (resultingX < 0 || resultingY < 0 || resultingX >= board[0].length || resultingY >= board.length) return false; - if (board[resultingY][resultingX] == 1) return false; - - board[resultingY][resultingX] = 1; - board[y][x] = 0; - return true; - } - - @Override - public void tick() { - super.tick(); - if (bugged) return; - byte[][] currboard = buildCurrentState(); - boolean calculate = lastboard == null; - if (!calculate) { - label: - for (int y = 0; y < 6; y ++) { - for (int x = 0; x < 7; x++) - if (currboard[y][x] != lastboard[y][x]) { - calculate = true; - break label; - } - } - } - if (calculate) { - for (int i = 0; i < 7; i++) { - if (currboard[5][i] == 0) { - try { - solution = solve(currboard, i, 5); - if (solution != null) { - solution.addFirst(new Move(i, 5)); - break; - } - } catch (Error e) { - e.printStackTrace(); - } - } - } - } - lastboard = currboard; - } - - private LinkedList<Action> solution; - - public Point getPlayerPos(byte[][] map) { - BlockPos playerPos = Minecraft.getMinecraft().thePlayer.getPosition(); - int minDir = Integer.MAX_VALUE; - Point pt = null; - for (int y = 0; y < poses.length; y++) { - for (int x = 0; x < poses[0].length; x++) { - if (map[y][x] == 1) continue; - int dir = (int) poses[y][x].distanceSq(playerPos); - if (dir < minDir) { - minDir = dir; - pt = new Point(x,y); - } - } - } - return pt; - } - - @Override - public void drawWorld(float partialTicks) { - super.drawWorld(partialTicks); - if (bugged) return; - if (solution == null) return; - try { - List<BlockPos> line = new ArrayList<BlockPos>(); - List<BlockPos> push = new ArrayList<BlockPos>(); - BlockPos lastLoc2 = null; - Move lastLoc = null; - for (Action action : solution) { - if (action instanceof Move) { - BlockPos pos = poses[((Move) action).getY()][((Move) action).getX()]; - line.add(pos.add(0, -1, 0)); - lastLoc = (Move) action; - lastLoc2 = pos; - } else if (action instanceof Push) { - int y = lastLoc.getY() + ((Push) action).getDy(); - int x = lastLoc.getX() + ((Push) action).getDx(); - - BlockPos vec = poses[y][x].subtract(lastLoc2); - if (vec.getZ() > 1 || vec.getZ() < -1) vec = new BlockPos(vec.getX(),0,vec.getZ() >1 ? 1:-1); - if (vec.getX() > 1 || vec.getX() < -1) vec = new BlockPos(vec.getX() >1 ? 1:-1,0,vec.getZ()); - push.add(lastLoc2.add(vec)); - } - } - boolean depth = Minecraft.getMinecraft().thePlayer.getPosition().getY() < 68; - - RenderUtils.drawLines(line, new Color(0, 255, 0, 255), partialTicks, depth); - for (BlockPos b2:push) - RenderUtils.highlightBlock(b2, new Color(0, 255, 0, 50), partialTicks, depth); - } catch (Exception e) { - e.printStackTrace(); - } - } - - public static class Generator implements RoomProcessorGenerator<RoomProcessorBoxSolver> { - @Override - public RoomProcessorBoxSolver createNew(DungeonRoom dungeonRoom) { - RoomProcessorBoxSolver defaultRoomProcessor = new RoomProcessorBoxSolver(dungeonRoom); - return defaultRoomProcessor; - } - } -} diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java new file mode 100644 index 00000000..010b5470 --- /dev/null +++ b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/BoxPuzzleSolvingThread.java @@ -0,0 +1,135 @@ +package kr.syeyoung.dungeonsguide.roomprocessor.boxpuzzle; + +import lombok.AllArgsConstructor; +import lombok.Data; +import lombok.Getter; +import lombok.Setter; + +import java.awt.*; +import java.util.*; +import java.util.List; + +@Getter +@Setter +public class BoxPuzzleSolvingThread extends Thread { + private byte[][] data; + private int playerX; + private int playerY; + private Runnable callback; + + + public BoxPuzzleSolvingThread(byte[][] data, int playerX, int playerY, Runnable onDone) { + this.data = data; + this.playerX = playerX; + this.playerY = playerY; + this.callback = onDone; + } + + LinkedList<BoxMove> solution = new LinkedList<BoxMove>(); + + private boolean solved = false; + + @Override + public void run() { + solved = false; + solution = solve(data,playerX,playerY); + callback.run(); + solved = true; + } + + public static String stateString(byte[][] array) { + StringBuilder sb = new StringBuilder(); + for (int y = 0; y < array.length; y++) + for(int x = 0; x < array[y].length; x++) + sb.append(array[y][x]); + + return sb.toString(); + } + + + 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 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; + } + if (board[resY][resX] > 0) { + possibleBoxMoves.add(new BoxMove(resX, resY, dir.x, dir.y)); + continue; + } + 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; + } + } + } + prevStates.remove(stateId); + + return null; + } + + + private 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; + if (resultingX < 0 || resultingY < 0 || resultingX >= board[0].length || resultingY >= board.length) return false; + if (board[resultingY][resultingX] == 1 || resultingY == 6) return false; + + board[resultingY][resultingX] = 1; + board[y][x] = 0; + return true; + } + + @Data + @AllArgsConstructor + public static class BoxMove { + int x; + int y; + int dx; + int dy; + } +} diff --git a/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java new file mode 100644 index 00000000..715252d1 --- /dev/null +++ b/src/main/java/kr/syeyoung/dungeonsguide/roomprocessor/boxpuzzle/RoomProcessorBoxSolver.java @@ -0,0 +1,291 @@ +package kr.syeyoung.dungeonsguide.roomprocessor.boxpuzzle; + +import kr.syeyoung.dungeonsguide.dungeon.data.OffsetPointSet; +import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom; +import kr.syeyoung.dungeonsguide.roomprocessor.GeneralRoomProcessor; +import kr.syeyoung.dungeonsguide.roomprocessor.RoomProcessorGenerator; +import kr.syeyoung.dungeonsguide.utils.RenderUtils; +import lombok.AllArgsConstructor; +import lombok.Data; +import net.minecraft.block.Block; +import net.minecraft.client.Minecraft; +import net.minecraft.client.gui.FontRenderer; +import net.minecraft.init.Blocks; +import net.minecraft.util.BlockPos; +import net.minecraft.util.ChatComponentText; +import net.minecraft.util.IChatComponent; +import net.minecraft.util.MathHelper; +import net.minecraft.world.World; + +import java.awt.*; +import java.util.*; +import java.util.List; + +public class RoomProcessorBoxSolver extends GeneralRoomProcessor { + + + private BlockPos[][] poses = new BlockPos[6][7]; + private boolean bugged= true; + + private BoxPuzzleSolvingThread puzzleSolvingThread; + + public RoomProcessorBoxSolver(DungeonRoom dungeonRoom) { + super(dungeonRoom); + + OffsetPointSet ops = (OffsetPointSet) dungeonRoom.getDungeonRoomInfo().getProperties().get("board"); + try { + if (ops != null) { + for (int y = 0; y < 6; y++) { + for (int x = 0; x < 7; x++) { + poses[y][x] = ops.getOffsetPointList().get(y * 7 + x).getBlockPos(dungeonRoom); + } + } + bugged = false; + } + } catch (Exception e) { + e.printStackTrace(); + } + } + + private byte[][] buildCurrentState() { + World w = getDungeonRoom().getContext().getWorld(); + byte[][] board = new byte[poses.length][poses[0].length]; + for (int y = 0; y < poses.length; y++) { + for (int x = 0; x < poses[0].length; x++) { + if (y == 6) { + board[y][x] = 0; + continue; + } + BlockPos pos = poses[y][x]; + Block b = w.getChunkFromBlockCoords(pos).getBlock(pos); + if (b == Blocks.air) + board[y][x] = 0; + else + board[y][x] = 1; + } + } + return board; + } + + private boolean calcReq = true; + + private boolean calcDone= false; + private boolean calcDone2 = false; + private int step = 0; + private byte[][] lastState; + + @Override + public void tick() { + super.tick(); + if (bugged) return; + byte[][] currboard = buildCurrentState(); + if (puzzleSolvingThread == null) { + calcDone = false; + puzzleSolvingThread = new BoxPuzzleSolvingThread(currboard, 0, 5, new Runnable() { + @Override + public void run() { + calcDone = true; + calcDone2 = true; + } + }); + puzzleSolvingThread.start(); + } + if (calcReq) { + calcDone = false; + puzzleSolvingThread = new BoxPuzzleSolvingThread(currboard, 0, 5, new Runnable() { + @Override + public void run() { + calcDone = true; + calcDone2 = true; + } + }); + puzzleSolvingThread.start(); + calcReq = false; + } + + boolean pathFindReq = false; + if (calcDone2) { + this.solution = puzzleSolvingThread.solution; + if (solution == null) { + Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: §cCouldn't find solution involving less than 20 box moves")); + } else{ + Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: Solution Found!")); + } + step = 0; + lastState = currboard; + calcDone2 = false; + pathFindReq = true; + } + + if (lastState == null) return; + boolean moved = false; + label: + for (int y = 0 ; y < currboard.length; y++) { + for (int x = 0; x < currboard[y].length; x++) { + if (lastState[y][x] != currboard[y][x]) { + moved = true; + break label; + } + } + } + + 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); + boolean currYState = Minecraft.getMinecraft().thePlayer.getPosition().getY() < 68; + if (((currYState && !player.equals(lastPlayer)) || (currYState != yState) || (moved) || pathFindReq) && solution != null) { + Point target = null; + if (step < solution.size()) { + BoxPuzzleSolvingThread.BoxMove boxMove = solution.get(step); + target = new Point(boxMove.x - boxMove.dx, boxMove.y - boxMove.dy); + } + List<Point> semi_pathFound = pathfind(currboard, player, target); + pathFound = new LinkedList<BlockPos>(); + for (Point point : semi_pathFound) { + pathFound.add(poses[point.y][point.x].add(0,-1,0)); + } + + lastPlayer = player; + yState = currYState; + } + + } + private boolean yState = true; + public Point getPlayerPos(byte[][] map) { + BlockPos playerPos = Minecraft.getMinecraft().thePlayer.getPosition(); + int minDir = Integer.MAX_VALUE; + Point pt = null; + for (int y = 0; y < poses.length; y++) { + for (int x = 0; x < poses[0].length; x++) { + if (map[y][x] == 1) continue; + int dir = (int) poses[y][x].distanceSq(playerPos); + if (dir < minDir) { + minDir = dir; + pt = new Point(x,y); + } + } + } + return pt; + } + + private List<BoxPuzzleSolvingThread.BoxMove> solution; + private List<BlockPos> pathFound; + 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)); + public List<Point> pathfind(byte[][] map, Point start, Point target2) { + int[][] distances = new int[map.length][map[0].length]; + + Queue<Point> evalulate = new LinkedList<Point>(); + evalulate.add(start); + Point target = null; + while (!evalulate.isEmpty()) { + Point p = evalulate.poll(); + if (p.equals(target2) || (target2 == null &&p.y == 0)) { + target = p; + break; + } + int max = 0; + for (Point dir:directions) { + int resX= p.x + dir.x; + int resY = p.y + dir.y; + if (resX < 0 || resY < 0 || resX >= distances[0].length || resY >= distances.length) { + continue; + } + + if (max < distances[resY][resX]) { + max = distances[resY][resX]; + } + if (distances[resY][resX] == 0 && map[resY][resX] == 0) { + evalulate.add(new Point(resX, resY)); + } + } + distances[p.y][p.x] = max + 1; + } + if (target == null) return Collections.emptyList(); + + List<Point> route = new LinkedList<Point>(); + while(!target.equals(start)) { + route.add(target); + int min = Integer.MAX_VALUE; + Point minPoint = null; + for (Point dir:directions) { + int resX= target.x + dir.x; + int resY = target.y + dir.y; + if (resX < 0 || resY < 0 || resX >= distances[0].length || resY >= distances.length) { + continue; + } + + if (min > distances[resY][resX] && distances[resY][resX] != 0) { + min = distances[resY][resX]; + minPoint = new Point(resX, resY); + } + } + target = minPoint; + } + route.add(start); + return route; + } + + @Override + public void chatReceived(IChatComponent chat) { + if (chat.getFormattedText().toLowerCase().contains("recalc")) { + if (calcDone) { + calcReq = true; + Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: Recalculating Route...")); + } else { + calcReq = true; + Minecraft.getMinecraft().thePlayer.addChatMessage(new ChatComponentText("§eDungeons Guide :::: Currently Calculating Route...")); + } + } + } + + @Override + public void drawScreen(float partialTicks) { + super.drawScreen(partialTicks); + FontRenderer fr = Minecraft.getMinecraft().fontRendererObj; + fr.drawString("Type recalc in chat for recalculation of route", 10, Minecraft.getMinecraft().displayHeight / 2, 0xFFFFFF); + } + + @Override + public void drawWorld(float partialTicks) { + super.drawWorld(partialTicks); + 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 (pathFound != null) { + RenderUtils.drawLines(pathFound, new Color(0,255,0,255), partialTicks, true); + } + + } + + public static class Generator implements RoomProcessorGenerator<RoomProcessorBoxSolver> { + @Override + public RoomProcessorBoxSolver createNew(DungeonRoom dungeonRoom) { + RoomProcessorBoxSolver defaultRoomProcessor = new RoomProcessorBoxSolver(dungeonRoom); + return defaultRoomProcessor; + } + } + + + +} |