diff options
Diffstat (limited to 'src/main')
14 files changed, 429 insertions, 77 deletions
diff --git a/src/main/java/at/hannibal2/skyhanni/config/commands/Commands.kt b/src/main/java/at/hannibal2/skyhanni/config/commands/Commands.kt index d0f58f082..3f2ddace6 100644 --- a/src/main/java/at/hannibal2/skyhanni/config/commands/Commands.kt +++ b/src/main/java/at/hannibal2/skyhanni/config/commands/Commands.kt @@ -77,7 +77,6 @@ import at.hannibal2.skyhanni.features.rift.area.westvillage.VerminTracker import at.hannibal2.skyhanni.features.rift.everywhere.PunchcardHighlight import at.hannibal2.skyhanni.features.slayer.SlayerProfitTracker import at.hannibal2.skyhanni.test.DebugCommand -import at.hannibal2.skyhanni.test.GraphEditor import at.hannibal2.skyhanni.test.PacketTest import at.hannibal2.skyhanni.test.SkyBlockIslandTest import at.hannibal2.skyhanni.test.SkyHanniConfigSearchResetCommand @@ -92,6 +91,7 @@ import at.hannibal2.skyhanni.test.command.CopyScoreboardCommand import at.hannibal2.skyhanni.test.command.TestChatCommand import at.hannibal2.skyhanni.test.command.TrackParticlesCommand import at.hannibal2.skyhanni.test.command.TrackSoundsCommand +import at.hannibal2.skyhanni.test.graph.GraphEditor import at.hannibal2.skyhanni.utils.APIUtil import at.hannibal2.skyhanni.utils.ChatUtils import at.hannibal2.skyhanni.utils.ExtendedChatColor diff --git a/src/main/java/at/hannibal2/skyhanni/config/features/dev/GraphConfig.java b/src/main/java/at/hannibal2/skyhanni/config/features/dev/GraphConfig.java index acf9ac67d..dda1ddb1e 100644 --- a/src/main/java/at/hannibal2/skyhanni/config/features/dev/GraphConfig.java +++ b/src/main/java/at/hannibal2/skyhanni/config/features/dev/GraphConfig.java @@ -33,6 +33,11 @@ public class GraphConfig { public int selectKey = -98; @Expose + @ConfigOption(name = "Select near look", desc = "Select the node closest to where you are looking.") + @ConfigEditorKeybind(defaultKey = Keyboard.KEY_NONE) + public int selectRaycastKey = Keyboard.KEY_NONE; + + @Expose @ConfigOption(name = "Connect Key", desc = "Connect the nearest node with the active node. If the nodes are already connected removes the connection.") @ConfigEditorKeybind(defaultKey = Keyboard.KEY_C) public int connectKey = Keyboard.KEY_C; diff --git a/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt b/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt index 0b173db46..ca3143b95 100644 --- a/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt +++ b/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt @@ -45,13 +45,14 @@ import kotlin.math.abs * 12 starter NPC's * diana * farming: - * pelt farming + * pelt farming area * rift: * enigma souls * eyes * big quests * montezuma souls * blood effigies + * avoid area around enderman * spider: * relicts + throw spot * dwarven mines: diff --git a/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt b/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt index 8c63be891..b9ad1251c 100644 --- a/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt +++ b/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt @@ -10,6 +10,7 @@ import com.google.gson.annotations.Expose import com.google.gson.stream.JsonToken import java.util.PriorityQueue +// TODO: This class should be disambiguated into a NodePath and a Graph class @JvmInline value class Graph( @Expose val nodes: List<GraphNode>, @@ -49,7 +50,7 @@ value class Graph( out.name("Name").value(it) } - it.tagNames?.takeIf { it.isNotEmpty() }?.let { + it.tagNames.takeIf { list -> list.isNotEmpty() }?.let { out.name("Tags") out.beginArray() for (tagName in it) { @@ -79,8 +80,8 @@ value class Graph( reader.beginObject() var position: LorenzVec? = null var name: String? = null - var tags: List<String>? = null - var neighbors = mutableListOf<Pair<Int, Double>>() + var tags = emptyList<String>() + val neighbors = mutableListOf<Pair<Int, Double>>() while (reader.hasNext()) { if (reader.peek() != JsonToken.NAME) { reader.skipValue() @@ -140,10 +141,10 @@ value class Graph( } // The node object that gets parsed from/to json -class GraphNode(val id: Int, val position: LorenzVec, val name: String? = null, val tagNames: List<String>? = null) { +class GraphNode(val id: Int, val position: LorenzVec, val name: String? = null, val tagNames: List<String> = emptyList()) { val tags: List<GraphNodeTag> by lazy { - tagNames?.mapNotNull { GraphNodeTag.byId(it) } ?: emptyList() + tagNames.mapNotNull { GraphNodeTag.byId(it) } } /** Keys are the neighbours and value the edge weight (e.g. Distance) */ @@ -167,18 +168,50 @@ class GraphNode(val id: Int, val position: LorenzVec, val name: String? = null, fun Graph.findShortestPathAsGraph(start: GraphNode, end: GraphNode): Graph = this.findShortestPathAsGraphWithDistance(start, end).first -fun Graph.findShortestPathAsGraphWithDistance(start: GraphNode, end: GraphNode): Pair<Graph, Double> { +data class DijkstraTree( + val origin: GraphNode, + /** + * A map of distances between the [origin] and each node in a graph. This distance map is only accurate for nodes closer to the + * origin than the [lastVisitedNode]. In case there is no early bailout, this map will be accurate for all nodes in the graph. + */ + val distances: Map<GraphNode, Double>, + /** + * A map of nodes to the neighbouring node that is the quickest path towards the origin (the neighbouring node that has the lowest value + * in [distances]) + */ + val towardsOrigin: Map<GraphNode, GraphNode>, + /** + * This is either the furthest away node in the graph, or the node that was bailed out on early because it fulfilled the search + * condition. In case the search condition matches nothing, this will *still* be the furthest away node, so an additional check might be + * necessary. + */ + val lastVisitedNode: GraphNode, +) + +/** + * Find a tree of distances to the [start] node using dijkstra's algorithm. + */ +fun Graph.findDijkstraDistances( + start: GraphNode, + /** + * Bail out early before collecting all the distances to all nodes in the graph. This will not collect valid distance data for *all* + * nodes for which bailout matches, but only the closest one. + */ + bailout: (GraphNode) -> Boolean, +): DijkstraTree { val distances = mutableMapOf<GraphNode, Double>() val previous = mutableMapOf<GraphNode, GraphNode>() val visited = mutableSetOf<GraphNode>() val queue = PriorityQueue<GraphNode>(compareBy { distances.getOrDefault(it, Double.MAX_VALUE) }) + var lastVisitedNode: GraphNode = start distances[start] = 0.0 queue.add(start) while (queue.isNotEmpty()) { val current = queue.poll() - if (current == end) break + lastVisitedNode = current + if (bailout(current)) break visited.add(current) @@ -194,16 +227,34 @@ fun Graph.findShortestPathAsGraphWithDistance(start: GraphNode, end: GraphNode): } } - return Graph( - buildList { - var current = end - while (current != start) { - add(current) - current = previous[current] ?: return Graph(emptyList()) to 0.0 - } - add(start) - }.reversed(), - ) to distances[end]!! + return DijkstraTree( + start, + distances, + previous, + lastVisitedNode, + ) +} + +fun Graph.findAllShortestDistances(start: GraphNode): DijkstraTree { + return findDijkstraDistances(start) { false } +} + +fun DijkstraTree.findPathToDestination(end: GraphNode): Pair<Graph, Double> { + val distances = this + val reversePath = buildList { + var current = end + while (true) { + add(current) + if (current == distances.origin) break + current = distances.towardsOrigin[current] ?: return Graph(emptyList()) to 0.0 + } + } + return Graph(reversePath.reversed()) to distances.distances[end]!! +} + +fun Graph.findShortestPathAsGraphWithDistance(start: GraphNode, end: GraphNode): Pair<Graph, Double> { + val distances = findDijkstraDistances(start) { it == end } + return distances.findPathToDestination(end) } fun Graph.findShortestPath(start: GraphNode, end: GraphNode): List<LorenzVec> = this.findShortestPathAsGraph(start, end).toPositionsList() diff --git a/src/main/java/at/hannibal2/skyhanni/data/model/GraphNodeTag.kt b/src/main/java/at/hannibal2/skyhanni/data/model/GraphNodeTag.kt index e1fa3317a..e70786137 100644 --- a/src/main/java/at/hannibal2/skyhanni/data/model/GraphNodeTag.kt +++ b/src/main/java/at/hannibal2/skyhanni/data/model/GraphNodeTag.kt @@ -6,7 +6,7 @@ import at.hannibal2.skyhanni.utils.LorenzColor enum class GraphNodeTag( val internalName: String, val color: LorenzColor, - val cleanName: String, + cleanName: String, val description: String, val onlyIsland: IslandType? = null, ) { @@ -17,13 +17,17 @@ enum class GraphNodeTag( AREA("area", LorenzColor.DARK_GREEN, "Area", "A big SkyBlock area."), SMALL_AREA("small_area", LorenzColor.GREEN, "Small Area", "A small SkyBlock area, e.g. a house."), POI("poi", LorenzColor.WHITE, "PoI", "Point of interest."), - LAUNCH_PAD("launch", LorenzColor.WHITE, "Launch Pad", "Slime blocks sending you to another server."), +// LAUNCH_PAD("launch", LorenzColor.WHITE, "Launch Pad", "Slime blocks sending you to another server."), + TELEPORT("teleport", LorenzColor.BLUE, "Teleport", "A spot from/to teleport."), // on multiple islands ROMEO("romeo", LorenzColor.WHITE, "Romeo & Juliette Quest", "Blocks related to the Romeo and Juliette/Ring of Love quest line."), RACE("race", LorenzColor.WHITE, "Race Start/Stop", "A race start or stop point."), - SLAYER("slayer", LorenzColor.WHITE, "Slayer", "A Slayer area"), + SLAYER("slayer", LorenzColor.RED, "Slayer", "A Slayer area"), HOPPITY("hoppity", LorenzColor.AQUA, "Hoppity Egg", "An egg location in Hoppity's Hunt."), + GRIND_MOBS("grind_mobs", LorenzColor.RED, "Grind Mobs", "A spot where combat mobs spawn that can be killed."), + GRIND_ORES("grind_ores", LorenzColor.DARK_AQUA, "Grind Ores", "A spot where mining ores spawn that can be mines."), + GRIND_CROPS("grind_crops", LorenzColor.DARK_GREEN, "Grind Crops", "A spot where farming crops spawn that can be farmed."), // hoppity // Hub @@ -52,6 +56,9 @@ enum class GraphNodeTag( // Crimson Isles CRIMSON_MINIBOSS("crimson_miniboss", LorenzColor.RED, "Crimson Miniboss", "Mini bosses in Crimson Isle.", onlyIsland = IslandType.CRIMSON_ISLE), + // The End + END_GOLEM("end_golem", LorenzColor.RED, "Golem Spawn", "A spot where the golem in the end spawns", onlyIsland = IslandType.THE_END), + ; val displayName: String = color.getChatColor() + cleanName diff --git a/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt b/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt index d85b34cc6..311af056e 100644 --- a/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt +++ b/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt @@ -6,7 +6,6 @@ import at.hannibal2.skyhanni.data.model.Graph import at.hannibal2.skyhanni.data.model.GraphNode import at.hannibal2.skyhanni.data.model.GraphNodeTag import at.hannibal2.skyhanni.data.model.TextInput -import at.hannibal2.skyhanni.data.model.findShortestPathAsGraphWithDistance import at.hannibal2.skyhanni.events.ConfigLoadEvent import at.hannibal2.skyhanni.events.EntityMoveEvent import at.hannibal2.skyhanni.events.GuiRenderEvent @@ -19,6 +18,7 @@ import at.hannibal2.skyhanni.utils.CollectionUtils.addSearchString import at.hannibal2.skyhanni.utils.CollectionUtils.sorted import at.hannibal2.skyhanni.utils.ColorUtils.toChromaColor import at.hannibal2.skyhanni.utils.ConditionalUtils +import at.hannibal2.skyhanni.utils.GraphUtils import at.hannibal2.skyhanni.utils.LocationUtils.canBeSeen import at.hannibal2.skyhanni.utils.LocationUtils.distanceToPlayer import at.hannibal2.skyhanni.utils.LorenzColor @@ -65,19 +65,10 @@ object IslandAreas { val graph = IslandGraphs.currentIslandGraph ?: return val closedNote = IslandGraphs.closedNote ?: return - val paths = mutableMapOf<GraphNode, Graph>() - - val map = mutableMapOf<GraphNode, Double>() - for (graphNode in graph.nodes) { - if (graphNode.getAreaTag() == null) continue - val (path, distance) = graph.findShortestPathAsGraphWithDistance(closedNote, graphNode) - paths[graphNode] = path - map[graphNode] = distance - } + val (paths, map) = GraphUtils.findFastestPaths(graph, closedNote) { it.getAreaTag() != null } this.paths = paths val finalNodes = mutableMapOf<GraphNode, Double>() - val alreadyFoundAreas = mutableListOf<String>() for ((node, distance) in map.sorted()) { val areaName = node.name ?: continue @@ -271,8 +262,8 @@ object IslandAreas { private val allAreas = listOf(GraphNodeTag.AREA, GraphNodeTag.SMALL_AREA) private val onlyLargeAreas = listOf(GraphNodeTag.AREA) - private fun GraphNode.getAreaTag(): GraphNodeTag? = tags.firstOrNull { - it in (if (config.includeSmallAreas) allAreas else onlyLargeAreas) + fun GraphNode.getAreaTag(ignoreConfig: Boolean = false): GraphNodeTag? = tags.firstOrNull { + it in (if (config.includeSmallAreas || ignoreConfig) allAreas else onlyLargeAreas) } private fun setTarget(node: GraphNode) { diff --git a/src/main/java/at/hannibal2/skyhanni/mixins/transformers/MixinKeyBinding.java b/src/main/java/at/hannibal2/skyhanni/mixins/transformers/MixinKeyBinding.java index a070f5e89..01efda5ce 100644 --- a/src/main/java/at/hannibal2/skyhanni/mixins/transformers/MixinKeyBinding.java +++ b/src/main/java/at/hannibal2/skyhanni/mixins/transformers/MixinKeyBinding.java @@ -2,7 +2,7 @@ package at.hannibal2.skyhanni.mixins.transformers; import at.hannibal2.skyhanni.data.model.TextInput; import at.hannibal2.skyhanni.features.garden.farming.GardenCustomKeybinds; -import at.hannibal2.skyhanni.test.GraphEditor; +import at.hannibal2.skyhanni.test.graph.GraphEditor; import net.minecraft.client.settings.KeyBinding; import org.spongepowered.asm.mixin.Mixin; import org.spongepowered.asm.mixin.injection.At; diff --git a/src/main/java/at/hannibal2/skyhanni/test/SkyHanniDebugsAndTests.kt b/src/main/java/at/hannibal2/skyhanni/test/SkyHanniDebugsAndTests.kt index 5b7333189..045ce5bce 100644 --- a/src/main/java/at/hannibal2/skyhanni/test/SkyHanniDebugsAndTests.kt +++ b/src/main/java/at/hannibal2/skyhanni/test/SkyHanniDebugsAndTests.kt @@ -131,36 +131,13 @@ object SkyHanniDebugsAndTests { } fun testCommand(args: Array<String>) { + SkyHanniMod.coroutineScope.launch { + asyncTest() + } + } + private fun asyncTest() { -// val a = Thread { OSUtils.copyToClipboard("123") } -// val b = Thread { OSUtils.copyToClipboard("456") } -// a.start() -// b.start() - -// for ((i, s) in ScoreboardData.siedebarLinesFormatted().withIndex()) { -// println("$i: '$s'") -// } - -// val name = args[0] -// val pitch = args[1].toFloat() -// val sound = SoundUtils.createSound("note.harp", 1.35f) -// val sound = SoundUtils.createSound("random.orb", 11.2f) -// SoundUtils.createSound(name, pitch).playSound() - -// a = args[0].toDouble() -// b = args[1].toDouble() -// c = args[2].toDouble() - -// for (line in getPlayerTabOverlay().footer.unformattedText -// .split("\n")) { -// println("footer: '$line'") -// } -// -// -// for (line in TabListUtils.getTabList()) { -// println("tablist: '$line'") -// } } fun findNullConfig(args: Array<String>) { diff --git a/src/main/java/at/hannibal2/skyhanni/test/GraphEditor.kt b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphEditor.kt index d4038162f..1aefeda52 100644 --- a/src/main/java/at/hannibal2/skyhanni/test/GraphEditor.kt +++ b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphEditor.kt @@ -1,4 +1,4 @@ -package at.hannibal2.skyhanni.test +package at.hannibal2.skyhanni.test.graph import at.hannibal2.skyhanni.SkyHanniMod import at.hannibal2.skyhanni.data.IslandGraphs @@ -26,6 +26,7 @@ import at.hannibal2.skyhanni.utils.LorenzUtils import at.hannibal2.skyhanni.utils.LorenzVec import at.hannibal2.skyhanni.utils.NumberUtil.addSeparators import at.hannibal2.skyhanni.utils.OSUtils +import at.hannibal2.skyhanni.utils.RaycastUtils import at.hannibal2.skyhanni.utils.RenderUtils.draw3DLine_nea import at.hannibal2.skyhanni.utils.RenderUtils.drawDynamicText import at.hannibal2.skyhanni.utils.RenderUtils.drawWaypointFilled @@ -127,6 +128,7 @@ object GraphEditor { if (!inEditMode && !inTextMode) { add("§ePlace: §6${KeyboardManager.getKeyName(config.placeKey)}") add("§eSelect: §6${KeyboardManager.getKeyName(config.selectKey)}") + add("§eSelect (Look): §6${KeyboardManager.getKeyName(config.selectRaycastKey)}") add("§eConnect: §6${KeyboardManager.getKeyName(config.connectKey)}") add("§eTest: §6${KeyboardManager.getKeyName(config.dijkstraKey)}") add("§eVision: §6${KeyboardManager.getKeyName(config.throughBlocksKey)}") @@ -259,7 +261,9 @@ object GraphEditor { } } - private fun chatAtDisable() = ChatUtils.clickableChat("Graph Editor is now inactive. §lClick to activate.", ::commandIn) + private fun chatAtDisable() = ChatUtils.clickableChat("Graph Editor is now inactive. §lClick to activate.", + GraphEditor::commandIn + ) private fun input() { if (LorenzUtils.isAnyGuiActive()) return @@ -346,13 +350,35 @@ object GraphEditor { closedNode } } + if (config.selectRaycastKey.isKeyClicked()) { + val playerRay = RaycastUtils.createPlayerLookDirectionRay() + var minimumDistance = Double.MAX_VALUE + var minimumNode: GraphingNode? = null + for (node in nodes) { + val nodeCenterPosition = node.position.add(0.5, 0.5, 0.5) + val distance = RaycastUtils.findDistanceToRay(playerRay, nodeCenterPosition) + if (distance > minimumDistance) { + continue + } + if (minimumDistance > 1.0) { + minimumNode = node + minimumDistance = distance + continue + } + if (minimumNode == null || minimumNode.position.distanceSqToPlayer() > node.position.distanceSqToPlayer()) { + minimumNode = node + minimumDistance = distance + } + } + activeNode = minimumNode + } if (activeNode != closedNode && config.connectKey.isKeyClicked()) { val edge = getEdgeIndex(activeNode, closedNode) if (edge == null) { addEdge(activeNode, closedNode) feedBackInTutorial("Added new edge.") } else { - this.edges.removeAt(edge) + edges.removeAt(edge) checkDissolve() selectedEdge = findEdgeBetweenActiveAndClosed() feedBackInTutorial("Removed edge.") @@ -405,6 +431,7 @@ object GraphEditor { val compileGraph = compileGraph() if (config.useAsIslandArea) { IslandGraphs.setNewGraph(compileGraph) + GraphEditorBugFinder.runTests() } val json = compileGraph.toJson() OSUtils.copyToClipboard(json) @@ -457,7 +484,7 @@ object GraphEditor { nodes.remove(closedNode) edges.removeIf { it.isInEdge(closedNode) } if (closedNode == activeNode) activeNode = null - this.closedNode = null + GraphEditor.closedNode = null return } } @@ -505,7 +532,7 @@ object GraphEditor { prune() val indexedTable = nodes.mapIndexed { index, node -> node.id to index }.toMap() val nodes = nodes.mapIndexed { index, it -> GraphNode(index, it.position, it.name, it.tags.mapNotNull { it.internalName }) } - val neighbours = this.nodes.map { node -> + val neighbours = GraphEditor.nodes.map { node -> edges.filter { it.isInEdge(node) }.map { edge -> val otherNode = if (node == edge.node1) edge.node2 else edge.node1 nodes[indexedTable[otherNode.id]!!] to node.position.distance(otherNode.position) @@ -523,7 +550,7 @@ object GraphEditor { it.id, it.position, it.name, - it.tagNames?.mapNotNull { GraphNodeTag.byId(it) }?.toMutableList() ?: mutableListOf(), + it.tagNames.mapNotNull { tag -> GraphNodeTag.byId(tag) }.toMutableList(), ) }, ) diff --git a/src/main/java/at/hannibal2/skyhanni/test/graph/GraphEditorBugFinder.kt b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphEditorBugFinder.kt new file mode 100644 index 000000000..aee75ec5f --- /dev/null +++ b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphEditorBugFinder.kt @@ -0,0 +1,95 @@ +package at.hannibal2.skyhanni.test.graph + +import at.hannibal2.skyhanni.SkyHanniMod +import at.hannibal2.skyhanni.data.IslandGraphs +import at.hannibal2.skyhanni.data.model.GraphNode +import at.hannibal2.skyhanni.events.LorenzRenderWorldEvent +import at.hannibal2.skyhanni.features.misc.IslandAreas.getAreaTag +import at.hannibal2.skyhanni.test.graph.GraphEditor.distanceSqToPlayer +import at.hannibal2.skyhanni.utils.GraphUtils +import at.hannibal2.skyhanni.utils.LorenzVec +import at.hannibal2.skyhanni.utils.RenderUtils.drawDynamicText +import kotlinx.coroutines.launch +import net.minecraftforge.fml.common.eventhandler.SubscribeEvent +import java.awt.Color + +// Trying to find errors in Area Graph for the current graph editor instance +object GraphEditorBugFinder { + private var errorsInWorld = emptyMap<LorenzVec, String>() + + fun runTests() { + SkyHanniMod.coroutineScope.launch { + asyncTest() + } + } + + private fun asyncTest() { + val graph = IslandGraphs.currentIslandGraph ?: return + val errorsInWorld: MutableMap<LorenzVec, String> = mutableMapOf() + val nodes = graph.nodes + + val nearestArea = mutableMapOf<GraphNode, GraphNode>() + for (node in nodes) { + val pathToNearestArea = GraphUtils.findFastestPath(graph, node) { it.getAreaTag(ignoreConfig = true) != null }?.first + if (pathToNearestArea == null) { + continue + } + val areaNode = pathToNearestArea.lastOrNull() ?: error("Empty path to nearest area") + nearestArea[node] = areaNode + } + var bugs = 0 + for (node in nodes) { + val areaNode = nearestArea[node]?.name ?: continue + for (neighbour in node.neighbours.keys) { + val neighbouringAreaNode = nearestArea[neighbour]?.name ?: continue + if (neighbouringAreaNode == areaNode) continue + if ((null == node.getAreaTag(ignoreConfig = true))) { + bugs++ + errorsInWorld[node.position] = "§cConflicting areas $areaNode and $neighbouringAreaNode" + } + } + } + for (node in nodes) { + val nameNull = node.name.isNullOrBlank() + val tagsEmpty = node.tags.isEmpty() + if (nameNull > tagsEmpty) { + errorsInWorld[node.position] = "§cMissing name despite having tags" + bugs++ + } + if (tagsEmpty > nameNull) { + errorsInWorld[node.position] = "§cMissing tags despite having name" + bugs++ + } + } + + val clusters = GraphUtils.findDisjointClusters(graph) + if (clusters.size > 1) { + val closestCluster = clusters.minBy { it.minOf { it.position.distanceSqToPlayer() } } + val foreignClusters = clusters.filter { it !== closestCluster } + val closestForeignNodes = foreignClusters.map { network -> network.minBy { it.position.distanceSqToPlayer() } } + closestForeignNodes.forEach { + errorsInWorld[it.position] = "§cDisjoint node network" + bugs++ + } + val closestForeignNode = closestForeignNodes.minBy { it.position.distanceSqToPlayer() } + val closestNodeToForeignNode = closestCluster.minBy { it.position.distanceSq(closestForeignNode.position) } + IslandGraphs.pathFind(closestNodeToForeignNode.position, Color.RED) + } + + println("found $bugs bugs!") + this.errorsInWorld = errorsInWorld + if (clusters.size <= 1) { + IslandGraphs.pathFind(errorsInWorld.keys.minByOrNull { it.distanceSqToPlayer() } ?: return, Color.RED) + } + } + + @SubscribeEvent + fun onRenderWorld(event: LorenzRenderWorldEvent) { + if (!isEnabled()) return + + for ((location, text) in errorsInWorld) { + event.drawDynamicText(location, text, 1.5) + } + } + fun isEnabled() = GraphEditor.isEnabled() +} diff --git a/src/main/java/at/hannibal2/skyhanni/test/GraphNodeEditor.kt b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphNodeEditor.kt index f541b16e3..e6c4536d8 100644 --- a/src/main/java/at/hannibal2/skyhanni/test/GraphNodeEditor.kt +++ b/src/main/java/at/hannibal2/skyhanni/test/graph/GraphNodeEditor.kt @@ -1,10 +1,10 @@ -package at.hannibal2.skyhanni.test +package at.hannibal2.skyhanni.test.graph import at.hannibal2.skyhanni.data.model.GraphNodeTag import at.hannibal2.skyhanni.data.model.TextInput import at.hannibal2.skyhanni.events.GuiRenderEvent import at.hannibal2.skyhanni.skyhannimodule.SkyHanniModule -import at.hannibal2.skyhanni.test.GraphEditor.distanceSqToPlayer +import at.hannibal2.skyhanni.test.graph.GraphEditor.distanceSqToPlayer import at.hannibal2.skyhanni.utils.CollectionUtils.addString import at.hannibal2.skyhanni.utils.KeyboardManager import at.hannibal2.skyhanni.utils.LorenzUtils @@ -29,12 +29,12 @@ object GraphNodeEditor { private val textInput = TextInput() private var nodesDisplay = emptyList<Renderable>() private var lastUpdate = SimpleTimeMark.farPast() + private val tagsToShow: MutableList<GraphNodeTag> = GraphNodeTag.entries.toMutableList() @SubscribeEvent fun onGuiRender(event: GuiRenderEvent) { if (!isEnabled()) return - config.namedNodesList.renderRenderables( getNodeNames(), posLabel = "Graph Nodes List", @@ -52,15 +52,66 @@ object GraphNodeEditor { lastUpdate = SimpleTimeMark.now() nodesDisplay = buildList { val list = drawNodeNames() - val size = list.size - addString("§eGraph Nodes: $size") - val height = (size * 10).coerceAtMost(250) + val total = GraphEditor.nodes.count { it.name?.isNotBlank() ?: false } + val shown = list.size + add( + Renderable.clickAndHover( + "§eGraph Nodes: $shown/$total", + listOf("§eClick to toggle node tags!"), + onClick = { + updateToggleTags() + }, + ), + ) + val height = (shown * 10).coerceAtMost(250) if (list.isNotEmpty()) { add(list.buildSearchableScrollable(height, textInput, scrollValueNodes, velocity = 10.0)) } } } + private fun updateToggleTags() { + lastUpdate = SimpleTimeMark.now() + 60.seconds + nodesDisplay = buildList { + addString("§eToggle Visible Tags") + for (tag in GraphNodeTag.entries) { + val isVisible = tag in tagsToShow + val nodes = GraphEditor.nodes.count { tag in it.tags } + val visibilityText = if (isVisible) " §aVisible" else " §7Invisible" + val name = " - ${tag.displayName} §8($nodes nodes) $visibilityText" + add( + Renderable.clickAndHover( + name, + listOf("§eClick to " + (if (isVisible) "hide" else "show") + " nodes with this tag!"), + onClick = { + toggleTag(tag) + updateToggleTags() + }, + ), + ) + } + addString("") + add( + Renderable.clickAndHover( + "§cGo Back!", + tips = listOf("§eClick to go back to the node list!"), + onClick = { + updateNodeNames() + }, + ), + ) + } + + } + + private fun toggleTag(tag: GraphNodeTag) { + if (tag in tagsToShow) { + tagsToShow.remove(tag) + } else { + tagsToShow.add(tag) + } + } + private fun updateTagView(node: GraphingNode) { lastUpdate = SimpleTimeMark.now() + 60.seconds nodesDisplay = buildList { @@ -123,7 +174,10 @@ object GraphNodeEditor { private fun drawNodeNames(): List<Searchable> = buildList { for ((node, distance: Double) in GraphEditor.nodes.map { it to it.position.distanceSqToPlayer() }.sortedBy { it.second }) { - val name = node.name?.takeIf { !it.isBlank() } ?: continue + if (node.tags.isNotEmpty()) { + if (!node.tags.any { it in tagsToShow }) continue + } + val name = node.name?.takeIf { it.isNotBlank() } ?: continue val color = if (node == GraphEditor.activeNode) "§a" else "§7" val distanceFormat = sqrt(distance).toInt().addSeparators() val tagText = node.tags.let { tags -> diff --git a/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt b/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt new file mode 100644 index 000000000..4a245a894 --- /dev/null +++ b/src/main/java/at/hannibal2/skyhanni/utils/GraphUtils.kt @@ -0,0 +1,68 @@ +package at.hannibal2.skyhanni.utils + +import at.hannibal2.skyhanni.data.model.Graph +import at.hannibal2.skyhanni.data.model.GraphNode +import at.hannibal2.skyhanni.data.model.findAllShortestDistances +import at.hannibal2.skyhanni.data.model.findDijkstraDistances +import at.hannibal2.skyhanni.data.model.findPathToDestination +import java.util.Stack + +object GraphUtils { + /** + * Find the fastest path from [closestNode] to *any* node that matches [condition]. + */ + fun findFastestPath( + graph: Graph, + closestNode: GraphNode, + condition: (GraphNode) -> Boolean, + ): Pair<Graph, Double>? { + val distances = graph.findDijkstraDistances(closestNode, condition) + val entry = distances.lastVisitedNode.takeIf(condition) + return entry?.let { + distances.findPathToDestination(it) + } + } + + /** + * Find the fastest path from [closestNode] to *all* nodes that matches [condition]. + */ + fun findFastestPaths( + graph: Graph, + closestNode: GraphNode, + condition: (GraphNode) -> Boolean = { true }, + ): Pair<MutableMap<GraphNode, Graph>, MutableMap<GraphNode, Double>> { + val paths = mutableMapOf<GraphNode, Graph>() + + val map = mutableMapOf<GraphNode, Double>() + val distances = graph.findAllShortestDistances(closestNode) + for (graphNode in graph.nodes) { + if (!condition(graphNode)) continue + val (path, distance) = distances.findPathToDestination(graphNode) + paths[graphNode] = path + map[graphNode] = distance + } + return Pair(paths, map) + } + + /** + * Find all maximal sub graphs of the given graph which are not connected + */ + fun findDisjointClusters(graph: Graph): List<Set<GraphNode>> { + val universe = graph.toMutableSet() + val allClusters = mutableListOf<Set<GraphNode>>() + while (universe.isNotEmpty()) { + val cluster = mutableSetOf<GraphNode>() + allClusters.add(cluster) + val queue = Stack<GraphNode>() + queue.add(universe.first()) + while (queue.isNotEmpty()) { + val next = queue.pop() + universe.remove(next) + cluster.add(next) + queue.addAll(next.neighbours.keys) + queue.retainAll(universe) + } + } + return allClusters + } +} diff --git a/src/main/java/at/hannibal2/skyhanni/utils/LorenzVec.kt b/src/main/java/at/hannibal2/skyhanni/utils/LorenzVec.kt index 51bb8b72c..a573ed78d 100644 --- a/src/main/java/at/hannibal2/skyhanni/utils/LorenzVec.kt +++ b/src/main/java/at/hannibal2/skyhanni/utils/LorenzVec.kt @@ -9,6 +9,7 @@ import net.minecraft.util.BlockPos import net.minecraft.util.Rotations import net.minecraft.util.Vec3 import kotlin.math.abs +import kotlin.math.absoluteValue import kotlin.math.acos import kotlin.math.cos import kotlin.math.max @@ -126,6 +127,8 @@ data class LorenzVec( fun lengthSquared(): Double = x * x + y * y + z * z fun length(): Double = sqrt(this.lengthSquared()) + fun isNormalized(tolerance: Double = 0.01) = (lengthSquared() - 1.0).absoluteValue < tolerance + fun isZero(): Boolean = x == 0.0 && y == 0.0 && z == 0.0 fun clone(): LorenzVec = LorenzVec(x, y, z) diff --git a/src/main/java/at/hannibal2/skyhanni/utils/RaycastUtils.kt b/src/main/java/at/hannibal2/skyhanni/utils/RaycastUtils.kt new file mode 100644 index 000000000..d5aafdcd3 --- /dev/null +++ b/src/main/java/at/hannibal2/skyhanni/utils/RaycastUtils.kt @@ -0,0 +1,73 @@ +package at.hannibal2.skyhanni.utils + +import net.minecraft.client.Minecraft + +object RaycastUtils { + + data class Ray( + val origin: LorenzVec, + val direction: LorenzVec, + ) { + init { + require(direction.isNormalized()) + } + } + + data class Plane( + val origin: LorenzVec, + val normal: LorenzVec, + ) { + init { + require(normal.isNormalized()) + } + } + + fun createPlayerLookDirectionRay(): Ray { + return Ray( + LocationUtils.playerEyeLocation(), + Minecraft.getMinecraft().thePlayer.lookVec.toLorenzVec() + ) + } + + /** + * Create a plane that contains [point] and is orthogonal to [ray]. + */ + fun createOrthogonalPlaneToRayAtPoint( + ray: Ray, + point: LorenzVec, + ): Plane { + return Plane(point, ray.direction) + } + + /** + * Intersect a plane (of any orientation) with a ray. The ray and plane may not be parallel to each other. + */ + fun intersectPlaneWithRay(plane: Plane, ray: Ray): LorenzVec { +// require(plane.normal.dotProduct(ray.direction).absoluteValue != 0.0) + val intersectionPointDistanceAlongRay = + (plane.normal.dotProduct(plane.origin) - plane.normal.dotProduct(ray.origin)) / plane.normal.dotProduct(ray.direction) + return ray.origin + ray.direction.scale(intersectionPointDistanceAlongRay) + } + + /** + * Finds the distance between the given ray and the point. If the point is behind the ray origin (according to the ray's direction), + * returns [Double.MAX_VALUE] instead. + */ + fun findDistanceToRay(ray: Ray, point: LorenzVec): Double { + val plane = createOrthogonalPlaneToRayAtPoint(ray, point) + val intersectionPoint = intersectPlaneWithRay(plane, ray) + if ((intersectionPoint - ray.origin).dotProduct(ray.direction) < 0) return Double.MAX_VALUE + return intersectionPoint.distance(point) + } + + inline fun <T> createDistanceToRayEstimator(ray: Ray, crossinline position: (T) -> LorenzVec): (T) -> Double { + return { + findDistanceToRay(ray, position(it)) + } + } + + fun <T : Any> List<T>.findClosestPointToRay(ray: Ray, positionExtractor: (T) -> LorenzVec): T? { + return minByOrNull(createDistanceToRayEstimator(ray, positionExtractor)) + } + +} |