- Project separation

6 files changed, 1114 insertions, 0 deletions

diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java
new file mode 100644
index 00000000..ee71f90b
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java
@@ -0,0 +1,189 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom;
+import lombok.Data;
+import lombok.EqualsAndHashCode;
+import lombok.Getter;
+import lombok.RequiredArgsConstructor;
+import net.minecraft.util.*;
+import net.minecraft.world.World;
+
+import java.util.*;
+
+public class AStarCornerCut {
+    private final BlockPos min, max;
+    private final World world;
+
+    int lastSx, lastSy, lastSz;
+    final int dx, dy, dz;
+    private DungeonRoom dungeonRoom;
+
+    @Getter
+    private AxisAlignedBB destinationBB;
+
+    public AStarCornerCut(DungeonRoom dungeonRoom, Vec3 destination) {
+        this.min = new BlockPos(dungeonRoom.getMinx(), 0, dungeonRoom.getMinz());
+        this.max = new BlockPos(dungeonRoom.getMaxx(), 255, dungeonRoom.getMaxz());
+
+        this.world = dungeonRoom.getCachedWorld();
+        this.dungeonRoom = dungeonRoom;
+
+        this.dx = (int) (destination.xCoord * 2);
+        this.dy = (int) (destination.yCoord * 2);
+        this.dz = (int) (destination.zCoord * 2);
+        destinationBB = AxisAlignedBB.fromBounds(dx-2, dy-2, dz-2, dx+2, dy+2, dz+2);
+    }
+
+    private Map<Node.Coordinate, Node> nodeMap = new HashMap<>();
+
+    private Node openNode(int x, int y, int z)
+    {
+        Node.Coordinate coordinate = new Node.Coordinate(x,y,z);
+        Node node = this.nodeMap.get(coordinate);
+
+        if (node == null)
+        {
+            node = new Node(coordinate);
+            this.nodeMap.put(coordinate, node);
+        }
+
+        return node;
+    }
+
+    @Getter
+    private LinkedList<Vec3> route = new LinkedList<>();
+
+    @Getter
+    private PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing((Node a) -> a == null ? Float.MAX_VALUE : a.f).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.x).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.y).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.z));
+
+    private int pfindIdx = 0;
+
+    public boolean pathfind(Vec3 from, long timeout) {
+        pfindIdx ++;
+        if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2))
+            open.clear();
+
+        this.lastSx = (int) Math.round(from.xCoord * 2);
+        this.lastSy = (int) Math.round(from.yCoord * 2);
+        this.lastSz = (int) Math.round(from.zCoord * 2);
+
+        Node startNode = openNode(dx, dy, dz);
+        Node goalNode = openNode(lastSx, lastSy, lastSz);
+
+        if (goalNode.parent != null) {
+            LinkedList<Vec3> route = new LinkedList<>();
+            Node curr =goalNode;
+            while(curr.parent != null) {
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                curr = curr.parent;
+            }
+            route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+            this.route = route;
+            return true;
+        }
+
+        startNode.g = 0;
+        startNode.f = 0;
+        goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE;
+
+
+        open.add(startNode);
+
+        long end = System.currentTimeMillis() + timeout;
+
+        while (!open.isEmpty()) {
+            if (System.currentTimeMillis() > end) {
+                return false;
+            }
+
+            Node n = open.poll();
+            if (n.lastVisited == pfindIdx) continue;
+            n.lastVisited = pfindIdx;
+
+            if (n == goalNode) {
+                // route = reconstructPath(startNode)
+                LinkedList<Vec3> route = new LinkedList<>();
+                Node curr =goalNode;
+                while(curr.parent != null) {
+                    route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                    curr = curr.parent;
+                }
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                this.route = route;
+                return true;
+            }
+
+            for (int z = -1; z <= 1; z++) {for (int y = -1; y <= 1; y ++) { for(int x = -1; x <= 1; x++) {
+                if (x == 0 && y == 0 && z == 0) continue;
+                Node neighbor = openNode(n.coordinate.x +x, n.coordinate.y +y, n.coordinate.z + z);
+
+                // check blocked.
+                if (!((destinationBB.minX <= neighbor.coordinate.x && neighbor.coordinate.x <= destinationBB.maxX &&
+                        destinationBB.minY <= neighbor.coordinate.y && neighbor.coordinate.y <= destinationBB.maxY &&
+                        destinationBB.minZ <= neighbor.coordinate.z && neighbor.coordinate.z <= destinationBB.maxZ) // near destination
+                 || !dungeonRoom.isBlocked(neighbor.coordinate.x, neighbor.coordinate.y, neighbor.coordinate.z))) { // not blocked
+                    continue;
+                }
+                if (neighbor.lastVisited == pfindIdx) continue;
+
+
+                float gScore = n.g + MathHelper.sqrt_float(x*x + y*y + z*z); // altho it's sq, it should be fine
+                if (gScore < neighbor.g ) {
+                    neighbor.parent = n;
+                    neighbor.g = gScore;
+                    neighbor.f = gScore + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                    open.add(neighbor);
+                } else if (neighbor.lastVisited != pfindIdx) {
+                    neighbor.f = gScore + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                    open.add(neighbor);
+                }
+            }}}
+        }
+        return true;
+    }
+
+    private int manhatten(int x, int y, int z) {return Math.abs(x)+ Math.abs(y)+ Math.abs(z);}
+    private float distSq(float x, float y, float z) {
+        return MathHelper.sqrt_float(x * x + y * y + z * z);
+    }
+
+    @RequiredArgsConstructor
+    @Data
+    public static final class Node {
+        @Data
+        @RequiredArgsConstructor
+        public static final class Coordinate {
+            private final int x, y, z;
+        }
+        private final Coordinate coordinate;
+
+        private float f = Float.MAX_VALUE, g = Float.MAX_VALUE;
+        private int lastVisited;
+
+        @EqualsAndHashCode.Exclude
+        private Node parent;
+
+        public static long makeHash(int x, int y, int z)
+        {
+            return y & 32767L | ((short)x & 32767L) << 16 | ((short)z & 32767L) << 32;
+        }
+    }
+}
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java
new file mode 100644
index 00000000..94fa8a87
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java
@@ -0,0 +1,182 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom;
+import lombok.Data;
+import lombok.EqualsAndHashCode;
+import lombok.Getter;
+import lombok.RequiredArgsConstructor;
+import net.minecraft.util.*;
+import net.minecraft.world.World;
+
+import java.util.*;
+
+public class AStarFineGrid {
+    private final BlockPos min, max;
+    private final World world;
+
+    int lastSx, lastSy, lastSz;
+    final int dx, dy, dz;
+    private DungeonRoom dungeonRoom;
+
+    @Getter
+    private AxisAlignedBB destinationBB;
+
+    public AStarFineGrid(DungeonRoom dungeonRoom, Vec3 destination) {
+        this.min = new BlockPos(dungeonRoom.getMinx(), 0, dungeonRoom.getMinz());
+        this.max = new BlockPos(dungeonRoom.getMaxx(), 255, dungeonRoom.getMaxz());
+
+        this.world = dungeonRoom.getCachedWorld();
+        this.dungeonRoom = dungeonRoom;
+
+        this.dx = (int) (destination.xCoord * 2);
+        this.dy = (int) (destination.yCoord * 2);
+        this.dz = (int) (destination.zCoord * 2);
+        destinationBB = AxisAlignedBB.fromBounds(dx-2, dy-2, dz-2, dx+2, dy+2, dz+2);
+    }
+
+    private Map<Node.Coordinate, Node> nodeMap = new HashMap<>();
+
+    private Node openNode(int x, int y, int z)
+    {
+        Node.Coordinate coordinate = new Node.Coordinate(x,y,z);
+        Node node = this.nodeMap.get(coordinate);
+
+        if (node == null)
+        {
+            node = new Node(coordinate);
+            this.nodeMap.put(coordinate, node);
+        }
+
+        return node;
+    }
+
+    @Getter
+    private LinkedList<Vec3> route = new LinkedList<>();
+
+    @Getter
+    private PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing((Node a) -> a == null ? Float.MAX_VALUE : a.f).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.x).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.y).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.z));
+
+    private int pfindIdx = 0;
+
+    public boolean pathfind(Vec3 from, long timeout) {
+        pfindIdx ++;
+        if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2))
+            open.clear();
+
+        this.lastSx = (int) Math.round(from.xCoord * 2);
+        this.lastSy = (int) Math.round(from.yCoord * 2);
+        this.lastSz = (int) Math.round(from.zCoord * 2);
+
+        Node startNode = openNode(dx, dy, dz);
+        Node goalNode = openNode(lastSx, lastSy, lastSz);
+        startNode.g = 0;
+        startNode.f = 0;
+        goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE;
+        if (goalNode.parent != null) {
+            LinkedList<Vec3> route = new LinkedList<>();
+            Node curr =goalNode;
+            while(curr.parent != null) {
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                curr = curr.parent;
+            }
+            route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+            this.route = route;
+            return true;
+        }
+        open.add(startNode);
+
+        long end = System.currentTimeMillis() + timeout;
+
+        while (!open.isEmpty()) {
+            if (System.currentTimeMillis() > end) {
+                return false;
+            }
+
+            Node n = open.poll();
+            if (n.lastVisited == pfindIdx) continue;
+            n.lastVisited = pfindIdx;
+
+            if (n == goalNode) {
+                // route = reconstructPath(startNode)
+                LinkedList<Vec3> route = new LinkedList<>();
+                Node curr =goalNode;
+                while(curr.parent != null) {
+                    route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                    curr = curr.parent;
+                }
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                this.route = route;
+                return true;
+            }
+
+            for (EnumFacing value : EnumFacing.VALUES) {
+                Node neighbor = openNode(n.coordinate.x + value.getFrontOffsetX(), n.coordinate.y + value.getFrontOffsetY(), n.coordinate.z + value.getFrontOffsetZ());
+
+                // check blocked.
+                if (!((destinationBB.minX <= neighbor.coordinate.x && neighbor.coordinate.x <= destinationBB.maxX &&
+                        destinationBB.minY <= neighbor.coordinate.y && neighbor.coordinate.y <= destinationBB.maxY &&
+                        destinationBB.minZ <= neighbor.coordinate.z && neighbor.coordinate.z <= destinationBB.maxZ) // near destination
+                 || !dungeonRoom.isBlocked(neighbor.coordinate.x, neighbor.coordinate.y, neighbor.coordinate.z))) { // not blocked
+                    continue;
+                }
+
+                float gScore = n.g + 1; // altho it's sq, it should be fine
+                if (gScore < neighbor.g) {
+                    neighbor.parent = n;
+                    neighbor.g = gScore;
+                    neighbor.f = gScore + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                    open.add(neighbor);
+                } else if (neighbor.lastVisited != pfindIdx) {
+                    neighbor.f = gScore + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                    open.add(neighbor);
+                }
+            }
+        }
+        return true;
+    }
+
+    private int manhatten(int x, int y, int z) {return Math.abs(x)+ Math.abs(y)+ Math.abs(z);}
+    private float distSq(float x, float y, float z) {
+        return MathHelper.sqrt_float(x * x + y * y + z * z);
+    }
+
+    @RequiredArgsConstructor
+    @Data
+    public static final class Node {
+        @Data
+        @RequiredArgsConstructor
+        public static final class Coordinate {
+            private final int x, y, z;
+        }
+        private final Coordinate coordinate;
+
+        private float f = Float.MAX_VALUE, g = Float.MAX_VALUE;
+        private int lastVisited;
+
+        @EqualsAndHashCode.Exclude
+        private Node parent;
+
+        public static long makeHash(int x, int y, int z)
+        {
+            return y & 32767L | ((short)x & 32767L) << 16 | ((short)z & 32767L) << 32;
+        }
+    }
+}
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/CachedWorld.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/CachedWorld.java
new file mode 100644
index 00000000..1291f794
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/CachedWorld.java
@@ -0,0 +1,85 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import net.minecraft.block.state.IBlockState;
+import net.minecraft.tileentity.TileEntity;
+import net.minecraft.util.BlockPos;
+import net.minecraft.util.EnumFacing;
+import net.minecraft.world.*;
+import net.minecraft.world.chunk.IChunkProvider;
+
+public class CachedWorld extends World {
+    private ChunkCache chunkCache;
+
+    public CachedWorld(ChunkCache chunkCache) {
+        super(null, null, new WorldProviderSurface(), null, true);
+        this.chunkCache = chunkCache;
+    }
+
+    @Override
+    protected IChunkProvider createChunkProvider() {
+        return null;
+    }
+
+    @Override
+    protected int getRenderDistanceChunks() {
+        return 999;
+    }
+
+    @Override
+    public boolean extendedLevelsInChunkCache() {
+        return chunkCache.extendedLevelsInChunkCache();
+    }
+
+    @Override
+    public TileEntity getTileEntity(BlockPos pos) {
+        return chunkCache.getTileEntity(pos);
+    }
+
+    @Override
+    public int getCombinedLight(BlockPos pos, int lightValue) {
+        return chunkCache.getCombinedLight(pos, lightValue);
+    }
+
+    @Override
+    public IBlockState getBlockState(BlockPos pos) {
+        return chunkCache.getBlockState(pos);
+    }
+
+    @Override
+    public int getLightFor(EnumSkyBlock type, BlockPos pos) {
+        return chunkCache.getLightFor(type, pos);
+    }
+
+    @Override
+    public boolean isAirBlock(BlockPos pos) {
+        return chunkCache.isAirBlock(pos);
+    }
+
+    @Override
+    public int getStrongPower(BlockPos pos, EnumFacing direction) {
+        return chunkCache.getStrongPower(pos, direction);
+    }
+
+    @Override
+    public boolean isSideSolid(BlockPos pos, EnumFacing side, boolean _default) {
+        return chunkCache.isSideSolid(pos, side, _default);
+    }
+}
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java
new file mode 100644
index 00000000..12aa1828
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java
@@ -0,0 +1,306 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom;
+import lombok.Data;
+import lombok.EqualsAndHashCode;
+import lombok.Getter;
+import lombok.RequiredArgsConstructor;
+import net.minecraft.util.*;
+import net.minecraft.world.World;
+
+import java.util.*;
+
+public class JPSPathfinder {
+    private final BlockPos min, max;
+    private final World world;
+
+    private Vec3 start;
+    private Vec3 destination;
+    private DungeonRoom dungeonRoom;
+
+    @Getter
+    private AxisAlignedBB destinationBB;
+
+    public JPSPathfinder(DungeonRoom dungeonRoom){
+        this.min = new BlockPos(dungeonRoom.getMinx(), 0, dungeonRoom.getMinz());
+        this.max = new BlockPos(dungeonRoom.getMaxx(), 255, dungeonRoom.getMaxz());
+
+        this.world = dungeonRoom.getCachedWorld();
+        this.dungeonRoom = dungeonRoom;
+    }
+
+    private IntHashMap<Node> nodeMap = new IntHashMap();
+
+    private Node openNode(int x, int y, int z)
+    {
+        int i = Node.makeHash(x, y, z);
+        Node node = this.nodeMap.lookup(i);
+
+        if (node == null)
+        {
+            node = new Node(x, y, z);
+            this.nodeMap.addKey(i, node);
+        }
+
+        return node;
+    }
+
+    @Getter
+    private LinkedList<Vec3> route = new LinkedList<>();
+
+    @Getter
+    private PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing((Node a) -> a == null ? Float.MAX_VALUE : a.f).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.x).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.y).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.z));
+
+    private int tx, ty, tz;
+
+    private Node addNode(Node parent, Node jumpPt, boolean addToOpen) {
+        float ng = parent.g + distSq(jumpPt.x - parent.x, jumpPt.y - parent.y, jumpPt.z - parent.z);
+
+        if (ng < jumpPt.g) {
+            if (addToOpen)
+            open.remove(jumpPt);
+            jumpPt.g = ng;
+            jumpPt.h = jumpPt.h == -1 ? distSq(tx - jumpPt.x, ty - jumpPt.y, tz - jumpPt.z) : jumpPt.h;
+            jumpPt.f = jumpPt.h + jumpPt.g;
+            jumpPt.parent = parent;
+            if (addToOpen)
+            open.add(jumpPt);
+        }
+        return jumpPt;
+    }
+
+
+    long arr[];
+
+    public boolean pathfind(Vec3 from, Vec3 to, float within, long timeout) {
+        route.clear(); nodeMap.clearMap();
+
+        {
+            from = new Vec3(((int)(from.xCoord * 2)) / 2.0, ((int)(from.yCoord * 2)) / 2.0, ((int)(from.zCoord* 2)) / 2.0);
+            to = new Vec3(((int)(to.xCoord * 2)) / 2.0, ((int)(to.yCoord * 2)) / 2.0, ((int)(to.zCoord* 2)) / 2.0);
+        }
+
+        this.start = from; this.destination = to;
+        tx = (int)(to.xCoord * 2);
+        ty = (int)(to.yCoord * 2);
+        tz = (int)(to.zCoord * 2);
+
+        destinationBB = AxisAlignedBB.fromBounds((to.xCoord - within)* 2, (to.yCoord - within) * 2, (to.zCoord - within) * 2, (to.xCoord + within) * 2, (to.yCoord + within)* 2, (to.zCoord + within) *2);
+        open.clear();
+        Node start;
+        open.add(start = openNode((int)from.xCoord * 2 + 1, (int)from.yCoord * 2, (int)from.zCoord * 2+1));
+        start.g = 0; start.f = 0; start.h = (float) from.squareDistanceTo(to);
+
+        Node end = null; float minDist = Float.MAX_VALUE;
+        long forceEnd = System.currentTimeMillis() + timeout + 999999999L;
+        while(!open.isEmpty()) {
+            if (forceEnd < System.currentTimeMillis() && timeout != -1) break;
+            Node n = open.poll();
+            n.closed= true;
+            if (minDist > n.h) {
+                minDist = n.h;
+                end = n;
+            }
+            if (n.x > destinationBB.minX && n.x < destinationBB.maxX && n.y > destinationBB.minY && n.y < destinationBB.maxY && n.z > destinationBB.minZ && n.z < destinationBB.maxZ) {
+                break;
+            }
+
+            for (Node neighbor : getNeighbors(n.parent == null ? n : n.parent, n)) {
+                Node jumpPT = expand(n.x, n.y, n.z, neighbor.x - n.x, neighbor.y - n.y, neighbor.z - n.z);
+                if (jumpPT == null || jumpPT.closed) continue;
+
+                addNode(n, jumpPT, true);
+            }
+        }
+
+        if (end == null) return false;
+        Node p = end;
+        while (p != null) {
+            route.addLast(new Vec3(p.x / 2.0f, p.y / 2.0f + 0.1, p.z / 2.0f));
+            p = p.parent;
+        }
+
+
+        return true;
+    }
+
+    private float distSq(float x, float y, float z) {
+        return MathHelper.sqrt_float(x * x + y * y + z * z);
+    }
+
+    public Set<Node> getNeighbors(Node prevN, Node n) {
+//        if (true) throw new RuntimeException("ah");
+        int dx = MathHelper.clamp_int(n.x - prevN.x, -1, 1);
+        int dy = MathHelper.clamp_int(n.y - prevN.y, -1, 1);
+        int dz = MathHelper.clamp_int(n.z - prevN.z, -1, 1);
+        int x = n.x, y = n.y, z = n.z;
+        int nx = n.x + dx, ny = n.y + dy, nz = n.z + dz;
+
+        Set<Node> nexts = new HashSet<>();
+        int determinant = Math.abs(dx) + Math.abs(dy) + Math.abs(dz);
+        if (determinant == 0) {
+            for (int i = -1; i <= 1; i++)
+                for (int j = -1; j <= 1; j++)
+                    for (int k = -1; k <= 1; k++) {
+                        if (i == 0 && j == 0 && k == 0) continue;
+                        nexts.add(openNode(x+i, y+j, z+k));
+                    }
+        } else if (determinant == 1) {
+            nexts.add(openNode(nx,ny,nz));
+            for (int i = -1; i<=1; i++) {
+                for (int j = - 1; j<=1; j++) {
+                    if (i == 0 && j == 0) continue;
+                    if (dx != 0 && dungeonRoom.isBlocked(x, y + i, z + j)) nexts.add(openNode(nx,y+i,z+j));
+                    if (dy != 0 && dungeonRoom.isBlocked(x + i, y, z + j)) nexts.add(openNode(x+i,ny,z+j));
+                    if (dz != 0 && dungeonRoom.isBlocked(x + i, y + j, z)) nexts.add(openNode(x+i,y+j,nz));
+                }
+            }
+        } else if (determinant == 2) {
+            if (dz != 0) nexts.add(openNode(x,y,nz));
+            if (dy != 0) nexts.add(openNode(x,ny,z));
+            if (dx != 0) nexts.add(openNode(nx,y,z));
+            nexts.add(openNode(nx,ny,nz));
+            if (dx == 0) {
+                if (dungeonRoom.isBlocked(x, y, z-dz)) {
+                    nexts.add(openNode(x, ny, z-dz));
+                    if (dungeonRoom.isBlocked(x+1, y, z-dz)) nexts.add(openNode(x+1, ny, z-dz));
+                    if (dungeonRoom.isBlocked(x-1, y, z-dz)) nexts.add(openNode(x-1, ny, z-dz));
+                }
+                if (dungeonRoom.isBlocked(x, y-dy, z)) {
+                    nexts.add(openNode(x, y-dy, nz));
+                    if (dungeonRoom.isBlocked(x+1, y-dy, z)) nexts.add(openNode(x+1, y-dy, nz));
+                    if (dungeonRoom.isBlocked(x-1, y-dy, z)) nexts.add(openNode(x+1, y-dy, nz));
+                }
+            } else if (dy == 0) {
+                if (dungeonRoom.isBlocked(x, y, z-dz)) {
+                    nexts.add(openNode(nx, y, z-dz));
+                    if (dungeonRoom.isBlocked(x, y+1, z-dz)) nexts.add(openNode(nx, y+1, z-dz));
+                    if (dungeonRoom.isBlocked(x, y-1, z-dz)) nexts.add(openNode(nx, y-1, z-dz));
+                }
+                if (dungeonRoom.isBlocked(x-dx, y, z)) {
+                    nexts.add(openNode(x-dx, y, nz));
+                    if (dungeonRoom.isBlocked(x-dx, y+1, z)) nexts.add(openNode(x-dx, y+1, nz));
+                    if (dungeonRoom.isBlocked(x-dx, y-1, z)) nexts.add(openNode(x-dx, y-1, nz));
+                }
+            } else if (dz == 0) {
+                if (dungeonRoom.isBlocked(x, y-dy, z)) {
+                    nexts.add(openNode(nx, y-dy, z));
+                    if (dungeonRoom.isBlocked(x, y-dy, z+1)) nexts.add(openNode(nx, y-dy, z+1));
+                    if (dungeonRoom.isBlocked(x, y-dy, z-1)) nexts.add(openNode(nx, y-dy, z-1));
+                }
+                if (dungeonRoom.isBlocked(x-dx, y, z)) {
+                    nexts.add(openNode(x-dx, ny, z));
+                    if (dungeonRoom.isBlocked(x-dx, y, z+1)) nexts.add(openNode(x-dx, ny, z+1));
+                    if (dungeonRoom.isBlocked(x-dx, y, z-1)) nexts.add(openNode(x-dx, ny, z-1));
+                }
+            }
+        } else if (determinant == 3) {
+            nexts.add(openNode(x,y,nz));
+            nexts.add(openNode(x,ny,z));
+            nexts.add(openNode(nx,y,z));
+            nexts.add(openNode(nx,y,nz));
+            nexts.add(openNode(x,ny,nz));
+            nexts.add(openNode(nx,ny,z));
+            nexts.add(openNode(nx,ny,nz));
+
+            if (dungeonRoom.isBlocked(x,y,z-dz)) {
+                nexts.add(openNode(x,ny,z-dz));
+                nexts.add(openNode(nx,ny,z-dz));
+                nexts.add(openNode(nx,y,z-dz));
+            }
+            if (dungeonRoom.isBlocked(x-dx,y,z)) {
+                nexts.add(openNode(x-dx,ny,nz));
+                nexts.add(openNode(x-dx,ny,z));
+                nexts.add(openNode(x-dx,y,nz));
+            }
+            if (dungeonRoom.isBlocked(x,y-dy,z)) {
+                nexts.add(openNode(x,y-dy,nz));
+                nexts.add(openNode(nx,y-dy,z));
+                nexts.add(openNode(nx,y-dy,nz));
+            }
+        }
+        return nexts;
+    }
+
+    public Node expand(int x, int y, int z, int dx, int dy, int dz) {
+        while(true) {
+            int nx =  x + dx, ny = y + dy, nz = z + dz;
+            if (dungeonRoom.isBlocked(nx, ny, nz)) return null;
+
+            if (nx > destinationBB.minX && nx < destinationBB.maxX && ny > destinationBB.minY && ny < destinationBB.maxY && nz > destinationBB.minZ && nz < destinationBB.maxZ) return openNode(nx,ny,nz);
+
+            int determinant = Math.abs(dx) + Math.abs(dy) + Math.abs(dz);
+            if (determinant == 1) {
+                for (int i = -1; i<=1; i++) {
+                    for (int j = - 1; j<=1; j++) {
+                        if (i == 0 && j == 0) continue;
+                        if (dx != 0 && dungeonRoom.isBlocked(nx, ny + i, nz + j) && !dungeonRoom.isBlocked(nx+dx, ny + i, nz + j)) return  openNode(nx,ny,nz);
+                        if (dy != 0 && dungeonRoom.isBlocked(nx + i, ny, nz + j) && !dungeonRoom.isBlocked(nx + i, ny+dy, nz + j)) return openNode(nx,ny,nz);
+                        if (dz != 0 && dungeonRoom.isBlocked(nx + i, ny + j , nz) && !dungeonRoom.isBlocked(nx + i, ny + j , nz+dz)) return openNode(nx,ny,nz);
+                    }
+                }
+            } else if (determinant == 2) {
+                for (EnumFacing value : EnumFacing.VALUES) {
+                    if (value.getFrontOffsetX() == dx || value.getFrontOffsetY() == dy || value.getFrontOffsetZ() == dz) continue;
+                    int tx = nx + value.getFrontOffsetX();
+                    int ty = ny + value.getFrontOffsetY();
+                    int tz = nz + value.getFrontOffsetZ();
+                    if (dungeonRoom.isBlocked(tx, ty, tz)) return openNode(nx, ny, nz);
+                }
+                if (dx != 0 &&  expand(nx, ny, nz, dx, 0,0) != null) return openNode(nx,ny,nz);
+                if (dy != 0 && expand(nx, ny, nz, 0, dy,0) != null) return openNode(nx,ny,nz);
+                if (dz != 0 && expand(nx, ny, nz, 0, 0,dz) != null) return openNode(nx,ny,nz);
+            } else if (determinant == 3) {
+                if (dungeonRoom.isBlocked(x, ny, nz ) || dungeonRoom.isBlocked(nx, y , nz) || dungeonRoom.isBlocked(nx, ny, z)) return openNode(nx,ny,nz);
+                if (expand(nx, ny, nz, dx, 0, 0) != null ||
+                        expand(nx, ny, nz, dx, dy, 0) != null ||
+                        expand(nx, ny, nz, dx, 0, dz) != null ||
+                        expand(nx, ny, nz, 0, dy, 0) != null ||
+                        expand(nx, ny, nz, 0, dy, dz) != null ||
+                        expand(nx, ny, nz, 0, 0, dz) != null) return openNode(nx,ny,nz);
+            }
+            x = nx; y = ny; z = nz;
+        }
+    }
+
+    @RequiredArgsConstructor
+    @Data
+    public static final class Node {
+        private final int x, y, z;
+
+        private float f, g = Float.MAX_VALUE, h = -1;
+        private boolean closed;
+
+        @EqualsAndHashCode.Exclude
+        private Node parent;
+
+        public static int makeHash(int x, int y, int z)
+        {
+            return y & 255 | (x & 32767) << 8 | (z & 32767) << 24 | (x < 0 ? Integer.MIN_VALUE : 0) | (z < 0 ? 32768 : 0);
+        }
+
+        public Node close() {
+            this.closed = true;
+            return this;
+        }
+
+    }
+}
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/NodeProcessorDungeonRoom.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/NodeProcessorDungeonRoom.java
new file mode 100644
index 00000000..d037c3a6
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/NodeProcessorDungeonRoom.java
@@ -0,0 +1,141 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import com.google.common.collect.Sets;
+import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom;
+import net.minecraft.block.Block;
+import net.minecraft.block.state.IBlockState;
+import net.minecraft.entity.Entity;
+import net.minecraft.init.Blocks;
+import net.minecraft.pathfinding.PathPoint;
+import net.minecraft.util.BlockPos;
+import net.minecraft.util.EnumFacing;
+import net.minecraft.util.Vec3i;
+import net.minecraft.world.pathfinder.NodeProcessor;
+
+import java.util.Set;
+
+public class NodeProcessorDungeonRoom extends NodeProcessor {
+    private final DungeonRoom dungeonRoom;
+    private final BlockPos sub;
+    public NodeProcessorDungeonRoom(DungeonRoom dungeonRoom) {
+        this.dungeonRoom = dungeonRoom;
+        sub = dungeonRoom.getMax().subtract(dungeonRoom.getMin());
+    }
+
+    @Override
+    public PathPoint getPathPointTo(Entity entityIn) {
+        return openPoint((int)entityIn.posX - dungeonRoom.getMin().getX(), (int)entityIn.posY - dungeonRoom.getMin().getY(),
+                (int)entityIn.posZ - dungeonRoom.getMin().getZ());
+    }
+
+    @Override
+    public PathPoint getPathPointToCoords(Entity entityIn, double x, double y, double z) {
+        return openPoint((int)x- dungeonRoom.getMin().getX(), (int)y - dungeonRoom.getMin().getY(),
+                (int)z - dungeonRoom.getMin().getZ());
+    }
+
+    private static final EnumFacing[] values2 = new EnumFacing[6];
+    static {
+        values2[0] = EnumFacing.DOWN;
+        values2[1] = EnumFacing.NORTH;
+        values2[2] = EnumFacing.SOUTH;
+        values2[3] = EnumFacing.EAST;
+        values2[4] = EnumFacing.WEST;
+        values2[5] = EnumFacing.UP;
+    }
+
+    @Override
+    public int findPathOptions(PathPoint[] pathOptions, Entity entityIn, PathPoint currentPoint, PathPoint targetPoint, float maxDistance) {
+
+        int i = 0;
+        for (EnumFacing ef:values2) {
+            Vec3i dir = ef.getDirectionVec();
+            int newX = currentPoint.xCoord + dir.getX();
+            int newY = currentPoint.yCoord + dir.getY();
+            int newZ = currentPoint.zCoord + dir.getZ();
+            if (newX < 0 || newZ < 0) continue;
+            if (newX > sub.getX()|| newZ > sub.getZ()) continue;
+            IBlockState curr = entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY, newZ));
+            IBlockState up = entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY + 1, newZ));
+            if (isValidBlock(curr)
+                && isValidBlock(up )) {
+                PathPoint pt = openPoint(newX, newY, newZ);
+                if (pt.visited) continue;
+                pathOptions[i++] = pt;
+                continue;
+            }
+
+            if (curr.getBlock() == Blocks.air) {
+                if (up.getBlock() == Blocks.stone_slab
+                || up.getBlock() == Blocks.wooden_slab
+                || up.getBlock() == Blocks.stone_slab2) {
+                    IBlockState up2 = entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY -1, newZ));
+                    if (up2.getBlock() == Blocks.stone_slab
+                                || up2.getBlock() == Blocks.wooden_slab
+                                || up2.getBlock() == Blocks.stone_slab2) {
+                        PathPoint pt = openPoint(newX, newY, newZ);
+                        if (pt.visited) continue;
+                        pathOptions[i++] = pt;
+                        continue;
+                    }
+                }
+            }
+
+            if (dir.getY() == 0 && curr.getBlock() == Blocks.iron_bars && up.getBlock() == Blocks.air &&
+                entityIn.getEntityWorld().getBlockState(new BlockPos(currentPoint.xCoord, currentPoint.yCoord, currentPoint.zCoord)).getBlock() != Blocks.iron_bars) {
+                boolean theFlag = false;
+                if (dir.getZ() == 0) {
+                    if (entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY, newZ)
+                            .add(0,0,1)).getBlock() == Blocks.air) {
+                        theFlag = true;
+                    } else if (entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY, newZ)
+                            .add(0,0,-1)).getBlock() == Blocks.air) {
+                        theFlag = true;
+                    }
+                } else if (dir.getX() == 0) {
+                    if (entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY, newZ)
+                            .add(-1,0,0)).getBlock() == Blocks.air) {
+                        theFlag = true;
+                    } else if (entityIn.getEntityWorld().getBlockState(dungeonRoom.getMin().add(newX, newY, newZ)
+                            .add(1,0,0)).getBlock() == Blocks.air) {
+                        theFlag = true;
+                    }
+                }
+                if (theFlag) {
+                    PathPoint pt = openPoint(newX, newY, newZ);
+                    if (pt.visited) continue;
+                    pathOptions[i++] = pt;
+                    continue;
+                }
+            }
+        }
+        return i;
+    }
+
+    public static final Set<Block> allowed = Sets.newHashSet(Blocks.air, Blocks.water, Blocks.lava, Blocks.flowing_water, Blocks.flowing_lava, Blocks.vine, Blocks.ladder
+    , Blocks.standing_sign, Blocks.wall_sign, Blocks.trapdoor, Blocks.iron_trapdoor, Blocks.wooden_button, Blocks.stone_button, Blocks.fire,
+            Blocks.torch, Blocks.rail, Blocks.golden_rail, Blocks.activator_rail, Blocks.detector_rail, Blocks.carpet, Blocks.redstone_torch);
+    public static final IBlockState preBuilt = Blocks.stone.getStateFromMeta(2);
+    public static boolean isValidBlock(IBlockState state) {
+        Block b = state.getBlock();
+        return state.equals(preBuilt) || allowed.contains(b);
+    }
+}
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java
new file mode 100644
index 00000000..032223f0
--- /dev/null
+++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java
@@ -0,0 +1,211 @@
+/*
+ * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod
+ * Copyright (C) 2021  cyoung06
+ *
+ * This program is free software: you can redistribute it and/or modify
+ * it under the terms of the GNU Affero General Public License as published
+ * by the Free Software Foundation, either version 3 of the License, or
+ * (at your option) any later version.
+ *
+ * This program is distributed in the hope that it will be useful,
+ * but WITHOUT ANY WARRANTY; without even the implied warranty of
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+ * GNU Affero General Public License for more details.
+ *
+ * You should have received a copy of the GNU Affero General Public License
+ * along with this program.  If not, see <https://www.gnu.org/licenses/>.
+ */
+
+package kr.syeyoung.dungeonsguide.pathfinding;
+
+import kr.syeyoung.dungeonsguide.dungeon.roomfinder.DungeonRoom;
+import lombok.*;
+import net.minecraft.util.*;
+import net.minecraft.world.World;
+
+import java.util.*;
+
+public class ThetaStar {
+    private final BlockPos min, max;
+    private final World world;
+
+    int lastSx, lastSy, lastSz;
+    final int dx, dy, dz;
+    private DungeonRoom dungeonRoom;
+
+    @Getter
+    private AxisAlignedBB destinationBB;
+
+    public ThetaStar(DungeonRoom dungeonRoom, Vec3 destination) {
+        this.min = new BlockPos(dungeonRoom.getMinx(), 0, dungeonRoom.getMinz());
+        this.max = new BlockPos(dungeonRoom.getMaxx(), 255, dungeonRoom.getMaxz());
+
+        this.world = dungeonRoom.getCachedWorld();
+        this.dungeonRoom = dungeonRoom;
+
+        this.dx = (int) (destination.xCoord * 2);
+        this.dy = (int) (destination.yCoord * 2);
+        this.dz = (int) (destination.zCoord * 2);
+        destinationBB = AxisAlignedBB.fromBounds(dx-2, dy-2, dz-2, dx+2, dy+2, dz+2);
+    }
+
+    private Map<Node.Coordinate, Node> nodeMap = new HashMap<>();
+
+    private Node openNode(int x, int y, int z)
+    {
+        Node.Coordinate coordinate = new Node.Coordinate(x,y,z);
+        Node node = this.nodeMap.get(coordinate);
+
+        if (node == null)
+        {
+            node = new Node(coordinate);
+            this.nodeMap.put(coordinate, node);
+        }
+
+        return node;
+    }
+
+    @Getter
+    private LinkedList<Vec3> route = new LinkedList<>();
+
+    @Getter
+    private PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing((Node a) -> a == null ? Float.MAX_VALUE : a.f).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.x).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.y).thenComparing(a -> a == null ? Float.MAX_VALUE :  a.coordinate.z));
+
+    private int pfindIdx = 0;
+
+    public boolean pathfind(Vec3 from, long timeout) {
+
+        pfindIdx ++;
+        if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2))
+            open.clear();
+
+        this.lastSx = (int) Math.round(from.xCoord * 2);
+        this.lastSy = (int) Math.round(from.yCoord * 2);
+        this.lastSz = (int) Math.round(from.zCoord * 2);
+        if (dungeonRoom.isBlocked(lastSx, lastSy, lastSz)) return false;
+
+        Node startNode = openNode(dx, dy, dz);
+        Node goalNode = openNode(lastSx, lastSy, lastSz);
+        startNode.g = 0;
+        startNode.f = 0;
+        goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE;
+        if (goalNode.parent != null) {
+            LinkedList<Vec3> route = new LinkedList<>();
+            Node curr =goalNode;
+            while(curr.parent != null) {
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                curr = curr.parent;
+            }
+            route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+            this.route = route;
+            return true;
+        }
+        open.add(startNode);
+
+        long end = System.currentTimeMillis() + timeout;
+
+        while (!open.isEmpty()) {
+            if (System.currentTimeMillis() > end) {
+                return false;
+            }
+            Node n = open.poll();
+            if (n.lastVisited == pfindIdx) continue;
+            n.lastVisited = pfindIdx;
+
+            if (n == goalNode) {
+                // route = reconstructPath(startNode)
+                LinkedList<Vec3> route = new LinkedList<>();
+                Node curr =goalNode;
+                while(curr.parent != null) {
+                    route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                    curr = curr.parent;
+                }
+                route.addLast(new Vec3(curr.coordinate.x / 2.0, curr.coordinate.y / 2.0 + 0.1, curr.coordinate.z/ 2.0));
+                this.route = route;
+                return true;
+            }
+
+            for (EnumFacing value : EnumFacing.VALUES) {
+                Node neighbor = openNode(n.coordinate.x + value.getFrontOffsetX(), n.coordinate.y + value.getFrontOffsetY(), n.coordinate.z + value.getFrontOffsetZ());
+
+                // check blocked.
+                if (!((destinationBB.minX <= neighbor.coordinate.x && neighbor.coordinate.x <= destinationBB.maxX &&
+                        destinationBB.minY <= neighbor.coordinate.y && neighbor.coordinate.y <= destinationBB.maxY &&
+                        destinationBB.minZ <= neighbor.coordinate.z && neighbor.coordinate.z <= destinationBB.maxZ) // near destination
+                 || !dungeonRoom.isBlocked(neighbor.coordinate.x, neighbor.coordinate.y, neighbor.coordinate.z))) { // not blocked
+                    continue;
+                }
+                if (neighbor.lastVisited == pfindIdx) continue;
+
+                boolean flag = false;
+                if (n. parent != null) {
+                    float tempGScore = n.parent.g + distSq(n.parent.coordinate.x - neighbor.coordinate.x, n.parent.coordinate.y - neighbor.coordinate.y, n.parent.coordinate.z - neighbor.coordinate.z);
+                    if (tempGScore < neighbor.g && lineofsight(n.parent, neighbor)) {
+                        neighbor.parent = n.parent;
+                        neighbor.g = tempGScore;
+                        neighbor.f = tempGScore + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                        open.add(neighbor);
+                        flag = true;
+                    }
+                }
+                if (!flag) {
+                    float gScore = n.g + 1; // altho it's sq, it should be fine
+                    if (gScore < neighbor.g) {
+                        neighbor.parent = n;
+                        neighbor.g = gScore;
+                        neighbor.f = gScore +distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                        open.add(neighbor);
+                    } else if (neighbor.lastVisited != pfindIdx) {
+                        neighbor.f = neighbor.g + distSq(goalNode.coordinate.x - neighbor.coordinate.x, goalNode.coordinate.y - neighbor.coordinate.y, goalNode.coordinate.z - neighbor.coordinate.z);
+                        open.add(neighbor);
+                    }
+                }
+            }
+        }
+        return true;
+    }
+
+    private boolean lineofsight(Node a, Node b) {
+        if (a == null || b == null) return false;
+        float sx = a.coordinate.x, sy = a.coordinate.y, sz = a.coordinate.z;
+        int ex = b.coordinate.x, ey = b.coordinate.y, ez = b.coordinate.z;
+
+        float dx = ex - sx, dy = ey - sy, dz = ez - sz;
+        float len = distSq(dx, dy, dz);
+        dx /= len; dy /= len; dz /= len;
+
+        for (int d = 0; d <= len; d += 1) {
+            if (dungeonRoom.isBlocked(Math.round(sx), (int) Math.ceil(sy), Math.round(sz))) return false;
+            if (dungeonRoom.isBlocked(Math.round(sx)+1, (int) Math.ceil(sy), Math.round(sz)+1)) return false;
+            if (dungeonRoom.isBlocked(Math.round(sx)-1, (int) Math.ceil(sy), Math.round(sz)-1)) return false;
+            if (dungeonRoom.isBlocked(Math.round(sx)+1, (int) Math.ceil(sy), Math.round(sz)-1)) return false;
+            if (dungeonRoom.isBlocked(Math.round(sx)-1, (int) Math.ceil(sy), Math.round(sz)+1)) return false;
+            sx += dx; sy += dy; sz += dz;
+        }
+        return true;
+    }
+
+    private int manhatten(int x, int y, int z) {return Math.abs(x)+ Math.abs(y)+ Math.abs(z);}
+    private float distSq(float x, float y, float z) {
+        return MathHelper.sqrt_float(x * x + y * y + z * z);
+    }
+
+    @RequiredArgsConstructor
+    @Data
+    public static final class Node {
+        @Data
+        @RequiredArgsConstructor
+        public static final class Coordinate {
+            private final int x, y, z;
+        }
+        
+        private final Coordinate coordinate;
+        
+        private float f = Float.MAX_VALUE, g = Float.MAX_VALUE;
+        private int lastVisited;
+
+        @EqualsAndHashCode.Exclude
+        @ToString.Exclude
+        private Node parent;
+    }
+}