Boulder Solver (#540)

8 files changed, 577 insertions, 0 deletions

diff --git a/src/main/java/de/hysky/skyblocker/SkyblockerMod.java b/src/main/java/de/hysky/skyblocker/SkyblockerMod.java
index b76e8b53..1aa97526 100644
--- a/src/main/java/de/hysky/skyblocker/SkyblockerMod.java
+++ b/src/main/java/de/hysky/skyblocker/SkyblockerMod.java
@@ -8,6 +8,7 @@ import de.hysky.skyblocker.skyblock.*;
 import de.hysky.skyblocker.skyblock.crimson.kuudra.Kuudra;
 import de.hysky.skyblocker.skyblock.dungeon.*;
 import de.hysky.skyblocker.skyblock.dungeon.partyfinder.PartyFinderScreen;
+import de.hysky.skyblocker.skyblock.dungeon.puzzle.boulder.Boulder;
 import de.hysky.skyblocker.skyblock.dungeon.puzzle.CreeperBeams;
 import de.hysky.skyblocker.skyblock.dungeon.puzzle.DungeonBlaze;
 import de.hysky.skyblocker.skyblock.dungeon.puzzle.TicTacToe;
@@ -137,6 +138,7 @@ public class SkyblockerMod implements ClientModInitializer {
         SpecialEffects.init();
         ItemProtection.init();
         CreeperBeams.init();
+        Boulder.init();
         ItemRarityBackgrounds.init();
         MuseumItemCache.init();
         SecretsTracker.init();
diff --git a/src/main/java/de/hysky/skyblocker/config/SkyblockerConfig.java b/src/main/java/de/hysky/skyblocker/config/SkyblockerConfig.java
index 826495fb..9544ad0f 100644
--- a/src/main/java/de/hysky/skyblocker/config/SkyblockerConfig.java
+++ b/src/main/java/de/hysky/skyblocker/config/SkyblockerConfig.java
@@ -717,6 +717,9 @@ public class SkyblockerConfig {
 		public boolean solveWaterboard = true;
 
 		@SerialEntry
+		public boolean solveBoulder = true;
+
+		@SerialEntry
 		public boolean fireFreezeStaffTimer = true;
 
 		@SerialEntry
diff --git a/src/main/java/de/hysky/skyblocker/config/categories/DungeonsCategory.java b/src/main/java/de/hysky/skyblocker/config/categories/DungeonsCategory.java
index 3b685f9a..5eb9a066 100644
--- a/src/main/java/de/hysky/skyblocker/config/categories/DungeonsCategory.java
+++ b/src/main/java/de/hysky/skyblocker/config/categories/DungeonsCategory.java
@@ -409,6 +409,14 @@ public class DungeonsCategory {
 						.controller(ConfigUtils::createBooleanController)
 						.build())
 				.option(Option.<Boolean>createBuilder()
+						.name(Text.translatable("text.autoconfig.skyblocker.option.locations.dungeons.solveBoulder"))
+						.description(OptionDescription.of(Text.translatable("text.autoconfig.skyblocker.option.locations.dungeons.solveBoulder.@Tooltip")))
+						.binding(defaults.locations.dungeons.solveBoulder,
+								() -> config.locations.dungeons.solveBoulder,
+								newValue -> config.locations.dungeons.solveBoulder = newValue)
+						.controller(ConfigUtils::createBooleanController)
+						.build())
+				.option(Option.<Boolean>createBuilder()
 						.name(Text.translatable("text.autoconfig.skyblocker.option.locations.dungeons.fireFreezeStaffTimer"))
 						.description(OptionDescription.of(Text.translatable("text.autoconfig.skyblocker.option.locations.dungeons.fireFreezeStaffTimer.@Tooltip")))
 						.binding(defaults.locations.dungeons.fireFreezeStaffTimer,
diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/Boulder.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/Boulder.java
new file mode 100644
index 00000000..878c8d0a
--- /dev/null
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/Boulder.java
@@ -0,0 +1,221 @@
+package de.hysky.skyblocker.skyblock.dungeon.puzzle.boulder;
+
+import de.hysky.skyblocker.config.SkyblockerConfigManager;
+import de.hysky.skyblocker.skyblock.dungeon.puzzle.DungeonPuzzle;
+import de.hysky.skyblocker.skyblock.dungeon.secrets.DungeonManager;
+import de.hysky.skyblocker.skyblock.dungeon.secrets.Room;
+import de.hysky.skyblocker.utils.render.RenderHelper;
+import de.hysky.skyblocker.utils.render.title.Title;
+import net.fabricmc.fabric.api.client.rendering.v1.WorldRenderContext;
+import net.minecraft.block.Block;
+import net.minecraft.block.BlockState;
+import net.minecraft.block.Blocks;
+import net.minecraft.client.MinecraftClient;
+import net.minecraft.client.world.ClientWorld;
+import net.minecraft.util.DyeColor;
+import net.minecraft.util.Formatting;
+import net.minecraft.util.math.BlockPos;
+import net.minecraft.util.math.Box;
+import net.minecraft.util.math.Vec3d;
+import net.minecraft.world.BlockView;
+import org.slf4j.Logger;
+import org.slf4j.LoggerFactory;
+
+import java.util.Arrays;
+import java.util.List;
+
+public class Boulder extends DungeonPuzzle {
+    private static final Logger LOGGER = LoggerFactory.getLogger(Boulder.class.getName());
+    private static final Boulder INSTANCE = new Boulder();
+    private static final float[] RED_COLOR_COMPONENTS = DyeColor.RED.getColorComponents();
+    private static final float[] ORANGE_COLOR_COMPONENTS = DyeColor.ORANGE.getColorComponents();
+    private static final int BASE_Y = 65;
+    static Vec3d[] linePoints;
+    static Box boundingBox;
+
+    private Boulder() {
+        super("boulder", "boxes-room");
+    }
+
+    public static void init() {
+    }
+
+    @Override
+    public void tick(MinecraftClient client) {
+
+        if (!shouldSolve() || !SkyblockerConfigManager.get().locations.dungeons.solveBoulder || client.world == null || !DungeonManager.isCurrentRoomMatched()) {
+            return;
+        }
+
+        Room room = DungeonManager.getCurrentRoom();
+
+        BlockPos chestPos = new BlockPos(15, BASE_Y, 29);
+        BlockPos start = new BlockPos(25, BASE_Y, 25);
+        BlockPos end = new BlockPos(5, BASE_Y, 8);
+        // Create a target BoulderObject for the puzzle
+        BoulderObject target = new BoulderObject(chestPos.getX(), chestPos.getX(), chestPos.getZ(), "T");
+        // Create a BoulderBoard representing the puzzle's grid
+        BoulderBoard board = new BoulderBoard(8, 7, target);
+
+        // Populate the BoulderBoard grid with BoulderObjects based on block types in the room
+        int column = 1;
+        for (int z = start.getZ(); z > end.getZ(); z--) {
+            int row = 0;
+            for (int x = start.getX(); x > end.getX(); x--) {
+                if (Math.abs(start.getX() - x) % 3 == 1 && Math.abs(start.getZ() - z) % 3 == 1) {
+                    String blockType = getBlockType(client.world, x, BASE_Y, z);
+                    board.placeObject(column, row, new BoulderObject(x, BASE_Y, z, blockType));
+                    row++;
+                }
+            }
+            if (row == board.getWidth()) {
+                column++;
+            }
+        }
+
+        // Generate initial game states for the A* solver
+        char[][] boardArray = board.getBoardCharArray();
+        List<BoulderSolver.GameState> initialStates = Arrays.asList(
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 0),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 1),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 2),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 3),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 4),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 5),
+                new BoulderSolver.GameState(boardArray, board.getHeight() - 1, 6)
+        );
+
+        // Solve the puzzle using the A* algorithm
+        List<int[]> solution = BoulderSolver.aStarSolve(initialStates);
+
+        if (solution != null) {
+            linePoints = new Vec3d[solution.size()];
+            int index = 0;
+            // Convert solution coordinates to Vec3d points for rendering
+            for (int[] coord : solution) {
+                int x = coord[0];
+                int y = coord[1];
+                // Convert relative coordinates to actual coordinates
+                linePoints[index++] = Vec3d.ofCenter(room.relativeToActual(board.getObject3DPosition(x, y)));
+            }
+
+            BlockPos button = null;
+            if (linePoints != null && linePoints.length > 0) {
+                // Check for buttons along the path of the solution
+                for (int i = 0; i < linePoints.length - 1; i++) {
+                    Vec3d point1 = linePoints[i];
+                    Vec3d point2 = linePoints[i + 1];
+                    button = checkForButtonBlocksOnLine(client.world, point1, point2);
+                    if (button != null) {
+                        // If a button is found, calculate its bounding box
+                        boundingBox = getBlockBoundingBox(client.world, button);
+                        break;
+                    }
+                }
+                if (button == null){
+                    // If no button is found along the path the puzzle is solved; reset the puzzle
+                    reset();
+                }
+            }
+        } else {
+            // If no solution is found, display a title message and reset the puzzle
+            Title title = new Title("skyblocker.dungeons.puzzle.boulder.noSolution", Formatting.GREEN);
+            RenderHelper.displayInTitleContainerAndPlaySound(title, 15);
+            reset();
+        }
+    }
+
+    /**
+     * Retrieves the type of block at the specified position in the world.
+     * If the block is Birch or Jungle plank, it will return "B"; otherwise, it will return ".".
+     *
+     * @param world The client world.
+     * @param x     The x-coordinate of the block.
+     * @param y     The y-coordinate of the block.
+     * @param z     The z-coordinate of the block.
+     * @return The type of block at the specified position.
+     */
+    public static String getBlockType(ClientWorld world, int x, int y, int z) {
+        Block block = world.getBlockState(DungeonManager.getCurrentRoom().relativeToActual(new BlockPos(x, y, z))).getBlock();
+        return (block == Blocks.BIRCH_PLANKS || block == Blocks.JUNGLE_PLANKS) ? "B" : ".";
+    }
+
+    /**
+     * Checks for blocks along the line between two points in the world.
+     * Returns the position of a block if it found a button on the line, if any.
+     *
+     * @param world   The client world.
+     * @param point1  The starting point of the line.
+     * @param point2  The ending point of the line.
+     * @return The position of the block found on the line, or null if no block is found.
+     */
+    private static BlockPos checkForButtonBlocksOnLine(ClientWorld world, Vec3d point1, Vec3d point2) {
+        double x1 = point1.getX();
+        double y1 = point1.getY() + 1;
+        double z1 = point1.getZ();
+
+        double x2 = point2.getX();
+        double y2 = point2.getY() + 1;
+        double z2 = point2.getZ();
+
+        int steps = (int) Math.max(Math.abs(x2 - x1), Math.max(Math.abs(y2 - y1), Math.abs(z2 - z1)));
+
+        double xStep = (x2 - x1) / steps;
+        double yStep = (y2 - y1) / steps;
+        double zStep = (z2 - z1) / steps;
+
+
+        for (int step = 0; step <= steps; step++) {
+            double currentX = x1 + step * xStep;
+            double currentY = y1 + step * yStep;
+            double currentZ = z1 + step * zStep;
+
+            BlockPos blockPos = BlockPos.ofFloored(currentX, currentY, currentZ);
+            Block block = world.getBlockState(blockPos).getBlock();
+
+            if (block == Blocks.STONE_BUTTON) {
+                return blockPos;
+            }
+
+        }
+        return null;
+    }
+
+    /**
+     * Retrieves the bounding box of a block in the world.
+     *
+     * @param world The client world.
+     * @param pos   The position of the block.
+     * @return The bounding box of the block.
+     */
+    public static Box getBlockBoundingBox(BlockView world, BlockPos pos) {
+        BlockState blockState = world.getBlockState(pos);
+        return blockState.getOutlineShape(world, pos).getBoundingBox().offset(pos);
+    }
+
+    @Override
+    public void render(WorldRenderContext context) {
+        if (!shouldSolve() || !SkyblockerConfigManager.get().locations.dungeons.solveBoulder || !DungeonManager.isCurrentRoomMatched())
+            return;
+        float alpha = 1.0f;
+        float lineWidth = 5.0f;
+
+        if (linePoints != null && linePoints.length > 0) {
+            for (int i = 0; i < linePoints.length - 1; i++) {
+                Vec3d startPoint = linePoints[i];
+                Vec3d endPoint = linePoints[i + 1];
+                RenderHelper.renderLinesFromPoints(context, new Vec3d[]{startPoint, endPoint}, ORANGE_COLOR_COMPONENTS, alpha, lineWidth, true);
+            }
+            if (boundingBox != null) {
+                RenderHelper.renderOutline(context, boundingBox, RED_COLOR_COMPONENTS, 5, false);
+            }
+        }
+    }
+
+    @Override
+    public void reset() {
+        super.reset();
+        linePoints = null;
+        boundingBox = null;
+    }
+}
diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderBoard.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderBoard.java
new file mode 100644
index 00000000..d29097e4
--- /dev/null
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderBoard.java
@@ -0,0 +1,129 @@
+package de.hysky.skyblocker.skyblock.dungeon.puzzle.boulder;
+
+import net.minecraft.util.math.BlockPos;
+import net.minecraft.util.math.Direction;
+
+/**
+ * Represents the game board for the Boulder puzzle, managing the grid of BoulderObjects.
+ * This class handles operations such as placing objects on the board, retrieving objects,
+ * and generating a character representation of the game board.
+ */
+public class BoulderBoard {
+    private final int height;
+    private final int width;
+    private final BoulderObject[][] grid;
+
+    /**
+     * Constructs a BoulderBoard with the specified height, width, and target BoulderObject.
+     *
+     * @param height The height of the board.
+     * @param width  The width of the board.
+     * @param target The target BoulderObject that needs to be reached to solve the puzzle.
+     */
+    public BoulderBoard(int height, int width, BoulderObject target) {
+        this.height = height;
+        this.width = width;
+        this.grid = new BoulderObject[height][width];
+
+        int offsetX = target.x() - 23;
+        int y = 65;
+
+        for (int z = 0; z < width; z++) {
+            if (z == width / 2) {
+                grid[0][z] = target;
+            } else {
+                grid[0][z] = new BoulderObject(offsetX, y, z, "B");
+            }
+            grid[height - 1][z] = new BoulderObject(24 - (3 * z), y, 6, "P");
+        }
+    }
+
+    /**
+     * Retrieves the BoulderObject at the specified position on the board.
+     *
+     * @param x The x-coordinate of the position.
+     * @param y The y-coordinate of the position.
+     * @return The BoulderObject at the specified position, or null if no object is present.
+     */
+    public BoulderObject getObjectAtPosition(int x, int y) {
+        return isValidPosition(x, y) ? grid[x][y] : null;
+    }
+
+    /**
+     * Retrieves the 3D position of the BoulderObject at the specified position on the board.
+     *
+     * @param x The x-coordinate of the position.
+     * @param y The y-coordinate of the position.
+     * @return The BlockPos representing the 3D position of the BoulderObject,
+     * or null if no object is present at the specified position.
+     */
+    public BlockPos getObject3DPosition(int x, int y) {
+        BoulderObject object = getObjectAtPosition(x, y);
+        return (object != null) ? object.get3DPosition().offset(Direction.Axis.Y, -1) : null;
+    }
+
+    /**
+     * Places a BoulderObject at the specified position on the board.
+     *
+     * @param x      The x-coordinate of the position.
+     * @param y      The y-coordinate of the position.
+     * @param object The BoulderObject to place on the board.
+     */
+    public void placeObject(int x, int y, BoulderObject object) {
+        grid[x][y] = object;
+    }
+
+    public int getHeight() {
+        return height;
+    }
+
+    public int getWidth() {
+        return width;
+    }
+
+    /**
+     * Checks whether the specified position is valid within the bounds of the game board.
+     *
+     * @param x The x-coordinate of the position to check.
+     * @param y The y-coordinate of the position to check.
+     * @return {@code true} if the position is valid within the bounds of the board, {@code false} otherwise.
+     */
+    private boolean isValidPosition(int x, int y) {
+        return x >= 0 && y >= 0 && x < height && y < width;
+    }
+
+    /**
+     * Generates a character array representation of the game board.
+     * Each character represents a type of BoulderObject or an empty space.
+     *
+     * @return A 2D character array representing the game board.
+     */
+    public char[][] getBoardCharArray() {
+        char[][] boardCharArray = new char[height][width];
+        for (int x = 0; x < height; x++) {
+            for (int y = 0; y < width; y++) {
+                BoulderObject boulderObject = grid[x][y];
+                boardCharArray[x][y] = (boulderObject != null) ? boulderObject.type().charAt(0) : '.';
+            }
+        }
+        return boardCharArray;
+    }
+
+    /**
+     * Prints the current state of the game board to the console.
+     * Each character represents a type of BoulderObject or an empty space.
+     */
+    public String boardToString() {
+        StringBuilder sb = new StringBuilder();
+        for (int x = 0; x < height; x++) {
+            for (int y = 0; y < width; y++) {
+                BoulderObject boulderObject = grid[x][y];
+                String displayChar = (boulderObject != null) ? boulderObject.type() : ".";
+                sb.append(displayChar);
+            }
+            sb.append("\n");
+        }
+        return sb.toString();
+    }
+
+}
diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderObject.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderObject.java
new file mode 100644
index 00000000..645dd456
--- /dev/null
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderObject.java
@@ -0,0 +1,9 @@
+package de.hysky.skyblocker.skyblock.dungeon.puzzle.boulder;
+
+import net.minecraft.util.math.BlockPos;
+
+public record BoulderObject(int x, int y, int z, String type) {
+    public BlockPos get3DPosition() {
+        return new BlockPos(x, y, z);
+    }
+}
diff --git a/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderSolver.java b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderSolver.java
new file mode 100644
index 00000000..f407ce8a
--- /dev/null
+++ b/src/main/java/de/hysky/skyblocker/skyblock/dungeon/puzzle/boulder/BoulderSolver.java
@@ -0,0 +1,202 @@
+package de.hysky.skyblocker.skyblock.dungeon.puzzle.boulder;
+
+import java.util.ArrayList;
+import java.util.Arrays;
+import java.util.Comparator;
+import java.util.HashSet;
+import java.util.List;
+import java.util.PriorityQueue;
+import java.util.Set;
+import it.unimi.dsi.fastutil.Pair;
+
+/**
+ * A utility class that provides methods to solve the Boulder puzzle using the A* search algorithm.
+ * The BoulderSolver class is responsible for finding the shortest path from the starting position
+ * to the target position by exploring possible moves and evaluating their costs.
+ */
+public class BoulderSolver {
+
+    /**
+     * Finds the shortest path to solve the Boulder puzzle using the A* search algorithm.
+     *
+     * @param initialStates The list of initial game states from which to start the search.
+     * @return A list of coordinates representing the shortest path to solve the puzzle,
+     *         or null if no solution is found within the maximum number of iterations.
+     */
+    public static List<int[]> aStarSolve(List<GameState> initialStates) {
+        Set<GameState> visited = new HashSet<>();
+        PriorityQueue<Pair<GameState, List<int[]>>> queue = new PriorityQueue<>(new AStarComparator());
+
+        for (GameState initialState : initialStates) {
+            queue.add(Pair.of(initialState, new ArrayList<>()));
+        }
+
+        int maxIterations = 10000;
+        int iterations = 0;
+
+        while (!queue.isEmpty() && iterations < maxIterations) {
+            Pair<GameState, List<int[]>> pair = queue.poll();
+            GameState state = pair.left();
+            List<int[]> path = pair.right();
+
+            if (state.isSolved()) {
+                return path;
+            }
+
+            if (visited.contains(state)) {
+                continue;
+            }
+            visited.add(state);
+
+            int[] currentCoord = {state.playerX, state.playerY};
+            path.add(currentCoord);
+
+            for (int[] direction : new int[][]{{-1, 0}, {0, -1}, {0, 1}, {1, 0}}) {
+                GameState newState = new GameState(state.grid, state.playerX, state.playerY);
+                if (newState.movePlayer(direction[0], direction[1])) {
+                    queue.add(Pair.of(newState, new ArrayList<>(path)));
+                }
+            }
+            iterations++;
+        }
+
+        return null;
+    }
+
+    /**
+     * A comparator used to compare game states based on their A* search cost.
+     * States with lower costs are prioritized for exploration.
+     */
+    private static class AStarComparator implements Comparator<Pair<GameState, List<int[]>>> {
+        /**
+         * Compares two pairs of game states and their associated paths based on their costs.
+         *
+         * @param a The first pair to compare.
+         * @param b The second pair to compare.
+         * @return A negative integer if a has a lower cost than b,
+         *         a positive integer if a has a higher cost than b,
+         *         or zero if both have the same cost.
+         */
+        @Override
+        public int compare(Pair<GameState, List<int[]>> a, Pair<GameState, List<int[]>> b) {
+            int costA = a.right().size() + a.left().heuristic();
+            int costB = b.right().size() + b.left().heuristic();
+            return Integer.compare(costA, costB);
+        }
+    }
+
+    /**
+     * Represents the game state for the Boulder puzzle, including the current grid configuration
+     * and the position of the theoretical player.
+     */
+    public static class GameState {
+        private final char[][] grid;
+        private int playerX;
+        private int playerY;
+
+        /**
+         * Constructs a new game state with the specified grid and theoretical player position.
+         *
+         * @param grid     The grid representing the Boulder puzzle configuration.
+         * @param playerX  The x-coordinate of the player's position.
+         * @param playerY  The y-coordinate of the player's position.
+         */
+        public GameState(char[][] grid, int playerX, int playerY) {
+            this.grid = copyGrid(grid);
+            this.playerX = playerX;
+            this.playerY = playerY;
+        }
+
+        @Override
+        public boolean equals(Object obj) {
+            if (this == obj) return true;
+            if (obj == null || getClass() != obj.getClass()) return false;
+            GameState gameState = (GameState) obj;
+            return Arrays.deepEquals(grid, gameState.grid) && playerX == gameState.playerX && playerY == gameState.playerY;
+        }
+
+        @Override
+        public int hashCode() {
+            int result = Arrays.deepHashCode(grid);
+            result = 31 * result + playerX;
+            result = 31 * result + playerY;
+            return result;
+        }
+
+        /**
+         * Moves the theoretical player in the specified direction and updates the game state accordingly.
+         *
+         * @param dx The change in x-coordinate (horizontal movement).
+         * @param dy The change in y-coordinate (vertical movement).
+         * @return true if the move is valid and the player is moved, false otherwise.
+         */
+        public boolean movePlayer(int dx, int dy) {
+            int newX = playerX + dx;
+            int newY = playerY + dy;
+
+            if (isValidPosition(newX, newY)) {
+                if (grid[newX][newY] == 'B') {
+                    int nextToBoxX = newX + dx;
+                    int nextToBoxY = newY + dy;
+                    if (isValidPosition(nextToBoxX, nextToBoxY) && grid[nextToBoxX][nextToBoxY] == '.') {
+                        grid[newX][newY] = '.';
+                        grid[nextToBoxX][nextToBoxY] = 'B';
+                        playerX = newX;
+                        playerY = newY;
+                        return true;
+                    }
+                } else {
+                    playerX = newX;
+                    playerY = newY;
+                    return true;
+                }
+            }
+            return false;
+        }
+
+        private boolean isValidPosition(int x, int y) {
+            return x >= 0 && y >= 0 && x < grid.length && y < grid[0].length;
+        }
+
+        /**
+         * Checks if the puzzle is solved, i.e., if the player is positioned on the target BoulderObject.
+         *
+         * @return true if the theoretical puzzle is solved, false otherwise.
+         */
+        public boolean isSolved() {
+            return grid[playerX][playerY] == 'T';
+        }
+
+        /**
+         * Calculates the heuristic value for the current game state, representing the estimated
+         * distance from the player's position to the target BoulderObject.
+         *
+         * @return The heuristic value for the current game state.
+         */
+        public int heuristic() {
+            // should be improved maybe prioritize empty path first
+            for (int i = 0; i < grid.length; i++) {
+                for (int j = 0; j < grid[0].length; j++) {
+                    if (grid[i][j] == 'T') {
+                        return Math.abs(playerX - i) + Math.abs(playerY - j);
+                    }
+                }
+            }
+            return Integer.MAX_VALUE;
+        }
+
+        /**
+         * Creates a deep copy of the grid array to avoid modifying the original grid.
+         *
+         * @param original The original grid array to copy.
+         * @return A deep copy of the original grid array.
+         */
+        private char[][] copyGrid(char[][] original) {
+            char[][] copy = new char[original.length][];
+            for (int i = 0; i < original.length; i++) {
+                copy[i] = original[i].clone();
+            }
+            return copy;
+        }
+    }
+}
diff --git a/src/main/resources/assets/skyblocker/lang/en_us.json b/src/main/resources/assets/skyblocker/lang/en_us.json
index 4eb3573b..6c6f22a9 100644
--- a/src/main/resources/assets/skyblocker/lang/en_us.json
+++ b/src/main/resources/assets/skyblocker/lang/en_us.json
@@ -267,6 +267,8 @@
   "text.autoconfig.skyblocker.option.locations.dungeons.solveTicTacToe.@Tooltip": "Puts a red box around the next best move for you to make!",
   "text.autoconfig.skyblocker.option.locations.dungeons.solveWaterboard": "Solve Waterboard Puzzle",
   "text.autoconfig.skyblocker.option.locations.dungeons.solveWaterboard.@Tooltip": "Click the levers with green boxes to solve the puzzle.",
