(Issues solved) I did not multiple the heuristic by the correct cost. But... why would this have mattered in the way it could not find a path? It should visit each node anyway afaik. If I simply return 0 on the heuristic it should work like Dijkstra but it is not adding anything to the openList. Anyway, this obviously fixed the performance issue by a great deal since it was not sorting correctly and the closed list was getting huge.
Original post
I am trying to make my own Hierarchical pathfinding system and apart from the fact I still think it's slow I'm having a issue I cannot put my finger on. I want to solve this issue first before I continue. I will explain what I have and start with this picture to visualize it for you. It is the top right of the map, so no node connection on the far top and far right are needed since the map ends there.
I have divided the map into "sectors" and connect these sectors by nodes (white circles). In the sector with the blue circles I have selected the single white one and painting all connected nodes blue, so afaik this is correctly implemented. The red ones are the path I generated from the bottom left to the bottom right.
When I request a path I create a node at the start and destination and add all reachable nodes in that sector as connections with corresponding costs. Then I add the start node to the open list and perform A* search.
The first time this always finds a path if there is a path. But somehow if I try to find a path between topleft-bottomright and then topright-bottomleft it won't find a path for the seconds one. If I start my program and do that in reversed order it won't find a path for topleft-bottomright. On a smaller scale, so not traversing the complete map but just a couple of sectors there does not seem to be a problem.
public List<Node> findNodePath(Coordinates start, Coordinates destination)
{
long time = System.nanoTime();
List<Node> path = new ArrayList<Node>();
boolean pathFound = false;
//create startnode and connect it to sector exits.
Node startNode = findExitNodes(start); //Find exit nodes for the sector start is in
startNode.setH(manhattanHeuristic(start, destination));
startNode.setG(0);
Node destinationNode = findExitNodes(destination); //Find exit nodes for the sector destination is in.
List<Node> openList = new ArrayList<Node>(); //Deciding what datastructure is best
CostComparator comparator = new CostComparator();
TreeSet<Node> closedList = new TreeSet<Node>(comparator); //Treemap since closeList is more for looking up then inserting
openList.add(startNode);
while (openList.size() > 0)
{
//sort openList
Collections.sort(openList, comparator);
//pop first
Node currentNode = openList.remove(0);
closedList.add(currentNode);
//Check if connection with the destination node is made.
//Todo: add a more efficient way of finding destination
for (Connection c : destinationNode.getConnections())
{
if (c.getTo().equals(currentNode)) pathFound = true;
}
if (!pathFound) {
//Find all connections and add them to the openlist
for (Connection c : currentNode.getConnections()) {
if (!closedList.contains(c.getTo())) {
if (!openList.contains(c.getTo())) {
//If it's not on the openList add it
c.getTo().setH(manhattanHeuristic(c.getTo().getPosition(), destination));
c.getTo().setG(currentNode.getG() + c.getCost());
c.getTo().setParent(currentNode);
openList.add(c.getTo());
} else {
//If it's already on the openList check if this is closer to start point and update it.
if (c.getTo().getG() > currentNode.getG() + c.getCost()) {
c.getTo().setG(currentNode.getG() + c.getCost());
c.getTo().setParent(currentNode);
//Collections.sort(openList, comparator);
}
}
}
}
}
else //currentNode is connected to destination
{
System.out.print("Path found! ");
while (currentNode.getParent() != null)
{
path.add(currentNode);
currentNode = currentNode.getParent();
}
//Break out of while loop
break;
}
}
System.out.println((System.nanoTime() - time) / 1000000 + "ms");
return path;
}
Now I really hope someone can spot what I am doing wrong. The only thing I am altering in the main graph is the G & H and the parent. But this should not matter since if it's not on the openList yet I am setting these to the correct values. The cost comparator just sorts on highest F score (G + H).
@Override
public int compare(Node n1, Node n2) {
return n1.getF() < n2.getF() ? -1 : n1.getF() == n2.getF() ? 0 : 1;
}
And the equals and hashcode of node are derived from just the coordinates.
Node.Java
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Node node = (Node) o;
return position.equals(node.position);
}
@Override
public int hashCode() {
return position.hashCode();
}
Coordinate.java
@Override
public boolean equals(Object o) {
if (this == o) return true;
if (o == null || getClass() != o.getClass()) return false;
Coordinates that = (Coordinates) o;
if (x != that.x) return false;
return y == that.y;
}
@Override
public int hashCode() {
int result = x;
result = 31 * result + y;
return result;
}
Performance?
Now other then this I find this to be very slow and this is probably mostly because of the closedList lookups. I am aware that my map in it's current state pretty much represents a worse case of a map, it is generating a lot more nodes then a open/indoor/playerbuild type of map. Anyway, on smaller maps with regular A* I have been using a boolean[][] as the close list so I had direct access if a certain location was already closed. I was getting near the same lookup times as I have now with a hierarchical search. But for this project I want to have a much larger map and do not want a huge boolean[][] in memory. So can you see a major performance issue and how to speed it up? Any other way to speed it up? I have a private HashMap<Coordinates, Node>[][] sectorGraph; which could be useful for much quicker lookups if I know which sector to look for.