Feature: Graphs Pathfinding (#2468)

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

5 files changed, 345 insertions, 26 deletions

diff --git a/src/main/java/at/hannibal2/skyhanni/features/event/diana/GriffinBurrowHelper.kt b/src/main/java/at/hannibal2/skyhanni/features/event/diana/GriffinBurrowHelper.kt
index 35a783f7d..aa58c3c0f 100644
--- a/src/main/java/at/hannibal2/skyhanni/features/event/diana/GriffinBurrowHelper.kt
+++ b/src/main/java/at/hannibal2/skyhanni/features/event/diana/GriffinBurrowHelper.kt
@@ -49,17 +49,16 @@ object GriffinBurrowHelper {
 
     private val config get() = SkyHanniMod.feature.event.diana
 
-    private val allowedBlocksAboveGround =
-        listOf(
-            Blocks.air,
-            Blocks.leaves,
-            Blocks.leaves2,
-            Blocks.tallgrass,
-            Blocks.double_plant,
-            Blocks.red_flower,
-            Blocks.yellow_flower,
-            Blocks.spruce_fence
-        )
+    private val allowedBlocksAboveGround = listOf(
+        Blocks.air,
+        Blocks.leaves,
+        Blocks.leaves2,
+        Blocks.tallgrass,
+        Blocks.double_plant,
+        Blocks.red_flower,
+        Blocks.yellow_flower,
+        Blocks.spruce_fence,
+    )
 
     var targetLocation: LorenzVec? = null
     private var guessLocation: LorenzVec? = null
@@ -134,7 +133,14 @@ object GriffinBurrowHelper {
             }
             locations.addAll(InquisitorWaypointShare.waypoints.values.map { it.location })
         }
-        targetLocation = locations.minByOrNull { it.distanceToPlayer() }
+        val newLocation = locations.minByOrNull { it.distanceToPlayer() }
+        if (targetLocation != newLocation) {
+            targetLocation = newLocation
+            // add island graphs here some day when the hub is fully added in the graph
+//             newLocation?.let {
+//                 IslandGraphs.find(it)
+//             }
+        }
 
         if (config.burrowNearestWarp) {
             targetLocation?.let {
@@ -401,7 +407,7 @@ object GriffinBurrowHelper {
             if (currentMayor != Mayor.DIANA) {
                 ChatUtils.chatAndOpenConfig(
                     "§cSelect Diana as mayor overwrite!",
-                    SkyHanniMod.feature.dev.debug::assumeMayor
+                    SkyHanniMod.feature.dev.debug::assumeMayor,
                 )
 
             } else {
diff --git a/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocations.kt b/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocations.kt
index cce0aef79..896220842 100644
--- a/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocations.kt
+++ b/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocations.kt
@@ -30,7 +30,7 @@ object HoppityEggLocations {
             ChocolateFactoryAPI.profileStorage?.collectedEggLocations = value
         }
 
-    private var apiEggLocations: Map<IslandType, Map<String, LorenzVec>> = mapOf()
+    var apiEggLocations: Map<IslandType, Map<String, LorenzVec>> = mapOf()
 
     val islandLocations
         get() = apiEggLocations[LorenzUtils.skyBlockIsland]?.values?.toSet() ?: emptySet()
diff --git a/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocator.kt b/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocator.kt
index d15d43d81..0d5bfefa8 100644
--- a/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocator.kt
+++ b/src/main/java/at/hannibal2/skyhanni/features/event/hoppity/HoppityEggLocator.kt
@@ -1,6 +1,7 @@
 package at.hannibal2.skyhanni.features.event.hoppity
 
 import at.hannibal2.skyhanni.data.ClickType
+import at.hannibal2.skyhanni.data.IslandGraphs
 import at.hannibal2.skyhanni.events.DebugDataCollectEvent
 import at.hannibal2.skyhanni.events.ItemClickEvent
 import at.hannibal2.skyhanni.events.LorenzRenderWorldEvent
@@ -19,6 +20,7 @@ import at.hannibal2.skyhanni.utils.LorenzUtils
 import at.hannibal2.skyhanni.utils.LorenzUtils.round
 import at.hannibal2.skyhanni.utils.LorenzVec
 import at.hannibal2.skyhanni.utils.NEUInternalName.Companion.asInternalName
+import at.hannibal2.skyhanni.utils.NumberUtil.formatInt
 import at.hannibal2.skyhanni.utils.RecalculatingValue
 import at.hannibal2.skyhanni.utils.RenderUtils.draw3DLine
 import at.hannibal2.skyhanni.utils.RenderUtils.drawColor
@@ -154,8 +156,7 @@ object HoppityEggLocator {
     }
 
     private fun LorenzRenderWorldEvent.drawEggWaypoint(location: LorenzVec, label: String) {
-        val shouldMarkDuplicate = config.highlightDuplicateEggLocations
-            && HoppityEggLocations.hasCollectedEgg(location)
+        val shouldMarkDuplicate = config.highlightDuplicateEggLocations && HoppityEggLocations.hasCollectedEgg(location)
         val possibleDuplicateLabel = if (shouldMarkDuplicate) "$label §c(Duplicate Location)" else label
         if (!shouldMarkDuplicate) {
             drawWaypointFilled(location, config.waypointColor.toChromaColor(), seeThroughBlocks = true)
@@ -165,8 +166,7 @@ object HoppityEggLocator {
         drawDynamicText(location.add(y = 1), possibleDuplicateLabel, 1.5)
     }
 
-    private fun shouldShowAllEggs() =
-        config.showAllWaypoints && !locatorInHotbar && HoppityEggType.eggsRemaining()
+    private fun shouldShowAllEggs() = config.showAllWaypoints && !locatorInHotbar && HoppityEggType.eggsRemaining()
 
     fun eggFound() {
         resetData()
@@ -214,6 +214,7 @@ object HoppityEggLocator {
         if (event.clickType == ClickType.RIGHT_CLICK && item.isLocatorItem) {
             lastClick = SimpleTimeMark.now()
             MythicRabbitPetWarning.check()
+            trySendingGraph()
         }
     }
 
@@ -264,20 +265,29 @@ object HoppityEggLocator {
 
         possibleEggLocations = filteredEggs
 
+        if (drawLocations) return
         drawLocations = true
+
+        trySendingGraph()
+    }
+
+    private fun trySendingGraph() {
+        if (!config.showPathFinder) return
+        val location = possibleEggLocations.firstOrNull() ?: return
+
+        val color = config.waypointColor.toChromaColor()
+
+        IslandGraphs.pathFind(location, color, condition = { config.showPathFinder })
     }
 
-    fun isValidEggLocation(location: LorenzVec): Boolean =
-        HoppityEggLocations.islandLocations.any { it.distance(location) < 5.0 }
+    fun isValidEggLocation(location: LorenzVec): Boolean = HoppityEggLocations.islandLocations.any { it.distance(location) < 5.0 }
 
-    private fun ReceiveParticleEvent.isVillagerParticle() =
-        type == EnumParticleTypes.VILLAGER_HAPPY && speed == 0.0f && count == 1
+    private fun ReceiveParticleEvent.isVillagerParticle() = type == EnumParticleTypes.VILLAGER_HAPPY && speed == 0.0f && count == 1
 
-    private fun ReceiveParticleEvent.isEnchantmentParticle() =
-        type == EnumParticleTypes.ENCHANTMENT_TABLE && speed == -2.0f && count == 10
+    private fun ReceiveParticleEvent.isEnchantmentParticle() = type == EnumParticleTypes.ENCHANTMENT_TABLE && speed == -2.0f && count == 10
 
-    fun isEnabled() = LorenzUtils.inSkyBlock && config.waypoints && !GardenAPI.inGarden() &&
-        !ReminderUtils.isBusy(true) && HoppityAPI.isHoppityEvent()
+    fun isEnabled() =
+        LorenzUtils.inSkyBlock && config.waypoints && !GardenAPI.inGarden() && !ReminderUtils.isBusy(true) && HoppityAPI.isHoppityEvent()
 
     private val ItemStack.isLocatorItem get() = getInternalName() == locatorItem
 
@@ -314,4 +324,16 @@ object HoppityEggLocator {
             add("Current Egg Note: ${currentEggNote ?: "None"}")
         }
     }
+
+    fun testPathfind(args: Array<String>) {
+        val target = args[0].formatInt()
+        HoppityEggLocations.apiEggLocations[LorenzUtils.skyBlockIsland]?.let {
+            for ((i, location) in it.values.withIndex()) {
+                if (i == target) {
+                    IslandGraphs.pathFind(location)
+                    return
+                }
+            }
+        }
+    }
 }
diff --git a/src/main/java/at/hannibal2/skyhanni/features/mining/TunnelsMaps.kt b/src/main/java/at/hannibal2/skyhanni/features/mining/TunnelsMaps.kt
index afe5694b1..8d7f771b7 100644
--- a/src/main/java/at/hannibal2/skyhanni/features/mining/TunnelsMaps.kt
+++ b/src/main/java/at/hannibal2/skyhanni/features/mining/TunnelsMaps.kt
@@ -447,6 +447,7 @@ object TunnelsMaps {
             true,
             bezierPoint = 2.0,
             textSize = config.textSize.toDouble(),
+            showNoteNames = true,
         )
         event.drawDynamicText(
             if (config.distanceFirst) {
diff --git a/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt b/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt
new file mode 100644
index 000000000..c5c0071f9
--- /dev/null
+++ b/src/main/java/at/hannibal2/skyhanni/features/misc/IslandAreas.kt
@@ -0,0 +1,290 @@
+package at.hannibal2.skyhanni.features.misc
+
+import at.hannibal2.skyhanni.SkyHanniMod
+import at.hannibal2.skyhanni.data.IslandGraphs
+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
+import at.hannibal2.skyhanni.events.LorenzRenderWorldEvent
+import at.hannibal2.skyhanni.events.LorenzTickEvent
+import at.hannibal2.skyhanni.events.LorenzWorldChangeEvent
+import at.hannibal2.skyhanni.skyhannimodule.SkyHanniModule
+import at.hannibal2.skyhanni.utils.ChatUtils
+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.LocationUtils.canBeSeen
+import at.hannibal2.skyhanni.utils.LocationUtils.distanceToPlayer
+import at.hannibal2.skyhanni.utils.LorenzColor
+import at.hannibal2.skyhanni.utils.LorenzUtils
+import at.hannibal2.skyhanni.utils.LorenzUtils.round
+import at.hannibal2.skyhanni.utils.RenderUtils.drawDynamicText
+import at.hannibal2.skyhanni.utils.RenderUtils.renderRenderable
+import at.hannibal2.skyhanni.utils.renderables.Renderable
+import at.hannibal2.skyhanni.utils.renderables.Searchable
+import at.hannibal2.skyhanni.utils.renderables.buildSearchBox
+import at.hannibal2.skyhanni.utils.renderables.toSearchable
+import net.minecraft.client.Minecraft
+import net.minecraftforge.fml.common.eventhandler.SubscribeEvent
+import kotlin.time.Duration.Companion.seconds
+
+@SkyHanniModule
+object IslandAreas {
+    private val config get() = SkyHanniMod.feature.misc.areaNavigation
+
+    private var nodes = mapOf<GraphNode, Double>()
+    private var paths = mapOf<GraphNode, Graph>()
+    private var display: Renderable? = null
+    private var targetNode: GraphNode? = null
+    private var currentAreaName = ""
+    private val textInput = TextInput()
+
+    @SubscribeEvent
+    fun onWorldChange(event: LorenzWorldChangeEvent) {
+        nodes = emptyMap()
+        display = null
+        targetNode = null
+        hasMoved = true
+    }
+
+    fun noteMoved() {
+        updateNodes()
+    }
+
+    private fun updateNodes() {
+        if (!isEnabled()) return
+        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
+        }
+        this.paths = paths
+
+        val finalNodes = mutableMapOf<GraphNode, Double>()
+
+        val alreadyFoundAreas = mutableListOf<String>()
+        for ((node, distance) in map.sorted()) {
+            val areaName = node.name ?: continue
+            if (areaName in alreadyFoundAreas) continue
+            alreadyFoundAreas.add(areaName)
+
+            finalNodes[node] = distance
+        }
+
+        nodes = finalNodes
+    }
+
+    var hasMoved = false
+
+    @SubscribeEvent
+    fun onTick(event: LorenzTickEvent) {
+        if (!LorenzUtils.inSkyBlock) return
+        if (!IslandGraphs.existsForThisIsland) return
+
+        if (event.isMod(2) && hasMoved) {
+            hasMoved = false
+            updatePosition()
+        }
+    }
+
+    @SubscribeEvent
+    fun onPlayerMove(event: EntityMoveEvent) {
+        if (isEnabled()) {
+            if (event.entity == Minecraft.getMinecraft().thePlayer) {
+                hasMoved = true
+            }
+        }
+    }
+
+    private fun updatePosition() {
+        display = buildDisplay().buildSearchBox(textInput)
+    }
+
+    @SubscribeEvent
+    fun onOverlay(event: GuiRenderEvent.GuiOverlayRenderEvent) {
+        if (!isEnabled()) return
+        if (!config.pathfinder.enabled) return
+        if (!config.pathfinder.showAlways) return
+
+        display?.let {
+            config.pathfinder.position.renderRenderable(it, posLabel = "Island Areas")
+        }
+    }
+
+    @SubscribeEvent
+    fun onOverlay(event: GuiRenderEvent.ChestGuiOverlayRenderEvent) {
+        if (!isEnabled()) return
+        if (!config.pathfinder.enabled) return
+
+        display?.let {
+            config.pathfinder.position.renderRenderable(it, posLabel = "Island Areas")
+        }
+    }
+
+    private fun buildDisplay() = buildList<Searchable> {
+        val closedNote = IslandGraphs.closedNote ?: return@buildList
+        val playerDiff = closedNote.position.distanceToPlayer()
+
+        var foundCurrentArea = false
+        var foundAreas = 0
+
+        for ((node, diff) in nodes) {
+            val difference = diff + playerDiff
+            val tag = node.getAreaTag() ?: continue
+
+            val name = node.name ?: continue
+            // can not compare nodes directly. By using names, we also accept other nodes
+            val isTarget = node.name == targetNode?.name
+            val color = if (isTarget) LorenzColor.GOLD else tag.color
+
+            // trying to find a faster path to the existing target
+            if (isTarget && node != targetNode) {
+                ChatUtils.debug("Found a faster node, rerouting...")
+                setTarget(node)
+            }
+            val coloredName = "${color.getChatColor()}${name}"
+
+            var suffix = ""
+            paths[node]?.let { path ->
+                val passedAreas = path.nodes.filter { it.getAreaTag() != null }.map { it.name }.distinct().toMutableList()
+                passedAreas.remove(name)
+                passedAreas.remove(null)
+                passedAreas.remove("null")
+                passedAreas.remove(currentAreaName)
+                // so show areas needed to pass thorough
+                if (passedAreas.isNotEmpty()) {
+//                     suffix = " §7${passedAreas.joinToString(", ")}"
+                }
+            }
+
+            val distance = difference.round(1)
+            val text = "${coloredName}§7: §e$distance$suffix"
+
+            if (!foundCurrentArea) {
+                foundCurrentArea = true
+
+                val inAnArea = name != "no_area"
+                if (config.pathfinder.includeCurrentArea.get()) {
+                    if (inAnArea) {
+                        addSearchString("§eCurrent area: $coloredName")
+                    } else {
+                        addSearchString("§7Not in an area.")
+                    }
+                }
+                if (name != currentAreaName) {
+                    if (inAnArea && config.enterTitle) {
+                        LorenzUtils.sendTitle("§aEntered $name!", 3.seconds)
+                    }
+                    currentAreaName = name
+                }
+
+                addSearchString("§eAreas nearby:")
+                continue
+            }
+
+            if (name == "no_area") continue
+            foundAreas++
+
+            add(
+                Renderable.clickAndHover(
+                    text,
+                    tips = buildList {
+                        add(tag.color.getChatColor() + node.name)
+                        add("§7Type: ${tag.displayName}")
+                        add("§7Distance: §e$distance blocks")
+                        add("")
+                        if (node == targetNode) {
+                            add("§aPath Finder points to this!")
+                            add("")
+                            add("§eClick to disable!")
+                        } else {
+                            add("§eClick to find a path!")
+                        }
+                    },
+                    onClick = {
+                        if (node == targetNode) {
+                            targetNode = null
+                            IslandGraphs.stop()
+                            updatePosition()
+                        } else {
+                            setTarget(node)
+                        }
+                    },
+                ).toSearchable(name),
+            )
+        }
+        if (foundAreas == 0) {
+            val islandName = LorenzUtils.skyBlockIsland.displayName
+            if (foundCurrentArea) {
+                addSearchString("§cThere is only one area in $islandName,")
+                addSearchString("§cnothing else to navigate to!")
+            } else {
+                addSearchString("§cThere is no $islandName area data avaliable yet!")
+            }
+        }
+    }
+
+    @SubscribeEvent
+    fun onRenderWorld(event: LorenzRenderWorldEvent) {
+        if (!LorenzUtils.inSkyBlock) return
+        if (!config.inWorld) return
+        for ((node, distance) in nodes) {
+            val name = node.name ?: continue
+            if (name == currentAreaName) continue
+            if (name == "no_area") continue
+            val position = node.position
+            val color = node.getAreaTag()?.color?.getChatColor() ?: ""
+            if (!position.canBeSeen(40.0)) return
+            event.drawDynamicText(position, color + name, 1.5)
+        }
+    }
+
+    @SubscribeEvent
+    fun onConfigLoad(event: ConfigLoadEvent) {
+        ConditionalUtils.onToggle(config.pathfinder.color) {
+            targetNode?.let {
+                setTarget(it)
+            }
+        }
+        ConditionalUtils.onToggle(config.pathfinder.color, config.pathfinder.includeCurrentArea) {
+            updateNodes()
+            updatePosition()
+        }
+    }
+
+    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)
+    }
+
+    private fun setTarget(node: GraphNode) {
+        targetNode = node
+        val color = config.pathfinder.color.get().toChromaColor()
+        IslandGraphs.pathFind(
+            node.position, color,
+            onFound = {
+                targetNode = null
+                updatePosition()
+            },
+            condition = { config.pathfinder.enabled },
+        )
+        hasMoved = true
+    }
+
+    fun isEnabled() = LorenzUtils.inSkyBlock && config.let { it.pathfinder.enabled || it.enterTitle || it.inWorld }
+}