aboutsummaryrefslogtreecommitdiff
path: root/src/main
diff options
context:
space:
mode:
authorsyeyoung <cyougn06@naver.com>2022-01-31 23:16:26 +0900
committersyeyoung <cyougn06@naver.com>2022-01-31 23:16:26 +0900
commit33bc7744dceed33aa3220f351a43d2617f68183b (patch)
treeed58162a9467f28568c8baaf4e90ec571228e6fe /src/main
parentb518d47800ced4dd0f0e0250090826b5f0bace44 (diff)
downloadSkyblock-Dungeons-Guide-33bc7744dceed33aa3220f351a43d2617f68183b.tar.gz
Skyblock-Dungeons-Guide-33bc7744dceed33aa3220f351a43d2617f68183b.tar.bz2
Skyblock-Dungeons-Guide-33bc7744dceed33aa3220f351a43d2617f68183b.zip
- Add 3 new pathfinding algorithms
- Theta* - A* with finegrid used by jps - A* with finegrid used by jps + diagonal routes - Make MStringSelectionButton inc and dec button work as intended - Add new "feature" for choosing pathfind strategy
Diffstat (limited to 'src/main')
-rwxr-xr-xsrc/main/java/kr/syeyoung/dungeonsguide/DungeonsGuide.java6
-rwxr-xr-xsrc/main/java/kr/syeyoung/dungeonsguide/dungeon/roomfinder/DungeonRoom.java38
-rwxr-xr-xsrc/main/java/kr/syeyoung/dungeonsguide/eventlistener/DungeonListener.java18
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/features/FeatureRegistry.java2
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/features/impl/secret/FeaturePathfindStrategy.java110
-rwxr-xr-xsrc/main/java/kr/syeyoung/dungeonsguide/gui/elements/MStringSelectionButton.java8
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java189
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java182
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java16
-rw-r--r--src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java212
10 files changed, 765 insertions, 16 deletions
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/DungeonsGuide.java b/src/main/java/kr/syeyoung/dungeonsguide/DungeonsGuide.java
index ac860e78..b3467132 100755
--- a/src/main/java/kr/syeyoung/dungeonsguide/DungeonsGuide.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/DungeonsGuide.java
@@ -38,12 +38,16 @@ import kr.syeyoung.dungeonsguide.stomp.StompClient;
import kr.syeyoung.dungeonsguide.stomp.StompInterface;
import kr.syeyoung.dungeonsguide.utils.AhUtils;
import kr.syeyoung.dungeonsguide.utils.TimeScoreUtil;
+import kr.syeyoung.dungeonsguide.utils.cursor.GLCursors;
import kr.syeyoung.dungeonsguide.wsresource.StaticResourceCache;
import lombok.Getter;
import net.minecraft.client.Minecraft;
import net.minecraft.client.gui.GuiButton;
import net.minecraft.client.gui.GuiErrorScreen;
import net.minecraft.client.gui.GuiScreen;
+import net.minecraft.client.resources.IReloadableResourceManager;
+import net.minecraft.client.resources.IResourceManager;
+import net.minecraft.client.resources.IResourceManagerReloadListener;
import net.minecraft.client.resources.IResourcePack;
import net.minecraft.launchwrapper.LaunchClassLoader;
import net.minecraft.util.IChatComponent;
@@ -166,6 +170,8 @@ public class DungeonsGuide implements DGInterface, CloseListener {
TimeScoreUtil.init();
ProgressManager.pop(progressbar);
+
+ ((IReloadableResourceManager)Minecraft.getMinecraft().getResourceManager()).registerReloadListener(resourceManager -> GLCursors.setupCursors());
}
@Getter
private boolean firstTimeUsingDG = false;
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/dungeon/roomfinder/DungeonRoom.java b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/roomfinder/DungeonRoom.java
index 4052d2a0..2419f50a 100755
--- a/src/main/java/kr/syeyoung/dungeonsguide/dungeon/roomfinder/DungeonRoom.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/dungeon/roomfinder/DungeonRoom.java
@@ -19,7 +19,6 @@
package kr.syeyoung.dungeonsguide.dungeon.roomfinder;
import com.google.common.collect.Sets;
-import kr.syeyoung.dungeonsguide.DungeonsGuide;
import kr.syeyoung.dungeonsguide.dungeon.DungeonContext;
import kr.syeyoung.dungeonsguide.dungeon.MapProcessor;
import kr.syeyoung.dungeonsguide.dungeon.data.DungeonRoomInfo;
@@ -29,9 +28,8 @@ import kr.syeyoung.dungeonsguide.dungeon.events.DungeonStateChangeEvent;
import kr.syeyoung.dungeonsguide.dungeon.mechanics.DungeonMechanic;
import kr.syeyoung.dungeonsguide.dungeon.mechanics.DungeonRoomDoor;
import kr.syeyoung.dungeonsguide.features.FeatureRegistry;
-import kr.syeyoung.dungeonsguide.pathfinding.CachedWorld;
-import kr.syeyoung.dungeonsguide.pathfinding.JPSPathfinder;
-import kr.syeyoung.dungeonsguide.pathfinding.NodeProcessorDungeonRoom;
+import kr.syeyoung.dungeonsguide.features.impl.secret.FeaturePathfindStrategy;
+import kr.syeyoung.dungeonsguide.pathfinding.*;
import kr.syeyoung.dungeonsguide.roomedit.EditingContext;
import kr.syeyoung.dungeonsguide.roomprocessor.ProcessorFactory;
import kr.syeyoung.dungeonsguide.roomprocessor.RoomProcessor;
@@ -102,8 +100,13 @@ public class DungeonRoom {
this.currentState = currentState;
}
+ private Map<BlockPos, AStarFineGrid> activeBetterAStar = new HashMap<>();
+ private Map<BlockPos, AStarCornerCut> activeBetterAStarCornerCut = new HashMap<>();
+ private Map<BlockPos, ThetaStar> activeThetaStar = new HashMap<>();
+
public ScheduledFuture<List<Vec3>> createEntityPathTo(IBlockAccess blockaccess, Entity entityIn, BlockPos targetPos, float dist, int timeout) {
- if (FeatureRegistry.SECRET_PATHFIND_STRATEGY.isEnabled()) {
+ FeaturePathfindStrategy.PathfindStrategy pathfindStrategy = FeatureRegistry.SECRET_PATHFIND_STRATEGY.getPathfindStrat();
+ if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.JPS_LEGACY) {
ScheduledFuture<List<Vec3>> sf = asyncPathFinder.schedule(() -> {
BlockPos min = new BlockPos(getMin().getX(), 0, getMin().getZ());
BlockPos max= new BlockPos(getMax().getX(), 255, getMax().getZ());
@@ -112,6 +115,30 @@ public class DungeonRoom {
return pathFinder.getRoute();
}, 0, TimeUnit.MILLISECONDS);
return sf;
+ } else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_FINE_GRID) {
+ ScheduledFuture<List<Vec3>> sf = 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);
+ return sf;
+ }else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.A_STAR_DIAGONAL) {
+ ScheduledFuture<List<Vec3>> sf = 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);
+ return sf;
+ } else if (pathfindStrategy == FeaturePathfindStrategy.PathfindStrategy.THETA_STAR) {
+ ScheduledFuture<List<Vec3>> sf = 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);
+ return sf;
} else {
ScheduledFuture<List<Vec3>> sf = asyncPathFinder.schedule(() -> {
PathFinder pathFinder = new PathFinder(nodeProcessorDungeonRoom);
@@ -276,6 +303,7 @@ public class DungeonRoom {
long arr[];
+ // These values are doubled
private final int minx, miny, minz, maxx, maxy, maxz;
private final int lenx, leny, lenz;
private static final float playerWidth = 0.3f;
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/eventlistener/DungeonListener.java b/src/main/java/kr/syeyoung/dungeonsguide/eventlistener/DungeonListener.java
index 2edf4d83..7997aec4 100755
--- a/src/main/java/kr/syeyoung/dungeonsguide/eventlistener/DungeonListener.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/eventlistener/DungeonListener.java
@@ -47,6 +47,8 @@ import net.minecraft.client.gui.GuiErrorScreen;
import net.minecraft.client.gui.GuiScreen;
import net.minecraft.client.renderer.GlStateManager;
import net.minecraft.entity.passive.EntityBat;
+import net.minecraft.util.AxisAlignedBB;
+import net.minecraft.util.BlockPos;
import net.minecraft.util.ChatComponentText;
import net.minecraft.util.Vec3;
import net.minecraftforge.client.event.ClientChatReceivedEvent;
@@ -339,6 +341,22 @@ public class DungeonListener {
}
}
+ if (FeatureRegistry.DEBUG.isEnabled() && dungeonRoom !=null) {
+
+ Vec3 player = Minecraft.getMinecraft().thePlayer.getPositionVector();
+ BlockPos real = new BlockPos(player.xCoord * 2, player.yCoord * 2, player.zCoord * 2);
+ for (BlockPos allInBox : BlockPos.getAllInBox(real.add(-1, -1, -1), real.add(1, 1, 1))) {
+ boolean blocked = dungeonRoom.isBlocked(allInBox.getX(), allInBox.getY(), allInBox.getZ());
+
+ RenderUtils.highlightBox(
+ AxisAlignedBB.fromBounds(
+ allInBox.getX() / 2.0 - 0.1, allInBox.getY() / 2.0 - 0.1, allInBox.getZ() / 2.0 - 0.1,
+ allInBox.getX() / 2.0 + 0.1, allInBox.getY() / 2.0 + 0.1, allInBox.getZ() / 2.0 + 0.1
+ ), blocked ? new Color(0x55FF0000, true) : new Color(0x3300FF00, true), renderWorldLastEvent.partialTicks, false);
+
+ }
+ }
+
}
if (EditingContext.getEditingContext() != null) {
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/features/FeatureRegistry.java b/src/main/java/kr/syeyoung/dungeonsguide/features/FeatureRegistry.java
index 16201dcb..7ef483e1 100644
--- a/src/main/java/kr/syeyoung/dungeonsguide/features/FeatureRegistry.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/features/FeatureRegistry.java
@@ -83,7 +83,7 @@ public class FeatureRegistry {
public static final PathfindLineProperties SECRET_LINE_PROPERTIES_SECRET_BROWSER = register(new PathfindLineProperties("Dungeon Secrets.Secret Browser", "Line Settings", "Line Settings when pathfinding using Secret Browser", "secret.lineproperties.secretbrowser", true, SECRET_LINE_PROPERTIES_GLOBAL));
public static final FeatureActions SECRET_ACTIONS = register(new FeatureActions());
- public static final SimpleFeature SECRET_PATHFIND_STRATEGY = register(new SimpleFeature("Dungeon Secrets", "Use NEW JPS Optimization instead of standard A Star", "Faster, and accurate routes.", "secret.secretpathfind.algorithm", true));
+ public static final FeaturePathfindStrategy SECRET_PATHFIND_STRATEGY = register(new FeaturePathfindStrategy());
public static final FeatureTogglePathfind SECRET_TOGGLE_KEY = register(new FeatureTogglePathfind());
public static final FeatureFreezePathfind SECRET_FREEZE_LINES = register(new FeatureFreezePathfind());
public static final FeatureCreateRefreshLine SECRET_CREATE_REFRESH_LINE = register(new FeatureCreateRefreshLine());
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/features/impl/secret/FeaturePathfindStrategy.java b/src/main/java/kr/syeyoung/dungeonsguide/features/impl/secret/FeaturePathfindStrategy.java
new file mode 100644
index 00000000..9c732dbf
--- /dev/null
+++ b/src/main/java/kr/syeyoung/dungeonsguide/features/impl/secret/FeaturePathfindStrategy.java
@@ -0,0 +1,110 @@
+/*
+ * 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.features.impl.secret;
+
+import com.google.common.base.Supplier;
+import com.google.gson.JsonObject;
+import kr.syeyoung.dungeonsguide.config.guiconfig.ConfigPanelCreator;
+import kr.syeyoung.dungeonsguide.config.guiconfig.MFeatureEdit;
+import kr.syeyoung.dungeonsguide.config.guiconfig.MParameterEdit;
+import kr.syeyoung.dungeonsguide.config.guiconfig.RootConfigPanel;
+import kr.syeyoung.dungeonsguide.features.FeatureParameter;
+import kr.syeyoung.dungeonsguide.features.SimpleFeature;
+import kr.syeyoung.dungeonsguide.features.text.PanelTextParameterConfig;
+import kr.syeyoung.dungeonsguide.features.text.StyledTextRenderer;
+import kr.syeyoung.dungeonsguide.features.text.TextHUDFeature;
+import kr.syeyoung.dungeonsguide.gui.MPanel;
+import kr.syeyoung.dungeonsguide.gui.elements.MStringSelectionButton;
+import lombok.Data;
+import lombok.Getter;
+import lombok.RequiredArgsConstructor;
+
+import java.awt.*;
+import java.util.Arrays;
+import java.util.stream.Collectors;
+
+public class FeaturePathfindStrategy extends SimpleFeature {
+ public FeaturePathfindStrategy() {
+ super("Dungeon Secrets", "Pathfind Algorithm", "Select pathfind algorithm used by paths", "secret.secretpathfind.algorithm", true);
+ this.parameters.put("strategy", new FeatureParameter<String>("strategy", "Pathfind Strategy", "Pathfind Strategy", "THETA_STAR", "string"));
+
+ }
+
+ @Override
+ public boolean isDisyllable() {
+ return false;
+ }
+
+ @Override
+ public String getEditRoute(RootConfigPanel rootConfigPanel) {
+ ConfigPanelCreator.map.put("base." + getKey() , new Supplier<MPanel>() {
+ @Override
+ public MPanel get() {
+
+ MFeatureEdit featureEdit = new MFeatureEdit(FeaturePathfindStrategy.this, rootConfigPanel);
+ PathfindStrategy alignment = getPathfindStrat();
+ MStringSelectionButton mStringSelectionButton = new MStringSelectionButton(Arrays.stream(PathfindStrategy.values()).map(Enum::name).collect(Collectors.toList()), alignment.name()) {
+ @Override
+ public Dimension getPreferredSize() {
+ return new Dimension(150, 20);
+ }
+ };
+ mStringSelectionButton.setOnUpdate(() -> {
+ FeaturePathfindStrategy.this.<String>getParameter("strategy").setValue(mStringSelectionButton.getSelected());
+ FeaturePathfindStrategy.this.<String>getParameter("strategy").setDescription(getPathfindStrat().getDescription());
+ featureEdit.removeParameterEdit(null);
+ });
+ featureEdit.addParameterEdit("strategy", new MParameterEdit(FeaturePathfindStrategy.this, FeaturePathfindStrategy.this.<String>getParameter("strategy"), rootConfigPanel, mStringSelectionButton, (a) -> false));
+
+ for (FeatureParameter parameter: getParameters()) {
+ if (parameter.getKey().equals("strategy")) continue;
+ featureEdit.addParameterEdit(parameter.getKey(), new MParameterEdit(FeaturePathfindStrategy.this, parameter, rootConfigPanel));
+ }
+ return featureEdit;
+ }
+ });
+ return "base." + getKey() ;
+ }
+
+ @Getter @RequiredArgsConstructor
+ public enum PathfindStrategy {
+ THETA_STAR("The default pathfinding algorithm. It will generate sub-optimal path quickly."),
+ A_STAR_DIAGONAL("New pathfinding algorithm. It will generate path that looks like the one JPS generates"),
+ A_STAR_FINE_GRID("New pathfinding algorithm. It will generate path that kind of looks like stair"),
+ JPS_LEGACY("The improved pathfinding algorithm. Not suggested for usage. It will have problems on diagonal movements, thus giving wrong routes"),
+ A_STAR_LEGACY("The first pathfinding algorithm. It may have problem on navigating through stairs. This is the one used by Minecraft for mob pathfind.");
+
+ private final String description;
+ }
+
+ @Override
+ public void loadConfig(JsonObject jsonObject) {
+ super.loadConfig(jsonObject);
+ FeaturePathfindStrategy.PathfindStrategy alignment;
+ try {
+ alignment = PathfindStrategy.valueOf(FeaturePathfindStrategy.this.<String>getParameter("strategy").getValue());
+ } catch (Exception e) {alignment = PathfindStrategy.THETA_STAR;}
+ FeaturePathfindStrategy.this.<String>getParameter("strategy").setValue(alignment.name());
+ FeaturePathfindStrategy.this.<String>getParameter("strategy").setDescription(alignment.getDescription());
+ }
+
+ public PathfindStrategy getPathfindStrat() {
+ return PathfindStrategy.valueOf(FeaturePathfindStrategy.this.<String>getParameter("strategy").getValue());
+ }
+}
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/gui/elements/MStringSelectionButton.java b/src/main/java/kr/syeyoung/dungeonsguide/gui/elements/MStringSelectionButton.java
index 7666865a..f2dcadce 100755
--- a/src/main/java/kr/syeyoung/dungeonsguide/gui/elements/MStringSelectionButton.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/gui/elements/MStringSelectionButton.java
@@ -54,8 +54,8 @@ public class MStringSelectionButton extends MPanel {
dec.setOnActionPerformed(new Runnable() {
@Override
public void run() {
- selectedIndex++;
- if (selectedIndex >= possible.size()) selectedIndex = 0;
+ selectedIndex --;
+ if (selectedIndex < 0) selectedIndex = possible.size() - 1;
updateSelected();
onUpdate.run();
}
@@ -63,8 +63,8 @@ public class MStringSelectionButton extends MPanel {
inc.setOnActionPerformed(new Runnable() {
@Override
public void run() {
- selectedIndex --;
- if (selectedIndex < 0) selectedIndex = possible.size() - 1;
+ selectedIndex++;
+ if (selectedIndex >= possible.size()) selectedIndex = 0;
updateSelected();
onUpdate.run();
}
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarCornerCut.java
new file mode 100644
index 00000000..ee71f90b
--- /dev/null
+++ b/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/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/AStarFineGrid.java
new file mode 100644
index 00000000..94fa8a87
--- /dev/null
+++ b/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/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java
index 6c88d4cf..5d48ccb2 100644
--- a/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java
+++ b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/JPSPathfinder.java
@@ -72,7 +72,7 @@ public class JPSPathfinder {
private LinkedList<Vec3> route = new LinkedList<>();
@Getter
- private PriorityQueue<Node> open = new PriorityQueue<>(Comparator.comparing((Node a) -> a.f).thenComparing(a -> a.x).thenComparing(a -> a.y).thenComparing(a -> a.z));
+ 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;
@@ -111,11 +111,11 @@ public class JPSPathfinder {
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 + 1, (int)from.zCoord * 2 + 1));
+ 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;
+ long forceEnd = System.currentTimeMillis() + timeout + 999999999L;
while(!open.isEmpty()) {
if (forceEnd < System.currentTimeMillis() && timeout != -1) break;
Node n = open.poll();
@@ -263,9 +263,13 @@ public class JPSPathfinder {
}
}
} else if (determinant == 2) {
- if ((dx != 0 && dungeonRoom.isBlocked(nx , y , z ) && !dungeonRoom.isBlocked(nx + dx, y , z))
- || (dy != 0 && dungeonRoom.isBlocked(x , ny , z) && !dungeonRoom.isBlocked(x , ny+dy , z))
- || (dz != 0 && dungeonRoom.isBlocked(x , y , nz ) && !dungeonRoom.isBlocked(x , y , nz+dz))) return openNode(nx,ny,nz);
+ 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);
diff --git a/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java
new file mode 100644
index 00000000..4e16cd4d
--- /dev/null
+++ b/src/main/java/kr/syeyoung/dungeonsguide/pathfinding/ThetaStar.java
@@ -0,0 +1,212 @@
+/*
+ * 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;
+ System.out.println("Route len: "+route.size());
+ 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;
+ }
+}