So I creating a minecraft plugin where I am in need of a graph to create a navigation system. I researched a bit and found out that I should be able to use Dijkstra, but I have a problem. When searching for the shortest path I am sometimes getting an infinite loop(not always, it usally works the first 2-3 runs but after that it goes into the loop).
When the player wants to get to a destination I search for the closest vertex and use computePaths with that vertex as parameter. When I then run the getShortestPathTo it sometimes gets stuck in an infinite loop and I run out of memory(which makes sence since im adding the same vertexes to the list). Can you see why it is getting stuck? As far as I knew Dijkstra should be able to handle going from A node to B node and from B node to A node right?
Below is my code:
public class Dijkstra { public static void computePaths(Vertex source) { source.minDistance = 0.; PriorityQueue<Vertex> vertexQueue = new PriorityQueue<Vertex>(); vertexQueue.add(source); while (!vertexQueue.isEmpty()) { Vertex u = vertexQueue.poll(); // Visit each edge exiting u for (Edge e : u.adjacencies) { Vertex v = e.target; double weight = e.weight; double distanceThroughU = u.minDistance + weight; if (distanceThroughU < v.minDistance) { vertexQueue.remove(v); v.minDistance = distanceThroughU; v.previous = u; vertexQueue.add(v); } } } } public static List<Vertex> getShortestPathTo(Vertex target) { List<Vertex> path = new ArrayList<Vertex>(); for (Vertex vertex = target; vertex != null; vertex = vertex.previous) { path.add(vertex); } Collections.reverse(path); return path; } } and the vertex class:
public class Vertex implements Comparable<Vertex> { public final String name; public Edge[] adjacencies; public double minDistance = Double.POSITIVE_INFINITY; public Vertex previous; public Location location; public Vertex(String argName) { name = argName; } public Vertex(String argName,Location l) { name = argName; location = l;} public String toString() { return name; } public int compareTo(Vertex other) { return Double.compare(minDistance, other.minDistance); } } When first the plugin is enabled I load all the vertexes from a config file looking something like this(It is the test one i am using)
I am adding vertexes and edges here(not sure if relevent but thought it might be?):
public void loadAllVertex() { ConfigurationSection section = nodeConfig.config.getConfigurationSection("nodes"); for (String key: section.getKeys(false)) { String locationString = nodeConfig.getString("nodes." + key + ".location"); if (locationString == null) return; String[] locationSplit = locationString.split(","); if (locationSplit.length <=1) { log.log(Level.SEVERE, "Location is not specified correctly in nodes.yml"); return; } Location l = new Location(Bukkit.getWorlds().get(0),Integer.parseInt(locationSplit[0]),Integer.parseInt(locationSplit[1]),Integer.parseInt(locationSplit[2])); Vertex tmpVertex = new Vertex(key, l); allNodes.add(tmpVertex); } for (Vertex v : allNodes) { String path = "nodes." + v.name + ".connectedTo"; List<String> connectedTo = nodeConfig.getStringList(path,true); List<Edge> edges = new ArrayList<>(); for (String sideNodeName : connectedTo) { Vertex vertexCon = GraphUtils.getVertexByName(allNodes, sideNodeName); if (vertexCon == null) { log.warning("The '" + sideNodeName + "' node is not defined"); return; } //A.adjacencies = new Edge[]{ new Edge(M, 8) }; edges.add(new Edge(vertexCon,vertexCon.location.distance(v.location))); } Edge[] arrayEdges = new Edge[edges.size()]; arrayEdges = edges.toArray(arrayEdges); v.adjacencies = arrayEdges; } } 1 Answers
Answers 1
Think i found the error, so I never had any loops the first time I ran the compute path and findshortestpath so I finally figured out that I could not be resetting things correctly(should have been obvious I know) - I didn't update the vertexes afterwards. So I added a method to reset the mindistance and previous attributes and this seems to have done the trick.
0 comments:
Post a Comment