diff options
Diffstat (limited to 'src/main/java/at/hannibal2/skyhanni/data')
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 |