Optimization of aStar in Java

Question

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<Node> closedList = new ArrayList<Node>();
List<Node> openList = new ArrayList<Node>();
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, Node goalNode)
{
    return (currentNode.col == goalNode.col) && (currentNode.row == goalNode.row);
}

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;
}

public Node getChildFromOpen(double row, double col, List<Node> 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;
}

public void addChild(int row, int col, TiledMap tiles, Node currentNode, Node target)
{
    if((row >= 0 && col >= 0) && (row <= 14 && col <= 39))
    {
        if (tiles.isPassable(row, col))
        {
            if (!isNodeClosed(row, col))
            {
                double g = currentNode.gCost + getDistanceFromParent(row, col, currentNode);
                double f = g + getDistance(row, col, target);
                Node child = getChildFromOpen(row, col, openList);

                if (child == null)
                {
                    child = new Node(row, col, g, f, currentNode);
                    openList.add(child);
                }
                else if (child.gCost > g)
                {
                    child.fCost = f;
                    child.gCost = g;
                    child.parentNode = currentNode;
                }
            }
        }
    }
}

public double getDistance(int row, int col, Node goal)
{
    return Math.sqrt((goal.row - row) * (goal.row - row) + (goal.col - col) * (goal.col - col));
}

public double getDistanceFromParent(int row, int col, Node parent)
{
    return Math.sqrt((row - parent.row) * (row - parent.row) + (col - parent.col) * (col - parent.col));
}

Node class

class Node implements Comparable<Node>
{
    public int row;
    public int col;
    public double gCost;
    public double fCost;
    public Node parentNode = null;

    public Node (int row, int col, double gCost, double fCost, Node parentNode)
    {
        this.row = row;
        this.col = col;
        this.gCost = gCost;
        this.fCost = fCost;
        this.parentNode = parentNode;
    }

    public int compareTo(Node other)
    {
        if(this.fCost < other.fCost)
        {
            return 1;
        }
        else if(this.fCost > other.fCost)
        {
            return -1;
        }
        else
        {
            return 0;
        }
    }
}

Answer 1

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<Node> 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<Node> 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<Node>
{
    public Location location;

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

public boolean isOpen(Node n, Set<Location> 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)
{
     return currentNode.location.equals(goalNode.location);
}

It could make sense to tease out the scores as another class as well. Because we aren't using Score as a key anywhere, we can leave the cost variables mutable.

class Score implements Comparable<Score>
{
    public double gCost;
    public double fCost;

    public int compareTo(Score other)
    {
        if(this.fCost < other.fCost)
        {
             return 1;
        }
        else if(this.fCost > other.fCost)
        {
             return -1;
        }
        else
        {
             return 0;
        }
    }
}

class Node implements Comparable<Node>
{
    public Location location;
    public Score score;
    public Node parentNode = null;

    public int compareTo(Score other)
    {
        return score.compareTo(other.score);
    }
}

At this point, you may even find that you don't need Node any more; you really just have different kinds of lookups based on Location.

Map<Location,Location> lookupParent = new HashMap();
Map<Location,Score> lookupScore = new HashMap();
Set<Location> openNodes = new HashSet();
Set<Location> closedNodes = new HashSet();

Answer 2

First of all, write shorter methods. It's better for the readers, its' better for the compiler (I've seen a factor two speed up after simply splitting a method into two), and it's better for you.

Avoid needless division in loops, it looks like you're working on a fixed grid.

Don't sort an ArrayList where a PriorityQueue does the job.

Try to implement the LOSCheck without so many cases. It may be hard and even cost some time, but it can make the program cleaner and easier to optimize.

I'm afraid, this doesn't solve your problem, but it's too long for a comment. I'll add some information later. However, a code review is what this question needs, and I'd suggest to move it there (and then my ramblings are right in place).

Answer 3

I suggest you look at;

• use a CPU profiler to see where it is spending most of it's time. If it is in a large method, consider breaking it up to get clarity.
• try stepping through the code in your debugger for a simple example to see if there is any obvious inefficiencies. e.g. is it valid to visit the same node more than once.