Optimization of aStar in Java

I'm currently looking to optimize my aStar algorithm as my last run through took roughly a minute to generate one path. I've never had to optimize before as I've never run into performance issues, so I'm not sure where to even start with this one.

http://pastebin.com/MbZtyQFu

```
import java.util.ArrayList;
import java.util.List;
import java.util.Collections;

public class Pathfinding
{
List closedList = new ArrayList();
List openList = new ArrayList();
int j = 0;

public Node aStar(TiledMap tiles, Node start, Node goal)
{

Node currentNode = new Node(start.row, start.col, start.gCost, start.fCost, null);
// closedList.clear();
//openList.clear();

while (!reachedGoal(currentNode, goal))
{
int row = currentNode.row;
int col = currentNode.col;

//right child
col++;
addChild(row, col, tiles, currentNode, goal);

//left child
col -= 2;
addChild(row, col, tiles, currentNode, goal);

//top child
col++;
row--;
addChild(row, col, tiles, currentNode, goal);

//bottom child
row += 2;
addChild(row, col, tiles, currentNode, goal);

//bottom right
col++;
addChild(row, col, tiles, currentNode, goal);

//bottom left
col -= 2;
addChild(row, col, tiles, currentNode, goal);

//top left
row -= 2;
addChild(row, col, tiles, currentNode, goal);

//top right
col += 2;
addChild(row, col, tiles, currentNode, goal);

//Put currentNode in the closedList
closedList.add(currentNode);
//Sort the openList
Collections.sort(openList);
//Assign currentNode to the last element in the List
currentNode = openList.remove(openList.size() - 1);
//System.out.println("Curr Node Row " + currentNode.row + ", Curr Node Col " + currentNode.col);
}
return currentNode;
}

public boolean reachedGoal(Node currentNode,

Teach a Man to Fish

If you have a program that is running slower than you expect, and you want to know where it is slow, the right answer is to profile the code. There's a question at StackOverflow
that describes a number of tools that will allow you to run the code and find the hotspots.

Alternatively, the poor man's profiler is to just to dump stack traces (send a signal via ctrl-break or kill -3) and look to see what method you are in right now. If your program is running slowly, at any given moment it is probably in a slow part of the code. If you break several times, and see that you are in the same place each time, the odds are very good that you are looking at the problem.

Give a Man a Fish

public boolean isNodeClosed(double row, double col)
{
     for (int i = 0; i < closedList.size(); ++i)
     {
         if (closedList.get(i).col == col && closedList.get(i).row == row)
         {
             return true;
         }
     }
     return false;
}

This is likely to be one of your problems; think about the behavior of this code for a moment -- to figure out if a node is closed, you are iterating through a list of every node you have already closed. As your solution progresses, this list gets longer and longer, which means figuring out if the node is closed keeps getting slower.

public Node getChildFromOpen(double row, double col, List openList)
 {
    for (int i = 0; i < openList.size(); ++i)
    {
        if (openList.get(i).col == col && openList.get(i).row == row)
        {
            return openList.get(i);
        }
    }
    return null;
}

Same problem here -- as more nodes go into the open list, finding the open node takes longer and longer.

Imagine if instead you were to keep track of what is open and closed by coordinates:

public boolean isOpen(int row, int col, boolean[][] open) 
{
    return open[row][col];
}

Now your lookup goes from O(N), meaning that the time required is a function of the number of nodes in your problem, to O(1) meaning that the time required is constant.

Of course, since you've created a Node class that has a row and column property, it might make sense to use nodes directly

public boolean isOpen(Node n, boolean [][] open) 
{
    return open[n.row][n.col];
}

But, more advanced programmers wouldn't do it this way. The problem with your List implementation is that figuring out if a List contains a specific node is slow. You've chosen the wrong kind of collection. Set, in particular HashSet is designed for this kind of thing.

public boolean isOpen(Node n, Set open) 
{
    return open.contains(n);
}

Now, sets depend on being able to recognize when two objects are the same. In general, it does this by using Object.hashCode() to decide which "bucket" to use to keep track of the object. Again, searching StackOverflow will provide suggestions on how to implement hashcode. For complicated objects, you might lean on something like Guava's HashFunction.

In this specific case, you don't really need to be hashing the entire node -- you are really only interested in where the node is located. So you might separate out those two ideas

class Location
{
     public int row;
     public int col;

     public int hashCode ()
     {
         return 37 * row + col ;
     }
}

class Node implements Comparable
{
    public Location location;

    public double gCost;
    public double fCost;
    public Node parentNode = null;
}

public boolean isOpen(Node n, Set open) {
    return open.contains(n.location);
}

Now, it's a bad idea to let values in a hashed collection change their hash values on the fly, so we should take some steps to lock down Location as a value-type.

class Location
{
     public final int row;
     public final int col;

     public Location(int row, int col)
     {
          this.row = row;
          this.col = col;
     }

     public int hashCode ()
     {
         return 37 * row + col ;
     }
}

Location is probably a nice abstraction for you here, since it greatly simplifies some of your "are we done yet?" checks, because you want to check your current Node is in the same Location as your goal. Location.equals() is a straight forward way to implement that idea. Once again: see StackOverflow; you are over-riding Object.equals(), and therefore it is important that you get the details right. (Joshua Block dedicated a chapter to these sorts of problems).

```
class Location
{
public int row;
public int col;

public boolean equals(Object obj)
{
if (!obj instanceof Location)
{
return false;
}
if (obj == that)
{
return true;
}
Location that = (Location) obj;

return (this.row == that.row) && (this.col == that.col);
}

public int hashCode () {
return 37 * row + col ;
}
}

public boolean reachedGoal(Node currentNode, Node goalNode)

StackExchange Code Review Q#55259, answer score: 11