Improvement: Area Navigation updates (#2537)

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

3 files changed, 80 insertions, 21 deletions

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