Feature: Graphs Pathfinding (#2468)

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

4 files changed, 340 insertions, 15 deletions

diff --git a/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt b/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt
new file mode 100644
index 000000000..02a065abe
--- /dev/null
+++ b/src/main/java/at/hannibal2/skyhanni/data/IslandGraphs.kt
@@ -0,0 +1,320 @@
+package at.hannibal2.skyhanni.data
+
+import at.hannibal2.skyhanni.SkyHanniMod
+import at.hannibal2.skyhanni.data.model.Graph
+import at.hannibal2.skyhanni.data.model.GraphNode
+import at.hannibal2.skyhanni.data.model.findShortestPathAsGraphWithDistance
+import at.hannibal2.skyhanni.data.repo.RepoUtils
+import at.hannibal2.skyhanni.events.IslandChangeEvent
+import at.hannibal2.skyhanni.events.LorenzRenderWorldEvent
+import at.hannibal2.skyhanni.events.LorenzTickEvent
+import at.hannibal2.skyhanni.events.LorenzWorldChangeEvent
+import at.hannibal2.skyhanni.events.RepositoryReloadEvent
+import at.hannibal2.skyhanni.features.misc.IslandAreas
+import at.hannibal2.skyhanni.skyhannimodule.SkyHanniModule
+import at.hannibal2.skyhanni.test.SkyHanniDebugsAndTests
+import at.hannibal2.skyhanni.utils.LocationUtils
+import at.hannibal2.skyhanni.utils.LocationUtils.canBeSeen
+import at.hannibal2.skyhanni.utils.LocationUtils.distanceSqToPlayer
+import at.hannibal2.skyhanni.utils.LocationUtils.distanceToPlayer
+import at.hannibal2.skyhanni.utils.LorenzColor
+import at.hannibal2.skyhanni.utils.LorenzUtils
+import at.hannibal2.skyhanni.utils.LorenzVec
+import at.hannibal2.skyhanni.utils.RenderUtils.draw3DLine
+import at.hannibal2.skyhanni.utils.RenderUtils.draw3DPathWithWaypoint
+import at.hannibal2.skyhanni.utils.RenderUtils.drawWaypointFilled
+import net.minecraftforge.fml.common.eventhandler.SubscribeEvent
+import java.awt.Color
+import java.io.File
+import kotlin.math.abs
+
+/**
+ * TODO
+ * benefits of every island graphs:
+ * global:
+ * 	NEU's fairy souls
+ * 	point of interest
+ * 	slayer area
+ * 	NEU's NPC's
+ * 	races (end, park, winter, dungeon hub)
+ * 	jump pads between servers
+ * 	ring of love/romeo juliet quest
+ * 	death location
+ * hub:
+ * 	12 starter NPC's
+ * 	diana
+ * farming:
+ * 	pelt farming
+ * rift:
+ * 	enigma souls
+ * 	eyes
+ * 	big quests
+ * spider:
+ * 	relicts + throw spot
+ * dwarven mines:
+ * 	emissary
+ * 	commssion areas
+ * 	events: raffle, goblin slayer, donpieresso
+ * deep
+ * 	path to the bottom
+ * end
+ * 	golem spawn
+ * 	dragon death spot
+ * crimson
+ *  vanquisher path
+ *  area mini bosses
+ *  daily quests
+ *  intro tutorials with elle
+ *
+ * graph todo:
+ * 	fix rename not using tick but input event we have (+ create the input event in the first place)
+ * 	toggle distance to node by node path lengh, instead of eye of sight lenght
+ * 	press test button again to enable "true test mode", with graph math and hiding other stuff
+ * 	option to compare two graphs, and store multiple graphs in the edit mode in paralell
+ */
+
+@SkyHanniModule
+object IslandGraphs {
+    var currentIslandGraph: Graph? = null
+
+    val existsForThisIsland get() = currentIslandGraph != null
+
+    var closedNote: GraphNode? = null
+
+    private var currentTarget: LorenzVec? = null
+    private var color = Color.WHITE
+    private var showGoalExact = false
+    private var onFound: () -> Unit = {}
+    private var goal: GraphNode? = null
+        set(value) {
+            prevGoal = field
+            field = value
+        }
+    private var prevGoal: GraphNode? = null
+
+    private var fastestPath: Graph? = null
+    private var condition: () -> Boolean = { true }
+
+    @SubscribeEvent
+    fun onRepoReload(event: RepositoryReloadEvent) {
+        if (!LorenzUtils.inSkyBlock) return
+
+        reloadFromJson(LorenzUtils.skyBlockIsland)
+    }
+
+    @SubscribeEvent
+    fun onIslandChange(event: IslandChangeEvent) {
+        reloadFromJson(event.newIsland)
+    }
+
+    @SubscribeEvent
+    fun onWorldChange(event: LorenzWorldChangeEvent) {
+        reset()
+    }
+
+    private fun reloadFromJson(newIsland: IslandType) {
+        val islandName = newIsland.name
+        val constant = "island_graphs/$islandName"
+        val name = "constants/$constant.json"
+        val jsonFile = File(SkyHanniMod.repo.repoLocation, name)
+        if (!jsonFile.isFile) {
+            currentIslandGraph = null
+            return
+        }
+
+        val graph = RepoUtils.getConstant(SkyHanniMod.repo.repoLocation, constant, Graph.gson, Graph::class.java)
+        setNewGraph(graph)
+    }
+
+    fun setNewGraph(graph: Graph) {
+        reset()
+        currentIslandGraph = graph
+    }
+
+    private fun reset() {
+        closedNote = null
+        currentTarget = null
+        goal = null
+        fastestPath = null
+    }
+
+    @SubscribeEvent
+    fun onTick(event: LorenzTickEvent) {
+        if (!LorenzUtils.inSkyBlock) return
+        val prevClosed = closedNote
+
+        val graph = currentIslandGraph ?: return
+
+        currentTarget?.let {
+            if (it.distanceToPlayer() < 3) {
+                onFound()
+                reset()
+            }
+            if (!condition()) {
+                reset()
+            }
+        }
+
+        val newClosest = if (SkyHanniDebugsAndTests.c == 0.0) {
+            graph.minBy { it.position.distanceSqToPlayer() }
+        } else null
+        if (closedNote == newClosest) return
+        closedNote = newClosest
+        onNewNote()
+        val closest = closedNote ?: return
+        val goal = goal ?: return
+        if (closest == prevClosed) return
+
+        val (path, distance) = graph.findShortestPathAsGraphWithDistance(closest, goal)
+        val first = path.firstOrNull()
+        val second = path.getOrNull(1)
+
+        val playerPosition = LocationUtils.playerLocation()
+        val nodeDistance = first?.let { playerPosition.distance(it.position) } ?: 0.0
+        if (first != null && second != null) {
+            val direct = playerPosition.distance(second.position)
+            val firstPath = first.neighbours[second] ?: 0.0
+            val around = nodeDistance + firstPath
+            if (direct < around) {
+                setFastestPath(Graph(path.drop(1)) to (distance - firstPath + direct))
+                return
+            }
+        }
+        setFastestPath(path to (distance + nodeDistance))
+    }
+
+    private fun setFastestPath(path: Pair<Graph, Double>) {
+        fastestPath = path.takeIf { it.first.isNotEmpty() }?.first
+
+        fastestPath?.let {
+            fastestPath = Graph(cutByMaxDistance(it.nodes, 3.0))
+        }
+    }
+
+    private fun onNewNote() {
+        // TODO create an event
+        IslandAreas.noteMoved()
+    }
+
+    fun stop() {
+        currentTarget = null
+        goal = null
+        fastestPath = null
+    }
+
+    fun pathFind(
+        location: LorenzVec,
+        color: Color = LorenzColor.WHITE.toColor(),
+        onFound: () -> Unit = {},
+        showGoalExact: Boolean = false,
+        condition: () -> Boolean = { true },
+    ) {
+        reset()
+        currentTarget = location
+        this.color = color
+        this.onFound = onFound
+        this.showGoalExact = showGoalExact
+        this.condition = condition
+        val graph = currentIslandGraph ?: return
+        goal = graph.minBy { it.position.distance(currentTarget!!) }
+    }
+
+    @SubscribeEvent
+    fun onRenderWorld(event: LorenzRenderWorldEvent) {
+        if (!LorenzUtils.inSkyBlock) return
+        val path = fastestPath ?: return
+
+        var graph = path
+        graph = skipNodes(graph) ?: graph
+
+        event.draw3DPathWithWaypoint(
+            graph,
+            color,
+            6,
+            true,
+            bezierPoint = 2.0,
+            textSize = 1.0,
+        )
+        val lastNode = graph.nodes.last().position
+        val targetLocation = currentTarget ?: return
+        event.draw3DLine(lastNode.add(0.5, 0.5, 0.5), targetLocation.add(0.5, 0.5, 0.5), color, 4, true)
+
+        if (showGoalExact) {
+            event.drawWaypointFilled(targetLocation, color)
+        }
+    }
+
+    // TODO move into new utils class
+    private fun cutByMaxDistance(nodes: List<GraphNode>, maxDistance: Double): List<GraphNode> {
+        var index = nodes.size * 10
+        val locations = mutableListOf<LorenzVec>()
+        var first = true
+        for (node in nodes) {
+            if (first) {
+                first = false
+            } else {
+                var lastPosition = locations.last()
+                val currentPosition = node.position
+                val vector = (currentPosition - lastPosition).normalize()
+                var distance = lastPosition.distance(currentPosition)
+                while (distance > maxDistance) {
+                    distance -= maxDistance
+                    val nextStepDistance = if (distance < maxDistance / 2) {
+                        (maxDistance + distance) / 2
+                        break
+                    } else maxDistance
+                    val newPosition = lastPosition + (vector * (nextStepDistance))
+                    locations.add(newPosition)
+                    lastPosition = newPosition
+                }
+            }
+            locations.add(node.position)
+        }
+
+        return locations.map { GraphNode(index++, it) }
+    }
+
+    // trying to find a faster node-path, if the future nodes are in line of sight and gratly beneift the current path
+    private fun skipNodes(graph: Graph): Graph? {
+        val closedNode = closedNote ?: return null
+
+        val playerEyeLocation = LocationUtils.playerEyeLocation()
+        val playerY = playerEyeLocation.y - 1
+
+        val distanceToPlayer = closedNode.position.distanceToPlayer()
+        val skipNodeDistance = distanceToPlayer > 8
+        val maxSkipDistance = if (skipNodeDistance) 50.0 else 20.0
+
+        val nodes = graph.nodes
+        val potentialSkip =
+            nodes.lastOrNull { it.position.canBeSeen(maxSkipDistance, -1.0) && abs(it.position.y - playerY) <= 2 }
+                ?: return null
+
+        val angleSkip = if (potentialSkip == nodes.first()) {
+            false
+        } else {
+            val v1 = potentialSkip.position - playerEyeLocation
+            val v2 = nodes.first().position - playerEyeLocation
+            val v = v1.angleInRad(v2)
+            v > 1
+        }
+
+        if (!skipNodeDistance && !angleSkip) return null
+
+        val list = mutableListOf<GraphNode>()
+        list.add(potentialSkip)
+
+        var passed = false
+        for (node in nodes) {
+            if (passed) {
+                list.add(node)
+            } else {
+                if (node == potentialSkip) {
+                    passed = true
+                }
+            }
+        }
+
+        return Graph(list)
+    }
+}
diff --git a/src/main/java/at/hannibal2/skyhanni/data/PurseAPI.kt b/src/main/java/at/hannibal2/skyhanni/data/PurseAPI.kt
index a5a8eb184..0f029a1f2 100644
--- a/src/main/java/at/hannibal2/skyhanni/data/PurseAPI.kt
+++ b/src/main/java/at/hannibal2/skyhanni/data/PurseAPI.kt
@@ -19,11 +19,11 @@ object PurseAPI {
     private val patternGroup = RepoPattern.group("data.purse")
     val coinsPattern by patternGroup.pattern(
         "coins",
-        "(§.)*(Piggy|Purse): §6(?<coins>[\\d,.]+)( ?(§.)*\\([+-](?<earned>[\\d,.]+)\\)?|.*)?$"
+        "(§.)*(Piggy|Purse): §6(?<coins>[\\d,.]+)( ?(§.)*\\([+-](?<earned>[\\d,.]+)\\)?|.*)?$",
     )
     val piggyPattern by patternGroup.pattern(
         "piggy",
-        "Piggy: (?<coins>.*)"
+        "Piggy: (?<coins>.*)",
     )
 
     private var inventoryCloseTime = SimpleTimeMark.farPast()
@@ -54,6 +54,7 @@ object PurseAPI {
                 return PurseChangeCause.GAIN_TALISMAN_OF_COINS
             }
 
+            // TODO relic of coins support
             if (diff == 15.million || diff == 100.million) {
                 return PurseChangeCause.GAIN_DICE_ROLL
             }
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 21440197d..8c63be891 100644
--- a/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt
+++ b/src/main/java/at/hannibal2/skyhanni/data/model/Graph.kt
@@ -12,29 +12,29 @@ import java.util.PriorityQueue
 
 @JvmInline
 value class Graph(
-    @Expose val graph: List<GraphNode>,
+    @Expose val nodes: List<GraphNode>,
 ) : List<GraphNode> {
     override val size
-        get() = graph.size
+        get() = nodes.size
 
-    override fun contains(element: GraphNode) = graph.contains(element)
+    override fun contains(element: GraphNode) = nodes.contains(element)
 
-    override fun containsAll(elements: Collection<GraphNode>) = graph.containsAll(elements)
+    override fun containsAll(elements: Collection<GraphNode>) = nodes.containsAll(elements)
 
-    override fun get(index: Int) = graph.get(index)
+    override fun get(index: Int) = nodes.get(index)
 
-    override fun isEmpty() = graph.isEmpty()
+    override fun isEmpty() = nodes.isEmpty()
 
-    override fun indexOf(element: GraphNode) = graph.indexOf(element)
+    override fun indexOf(element: GraphNode) = nodes.indexOf(element)
 
-    override fun iterator(): Iterator<GraphNode> = graph.iterator()
-    override fun listIterator() = graph.listIterator()
+    override fun iterator(): Iterator<GraphNode> = nodes.iterator()
+    override fun listIterator() = nodes.listIterator()
 
-    override fun listIterator(index: Int) = graph.listIterator(index)
+    override fun listIterator(index: Int) = nodes.listIterator(index)
 
-    override fun subList(fromIndex: Int, toIndex: Int) = graph.subList(fromIndex, toIndex)
+    override fun subList(fromIndex: Int, toIndex: Int) = nodes.subList(fromIndex, toIndex)
 
-    override fun lastIndexOf(element: GraphNode) = graph.lastIndexOf(element)
+    override fun lastIndexOf(element: GraphNode) = nodes.lastIndexOf(element)
 
     companion object {
         val gson = GsonBuilder().setPrettyPrinting().registerTypeAdapter<Graph>(
@@ -142,6 +142,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) {
 
+    val tags: List<GraphNodeTag> by lazy {
+        tagNames?.mapNotNull { GraphNodeTag.byId(it) } ?: emptyList()
+    }
+
     /** Keys are the neighbours and value the edge weight (e.g. Distance) */
     lateinit var neighbours: Map<GraphNode, Double>
 
diff --git a/src/main/java/at/hannibal2/skyhanni/data/repo/RepoManager.kt b/src/main/java/at/hannibal2/skyhanni/data/repo/RepoManager.kt
index 551f44699..ec6f0cbd9 100644
--- a/src/main/java/at/hannibal2/skyhanni/data/repo/RepoManager.kt
+++ b/src/main/java/at/hannibal2/skyhanni/data/repo/RepoManager.kt
@@ -34,7 +34,7 @@ class RepoManager(private val configLocation: File) {
 
     private val gson get() = ConfigManager.gson
     private var latestRepoCommit: String? = null
-    private val repoLocation: File = File(configLocation, "repo")
+    val repoLocation: File = File(configLocation, "repo")
     private var error = false
     private var lastRepoUpdate = SimpleTimeMark.farPast()