+  "text.autoconfig.skyblocker.option.locations.dungeons.solveBoulder": "Solve Boulder Puzzle",
+  "text.autoconfig.skyblocker.option.locations.dungeons.solveBoulder.@Tooltip": "Draws a line to the chest and highlight button",
   "text.autoconfig.skyblocker.option.locations.dungeons.mimicMessage": "Mimic Message",
   "text.autoconfig.skyblocker.option.locations.dungeons.mimicMessage.sendMimicMessage": "Enable Mimic Message",
   "text.autoconfig.skyblocker.option.locations.dungeons.mimicMessage.sendMimicMessage.@Tooltip": "Sends a message in chat upon killing a mimic for other players' score calculation mods.",
@@ -403,6 +405,7 @@
   "skyblocker.dungeons.secrets.customWaypointRemoved": "§rRemoved custom waypoint at X: %d, Y: %d, Z: %d for room %s secret #%d of category %s with name '%s'.",
   "skyblocker.dungeons.secrets.customWaypointNotFound": "§cNo custom waypoint found at X: %d, Y: %d, Z: %d for room %s.",
   "skyblocker.dungeons.dungeonScore.scoreText": "Score: %s",
+  "skyblocker.dungeons.puzzle.boulder.noSolution": "No solution found!",
   
   "skyblocker.dungeons.secretsTracker.feedback": "%s§f found %s§f secrets. %s",
   "skyblocker.dungeons.secretsTracker.failFeedback": "§cUnable to calculate the amount of secrets everybody did this run!",