Improvement: Area Navigation updates (#2537)

Co-authored-by: nea <nea@nea.moe>
Co-authored-by: hannibal2 <24389977+hannibal00212@users.noreply.github.com>

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))
+    }
+
+}