diff options
15 files changed, 784 insertions, 979 deletions
diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonContext.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonContext.java index 62c557d7..42fa664c 100755 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonContext.java +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonContext.java @@ -29,6 +29,7 @@ import kr.syeyoung.dungeonsguide.mod.dungeon.map.DungeonMapConstantRetriever; import kr.syeyoung.dungeonsguide.mod.dungeon.map.DungeonMapLayout; import kr.syeyoung.dungeonsguide.mod.dungeon.map.DungeonRoomScaffoldParser; import kr.syeyoung.dungeonsguide.mod.dungeon.map.MapPlayerProcessor; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.PathfinderExecutor; import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; import kr.syeyoung.dungeonsguide.mod.dungeon.roomprocessor.RoomProcessor; import kr.syeyoung.dungeonsguide.mod.dungeon.roomprocessor.bossfight.BossfightProcessor; @@ -54,6 +55,7 @@ import java.util.ArrayList; import java.util.HashSet; import java.util.List; import java.util.Set; +import java.util.concurrent.CopyOnWriteArrayList; public class DungeonContext { @Getter @Setter @@ -67,6 +69,9 @@ public class DungeonContext { @Getter private DungeonEventRecorder recorder = new DungeonEventRecorder(); + @Getter + private List<PathfinderExecutor> executors = new CopyOnWriteArrayList<>(); + @Getter private final List<RoomProcessor> globalRoomProcessors = new ArrayList<>(); @@ -92,6 +97,8 @@ public class DungeonContext { @Getter @Setter public int percentage; + private PathfinderExecutorExecutor executor = new PathfinderExecutorExecutor(this); + public void setGotMimic(boolean gotMimic) { this.gotMimic = gotMimic; @@ -130,6 +137,8 @@ public class DungeonContext { init = System.currentTimeMillis(); + + executor.start(); } @@ -202,6 +211,10 @@ public class DungeonContext { } } + public void cleanup() { + executor.interrupt(); + } + @Getter private boolean ended = false; @Getter diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonFacade.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonFacade.java index cfa4e0cb..9ee4a55a 100644 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonFacade.java +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/DungeonFacade.java @@ -34,9 +34,14 @@ import java.security.NoSuchAlgorithmException; public class DungeonFacade { @Getter - @Setter private DungeonContext context; + public void setContext(DungeonContext context) { + if (this.context != null) + this.context.cleanup(); + this.context = context; + } + public void init() { try { DungeonRoomInfoRegistry.loadAll(Main.getConfigDir()); diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/PathfinderExecutorExecutor.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/PathfinderExecutorExecutor.java new file mode 100644 index 00000000..676dd017 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/PathfinderExecutorExecutor.java @@ -0,0 +1,56 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon; + +import kr.syeyoung.dungeonsguide.mod.DungeonsGuide; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.PathfinderExecutor; +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import net.minecraft.client.Minecraft; + +import java.awt.*; + +public class PathfinderExecutorExecutor extends Thread{ + public PathfinderExecutorExecutor(DungeonContext context) { + super(DungeonsGuide.THREAD_GROUP, "DG Pathfinder"); + this.context =context; + } + private DungeonContext context; + @Override + public void run() { + while(!isInterrupted()) { + if (context.getScaffoldParser() != null) { + Point roomPt = context.getScaffoldParser().getDungeonMapLayout().worldPointToRoomPoint(Minecraft.getMinecraft().thePlayer.getPosition()); + + DungeonRoom dungeonRoom = context.getScaffoldParser().getRoomMap().get(roomPt); + try { + for (PathfinderExecutor executor : context.getExecutors()) { + if (executor.getDungeonRoom() == dungeonRoom) + executor.doStep(); + } + } catch (Exception e) { + e.printStackTrace(); // wtf? + try { + Thread.sleep(1000); + } catch (InterruptedException ex) { + } + } + } + } + } +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMove.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMove.java index b56cc05d..426c75ae 100755 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMove.java +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMove.java @@ -21,6 +21,7 @@ package kr.syeyoung.dungeonsguide.mod.dungeon.actions; import kr.syeyoung.dungeonsguide.dungeon.data.OffsetPoint; import kr.syeyoung.dungeonsguide.mod.dungeon.actions.tree.ActionRouteProperties; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.PathfinderExecutor; import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; import kr.syeyoung.dungeonsguide.mod.features.FeatureRegistry; import kr.syeyoung.dungeonsguide.mod.utils.RenderUtils; @@ -34,8 +35,6 @@ import net.minecraft.util.Vec3; import java.util.HashSet; import java.util.List; import java.util.Set; -import java.util.concurrent.ExecutionException; -import java.util.concurrent.Future; @Data @EqualsAndHashCode(callSuper=false) @@ -90,31 +89,27 @@ public class ActionMove extends AbstractAction { private int tick = -1; private List<Vec3> poses; - private Future<List<Vec3>> latestFuture; + private PathfinderExecutor executor; @Override public void onTick(DungeonRoom dungeonRoom, ActionRouteProperties actionRouteProperties) { tick = (tick+1) % Math.max(1, actionRouteProperties.getLineRefreshRate()); - if (latestFuture != null && latestFuture.isDone()) { - try { - poses = latestFuture.get(); - latestFuture = null; - } catch (InterruptedException | ExecutionException e) { - e.printStackTrace(); - } + if (executor == null) { + executor = dungeonRoom.createEntityPathTo(target.getBlockPos(dungeonRoom)); + } + if (executor != null) { + poses = executor.getRoute(Minecraft.getMinecraft().thePlayer.getPositionVector()); } - if (tick == 0 && actionRouteProperties.isPathfind() && latestFuture == null) { + if (tick == 0 && actionRouteProperties.isPathfind() && executor != null) { if (!FeatureRegistry.SECRET_FREEZE_LINES.isEnabled() || poses == null || actionRouteProperties.getLineRefreshRate() != -1) { - latestFuture = dungeonRoom.createEntityPathTo(dungeonRoom.getContext().getWorld(), Minecraft.getMinecraft().thePlayer, target.getBlockPos(dungeonRoom), Integer.MAX_VALUE, 10000); + executor.setTarget(Minecraft.getMinecraft().thePlayer.getPositionVector()); } } } public void forceRefresh(DungeonRoom dungeonRoom) { - if (latestFuture == null) { - latestFuture = dungeonRoom.createEntityPathTo(dungeonRoom.getContext().getWorld(), Minecraft.getMinecraft().thePlayer, target.getBlockPos(dungeonRoom), Integer.MAX_VALUE, 10000); - } + if (executor != null) executor.setTarget(Minecraft.getMinecraft().thePlayer.getPositionVector()); } @Override public String toString() { diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMoveNearestAir.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMoveNearestAir.java index 08487d81..c12d1ffd 100755 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMoveNearestAir.java +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/actions/ActionMoveNearestAir.java @@ -21,6 +21,7 @@ package kr.syeyoung.dungeonsguide.mod.dungeon.actions; import kr.syeyoung.dungeonsguide.dungeon.data.OffsetPoint; import kr.syeyoung.dungeonsguide.mod.dungeon.actions.tree.ActionRouteProperties; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.PathfinderExecutor; import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; import kr.syeyoung.dungeonsguide.mod.features.FeatureRegistry; import lombok.Data; @@ -31,8 +32,6 @@ import net.minecraft.util.Vec3; import java.util.HashSet; import java.util.List; import java.util.Set; -import java.util.concurrent.ExecutionException; -import java.util.concurrent.Future; @Data @EqualsAndHashCode(callSuper=false) @@ -60,31 +59,26 @@ public class ActionMoveNearestAir extends AbstractAction { private int tick = -1; private List<Vec3> poses; - private Future<List<Vec3>> latestFuture; + private PathfinderExecutor executor; @Override public void onTick(DungeonRoom dungeonRoom, ActionRouteProperties actionRouteProperties) { tick = (tick+1) % Math.max(1, actionRouteProperties.getLineRefreshRate()); - if (latestFuture != null && latestFuture.isDone()) { - try { - poses = latestFuture.get(); - latestFuture = null; - } catch (InterruptedException | ExecutionException e) { - e.printStackTrace(); - } + if (executor == null) { + executor = dungeonRoom.createEntityPathTo(target.getBlockPos(dungeonRoom)); + } + if (executor != null) { + poses = executor.getRoute(Minecraft.getMinecraft().thePlayer.getPositionVector()); } - if (tick == 0 && actionRouteProperties.isPathfind() && latestFuture == null) { + if (tick == 0 && actionRouteProperties.isPathfind() && executor != null) { if (!FeatureRegistry.SECRET_FREEZE_LINES.isEnabled() || poses == null || actionRouteProperties.getLineRefreshRate() != -1) { - latestFuture = dungeonRoom.createEntityPathTo(dungeonRoom.getContext().getWorld(), Minecraft.getMinecraft().thePlayer, target.getBlockPos(dungeonRoom), Integer.MAX_VALUE, 10000); + executor.setTarget(Minecraft.getMinecraft().thePlayer.getPositionVector()); } } } - public void forceRefresh(DungeonRoom dungeonRoom) { - if (latestFuture == null) { - latestFuture = dungeonRoom.createEntityPathTo(dungeonRoom.getContext().getWorld(), Minecraft.getMinecraft().thePlayer, target.getBlockPos(dungeonRoom), Integer.MAX_VALUE, 10000); - } + if (executor != null) executor.setTarget(Minecraft.getMinecraft().thePlayer.getPositionVector()); } @Override public String toString() { diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/AStarCornerCut.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/AStarCornerCut.java deleted file mode 100644 index a21bffd5..00000000 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/AStarCornerCut.java +++ /dev/null @@ -1,192 +0,0 @@ -/* - * 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.mod.dungeon.pathfinding; - -import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; -import lombok.Data; -import lombok.EqualsAndHashCode; -import lombok.Getter; -import lombok.RequiredArgsConstructor; -import net.minecraft.util.AxisAlignedBB; -import net.minecraft.util.BlockPos; -import net.minecraft.util.MathHelper; -import net.minecraft.util.Vec3; -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/mod/dungeon/pathfinding/AStarFineGrid.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/AStarFineGrid.java deleted file mode 100644 index 8cb49a10..00000000 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/AStarFineGrid.java +++ /dev/null @@ -1,182 +0,0 @@ -/* - * 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.mod.dungeon.pathfinding; - -import kr.syeyoung.dungeonsguide.mod.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/mod/dungeon/pathfinding/JPSPathfinder.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/JPSPathfinder.java deleted file mode 100644 index 0a4e1b7d..00000000 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/JPSPathfinder.java +++ /dev/null @@ -1,306 +0,0 @@ -/* - * 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.mod.dungeon.pathfinding; - -import kr.syeyoung.dungeonsguide.mod.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/mod/dungeon/pathfinding/ThetaStar.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/ThetaStar.java deleted file mode 100644 index 2b441dd3..00000000 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/ThetaStar.java +++ /dev/null @@ -1,212 +0,0 @@ -/* - * 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.mod.dungeon.pathfinding; - -import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; -import lombok.Data; -import lombok.EqualsAndHashCode; -import lombok.Getter; -import lombok.ToString; -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); - } - - @Data - public static final class Node { - @Data - 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; - } -} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarCornerCut.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarCornerCut.java new file mode 100644 index 00000000..d0fc9a16 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarCornerCut.java @@ -0,0 +1,183 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon.pathfinding.algorithms; + +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import lombok.Data; +import lombok.EqualsAndHashCode; +import lombok.Getter; +import lombok.RequiredArgsConstructor; +import net.minecraft.util.AxisAlignedBB; +import net.minecraft.util.MathHelper; +import net.minecraft.util.Vec3; + +import java.util.*; + +public class AStarCornerCut implements IPathfinder { + private int lastSx, lastSy, lastSz; + private int dx, dy, dz; + private DungeonRoom dungeonRoom; + + + private Node startNode; + private Node goalNode; + + @Getter + private AxisAlignedBB destinationBB; + @Override + public void init(DungeonRoom dungeonRoom, Vec3 destination) { + 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); + startNode = openNode(dx, dy, dz); + } + private Map<Node.Coordinate, Node> nodeMap = new HashMap<>(); + @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; + 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; + } + private boolean found = false; + + @Override + public boolean doOneStep() { + if (found) return true; + Node n = open.poll(); + if (n == null) return false; + if (n.lastVisited == pfindIdx) return false; + n.lastVisited = pfindIdx; + + if (n == goalNode) { + // route = reconstructPath(startNode) + found = true; + 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 false; + } + + @Override + public void setTarget(Vec3 from) { + if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2)) { + } else { + return; + } + open.clear(); + pfindIdx++; + found = false; + this.lastSx = (int) Math.round(from.xCoord * 2); + this.lastSy = (int) Math.round(from.yCoord * 2); + this.lastSz = (int) Math.round(from.zCoord * 2); + + goalNode = openNode(lastSx, lastSy, lastSz); + + startNode.g = 0; + startNode.f = 0; + goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE; + + open.add(startNode); + + if (goalNode.parent != null) { + found = true; + } + } + + @Override + public List<Vec3> getRoute(Vec3 from) { + int lastSx = (int) Math.round(from.xCoord * 2); + int lastSy = (int) Math.round(from.yCoord * 2); + int lastSz = (int) Math.round(from.zCoord * 2); + + Node goalNode = openNode(lastSx, lastSy, lastSz); + + LinkedList<Vec3> route = new LinkedList<>(); + Node curr =goalNode; + if (curr.parent == null) return null; + 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)); + return route; + } + + + 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 Node.Coordinate coordinate; + + private float f = Float.MAX_VALUE, g = Float.MAX_VALUE; + private int lastVisited; + + @EqualsAndHashCode.Exclude + private Node parent; + + } +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarFineGrid.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarFineGrid.java new file mode 100644 index 00000000..e3b73d52 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/AStarFineGrid.java @@ -0,0 +1,181 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon.pathfinding.algorithms; + +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import lombok.Data; +import lombok.EqualsAndHashCode; +import lombok.Getter; +import lombok.RequiredArgsConstructor; +import net.minecraft.util.*; + +import java.util.*; + +public class AStarFineGrid implements IPathfinder { + + private int lastSx, lastSy, lastSz; + private int dx, dy, dz; + private DungeonRoom dungeonRoom; + + + private Node startNode; + private Node goalNode; + + @Getter + private AxisAlignedBB destinationBB; + @Override + public void init(DungeonRoom dungeonRoom, Vec3 destination) { + 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); + startNode = openNode(dx, dy, dz); + } + private Map<Node.Coordinate, Node> nodeMap = new HashMap<>(); + @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; + 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; + } + private boolean found = false; + + @Override + public boolean doOneStep() { + if (found) return true; + Node n = open.poll(); + if (n == null) return false; + if (n.lastVisited == pfindIdx) return false; + n.lastVisited = pfindIdx; + + if (n == goalNode) { + // route = reconstructPath(startNode) + found = true; + 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 false; + } + + @Override + public void setTarget(Vec3 from) { + if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2)) { + } else { + return; + } + open.clear(); + pfindIdx++; + found = false; + this.lastSx = (int) Math.round(from.xCoord * 2); + this.lastSy = (int) Math.round(from.yCoord * 2); + this.lastSz = (int) Math.round(from.zCoord * 2); + + goalNode = openNode(lastSx, lastSy, lastSz); + + startNode.g = 0; + startNode.f = 0; + goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE; + + open.add(startNode); + + + if (goalNode.parent != null) { + found = true; + } + } + + @Override + public List<Vec3> getRoute(Vec3 from) { + int lastSx = (int) Math.round(from.xCoord * 2); + int lastSy = (int) Math.round(from.yCoord * 2); + int lastSz = (int) Math.round(from.zCoord * 2); + + Node goalNode = openNode(lastSx, lastSy, lastSz); + + LinkedList<Vec3> route = new LinkedList<>(); + Node curr =goalNode; + if (curr.parent == null) return null; + 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)); + return route; + } + + + 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; + + } +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/IPathfinder.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/IPathfinder.java new file mode 100644 index 00000000..3ea5cfa1 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/IPathfinder.java @@ -0,0 +1,32 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon.pathfinding.algorithms; + +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import net.minecraft.util.Vec3; + +import java.util.List; + +public interface IPathfinder { + void init(DungeonRoom dungeonRoom, Vec3 destination); + boolean doOneStep(); + + void setTarget(Vec3 from); + List<Vec3> getRoute(Vec3 from); +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/PathfinderExecutor.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/PathfinderExecutor.java new file mode 100644 index 00000000..0313d3c4 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/PathfinderExecutor.java @@ -0,0 +1,63 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon.pathfinding.algorithms; + +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import lombok.Getter; +import net.minecraft.util.Vec3; + +import java.util.ArrayList; +import java.util.List; + +public class PathfinderExecutor { + private boolean invalidate = false; + @Getter + private Vec3 target; + + @Getter + private DungeonRoom dungeonRoom; + + private IPathfinder pathfinder; + private boolean isComplete = false; + private List<Vec3> lastRoute = new ArrayList<>(); + + public PathfinderExecutor(IPathfinder pathfinder, Vec3 target, DungeonRoom dungeonRoom) { + this.pathfinder = pathfinder; + this.target = target; + this.dungeonRoom = dungeonRoom; + pathfinder.init(dungeonRoom, target); + } + + public boolean doStep() { + pathfinder.setTarget(target); + isComplete = pathfinder.doOneStep(); + return isComplete; + } + + public void setTarget(Vec3 target) { + this.target = target; + } + + public List<Vec3> getRoute(Vec3 target) { + if (!isComplete) return lastRoute; + List<Vec3> route = pathfinder.getRoute(target); + if (route == null) return lastRoute = pathfinder.getRoute(getTarget()); + else return lastRoute = route; + } +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/ThetaStar.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/ThetaStar.java new file mode 100644 index 00000000..ce7ffcc8 --- /dev/null +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/pathfinding/algorithms/ThetaStar.java @@ -0,0 +1,213 @@ +/* + * Dungeons Guide - The most intelligent Hypixel Skyblock Dungeons Mod + * Copyright (C) 2023 cyoung06 (syeyoung) + * + * 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.mod.dungeon.pathfinding.algorithms; + +import kr.syeyoung.dungeonsguide.mod.dungeon.roomfinder.DungeonRoom; +import lombok.Data; +import lombok.EqualsAndHashCode; +import lombok.Getter; +import lombok.RequiredArgsConstructor; +import net.minecraft.util.*; + +import java.util.*; + +public class ThetaStar implements IPathfinder { + + private int lastSx, lastSy, lastSz; + private int dx, dy, dz; + private DungeonRoom dungeonRoom; + + + private Node startNode; + private Node goalNode; + + @Getter + private AxisAlignedBB destinationBB; + @Override + public void init(DungeonRoom dungeonRoom, Vec3 destination) { + 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); + startNode = openNode(dx, dy, dz); + } + private Map<Node.Coordinate, Node> nodeMap = new HashMap<>(); + @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; + 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; + } + private boolean found = false; + + @Override + public boolean doOneStep() { + if (found) return true; + Node n = open.poll(); + if (n == null) return false; + if (n.lastVisited == pfindIdx) return false; + n.lastVisited = pfindIdx; + + if (n == goalNode) { + // route = reconstructPath(startNode) + found =true; + 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 false; + } + + @Override + public void setTarget(Vec3 from) { + if (lastSx != (int)Math.round(from.xCoord * 2) || lastSy != (int)Math.round(from.yCoord*2) || lastSz != (int)Math.round(from.zCoord * 2)) { + } else { + return; + } + open.clear(); + pfindIdx++; + found = false; + this.lastSx = (int) Math.round(from.xCoord * 2); + this.lastSy = (int) Math.round(from.yCoord * 2); + this.lastSz = (int) Math.round(from.zCoord * 2); + + goalNode = openNode(lastSx, lastSy, lastSz); + + startNode.g = 0; + startNode.f = 0; + goalNode.g = Integer.MAX_VALUE; goalNode.f = Integer.MAX_VALUE; + + open.add(startNode); + + + if (goalNode.parent != null) { + found = true; + } + } + + @Override + public List<Vec3> getRoute(Vec3 from) { + int lastSx = (int) Math.round(from.xCoord * 2); + int lastSy = (int) Math.round(from.yCoord * 2); + int lastSz = (int) Math.round(from.zCoord * 2); + + Node goalNode = openNode(lastSx, lastSy, lastSz); + + LinkedList<Vec3> route = new LinkedList<>(); + Node curr =goalNode; + if (curr.parent == null) return null; + 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)); + return route; + } + 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 + private Node parent; + + } +} diff --git a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/roomfinder/DungeonRoom.java b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/roomfinder/DungeonRoom.java index 5957ebf3..44bad60f 100755 --- a/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/roomfinder/DungeonRoom.java +++ b/mod/src/main/java/kr/syeyoung/dungeonsguide/mod/dungeon/roomfinder/DungeonRoom.java @@ -32,6 +32,10 @@ import kr.syeyoung.dungeonsguide.mod.dungeon.events.impl.DungeonRoomMatchEvent; import kr.syeyoung.dungeonsguide.mod.dungeon.events.impl.DungeonStateChangeEvent; import kr.syeyoung.dungeonsguide.mod.dungeon.map.DungeonRoomScaffoldParser; import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.*; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.AStarCornerCut; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.AStarFineGrid; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.PathfinderExecutor; +import kr.syeyoung.dungeonsguide.mod.dungeon.pathfinding.algorithms.ThetaStar; import kr.syeyoung.dungeonsguide.mod.dungeon.roomedit.EditingContext; import kr.syeyoung.dungeonsguide.mod.dungeon.roomprocessor.ProcessorFactory; import kr.syeyoung.dungeonsguide.mod.dungeon.roomprocessor.RoomProcessor; @@ -43,13 +47,8 @@ import lombok.Getter; import lombok.Setter; import net.minecraft.block.Block; import net.minecraft.block.state.IBlockState; -import net.minecraft.entity.Entity; -import net.minecraft.pathfinding.PathEntity; -import net.minecraft.pathfinding.PathFinder; -import net.minecraft.pathfinding.PathPoint; import net.minecraft.util.*; import net.minecraft.world.ChunkCache; -import net.minecraft.world.IBlockAccess; import net.minecraft.world.World; import javax.vecmath.Vector2d; @@ -102,63 +101,27 @@ public class DungeonRoom { this.currentState = currentState; } - private final Map<BlockPos, AStarFineGrid> activeBetterAStar = new HashMap<>(); - private final Map<BlockPos, AStarCornerCut> activeBetterAStarCornerCut = new HashMap<>(); - private final Map<BlockPos, ThetaStar> activeThetaStar = new HashMap<>(); + private final Map<BlockPos, PathfinderExecutor> activePathfind = new HashMap<>(); - public ScheduledFuture<List<Vec3>> createEntityPathTo(IBlockAccess blockAccess, Entity entityIn, BlockPos targetPos, float dist, int timeout) { + public PathfinderExecutor createEntityPathTo(BlockPos pos) { FeaturePathfindStrategy.PathfindStrategy pathfindStrategy = FeatureRegistry.SECRET_PATHFIND_STRATEGY.getPathfindStrat(); - if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.JPS_LEGACY) { - return asyncPathFinder.schedule(() -> { - BlockPos min = new BlockPos(getMin().getX(), 0, getMin().getZ()); - BlockPos max= new BlockPos(getMax().getX(), 255, getMax().getZ()); - JPSPathfinder pathFinder = new JPSPathfinder(this); - pathFinder.pathfind(entityIn.getPositionVector(), new Vec3(targetPos).addVector(0.5, 0.5, 0.5), 1.5f,timeout); - return pathFinder.getRoute(); - }, 0, TimeUnit.MILLISECONDS); - } else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_FINE_GRID) { - return asyncPathFinder.schedule(() -> { - AStarFineGrid pathFinder = - activeBetterAStar.computeIfAbsent(targetPos, (pos) -> new AStarFineGrid(this, new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5))); - pathFinder.pathfind(entityIn.getPositionVector(),timeout); - return pathFinder.getRoute(); - }, 0, TimeUnit.MILLISECONDS); - }else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_DIAGONAL) { - return asyncPathFinder.schedule(() -> { - AStarCornerCut pathFinder = - activeBetterAStarCornerCut.computeIfAbsent(targetPos, (pos) -> new AStarCornerCut(this, new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5))); - pathFinder.pathfind(entityIn.getPositionVector(),timeout); - return pathFinder.getRoute(); - }, 0, TimeUnit.MILLISECONDS); + if (activePathfind.containsKey(pos)) return activePathfind.get(pos); + PathfinderExecutor executor; + if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_FINE_GRID) { + executor = new PathfinderExecutor(new AStarFineGrid(), new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5), this); + } else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_DIAGONAL) { + executor = new PathfinderExecutor(new AStarCornerCut(), new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5), this); } else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.THETA_STAR) { - return asyncPathFinder.schedule(() -> { - ThetaStar pathFinder = - activeThetaStar.computeIfAbsent(targetPos, (pos) -> new ThetaStar(this, new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5))); - pathFinder.pathfind(entityIn.getPositionVector(),timeout); - return pathFinder.getRoute(); - }, 0, TimeUnit.MILLISECONDS); + executor = new PathfinderExecutor(new ThetaStar(), new Vec3(pos.getX(), pos.getY(), pos.getZ()).addVector(0.5, 0.5, 0.5), this); } else { - return asyncPathFinder.schedule(() -> { - PathFinder pathFinder = new PathFinder(nodeProcessorDungeonRoom); - PathEntity latest = pathFinder.createEntityPathTo(blockAccess, entityIn, targetPos, dist); - if (latest != null) { - List<Vec3> poses = new ArrayList<>(); - for (int i = 0; i < latest.getCurrentPathLength(); i++) { - PathPoint pathPoint = latest.getPathPointFromIndex(i); - poses.add(new Vec3(getMin().add(pathPoint.xCoord, pathPoint.yCoord, pathPoint.zCoord)).addVector(0.5,0.5,0.5)); - } - return poses; - } - return new ArrayList<>(); - }, 0, TimeUnit.MILLISECONDS); + return null; } + activePathfind.put(pos, executor); + context.getExecutors().add(executor); + return executor; } private static final ExecutorService roomMatcherThread = Executors.newSingleThreadExecutor( DungeonsGuide.THREAD_FACTORY); - private static final ScheduledExecutorService asyncPathFinder = Executors.newScheduledThreadPool(4, DungeonsGuide.THREAD_FACTORY); - @Getter - private final NodeProcessorDungeonRoom nodeProcessorDungeonRoom; - @Getter private final Map<String, Object> roomContext = new HashMap<>(); @@ -202,7 +165,6 @@ public class DungeonRoom { arr = new long[lenx *leny * lenz * 2 / 8];; buildDoors(doorsAndStates); - nodeProcessorDungeonRoom = new NodeProcessorDungeonRoom(this); roomMatcherThread.submit(() -> { try { |